Introduction

In this blog post, we'll share the most commonly asked coding interview questions at LTI. If you don't have months to study for your interviews, you can use AI tools like Chatmagic to generate solutions quickly and efficiently - helping you pass the interviews and get the job offer!

Problem #1: Maximum White Tiles Covered by a Carpet

You are given a 2D integer array tiles where tiles[i] = [li, ri] represents that every tile j in the range li <= j <= ri is colored white. You are also given an integer carpetLen, the length of a single carpet that can be placed anywhere. Return the maximum number of white tiles that can be covered by the carpet. Example 1: Input: tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10 Output: 9 Explanation: Place the carpet starting on tile 10. It covers 9 white tiles, so we return 9. Note that there may be other places where the carpet covers 9 white tiles. It can be shown that the carpet cannot cover more than 9 white tiles. Example 2: Input: tiles = [[10,11],[1,1]], carpetLen = 2 Output: 2 Explanation: Place the carpet starting on tile 10. It covers 2 white tiles, so we return 2. Constraints: 1 <= tiles.length <= 5 * 104 tiles[i].length == 2 1 <= li <= ri <= 109 1 <= carpetLen <= 109 The tiles are non-overlapping.

Topics: Array, Binary Search, Greedy, Sliding Window, Sorting, Prefix Sum

Problem #2: Closest Subsequence Sum

You are given an integer array nums and an integer goal. You want to choose a subsequence of nums such that the sum of its elements is the closest possible to goal. That is, if the sum of the subsequence's elements is sum, then you want to minimize the absolute difference abs(sum - goal). Return the minimum possible value of abs(sum - goal). Note that a subsequence of an array is an array formed by removing some elements (possibly all or none) of the original array. Example 1: Input: nums = [5,-7,3,5], goal = 6 Output: 0 Explanation: Choose the whole array as a subsequence, with a sum of 6. This is equal to the goal, so the absolute difference is 0. Example 2: Input: nums = [7,-9,15,-2], goal = -5 Output: 1 Explanation: Choose the subsequence [7,-9,-2], with a sum of -4. The absolute difference is abs(-4 - (-5)) = abs(1) = 1, which is the minimum. Example 3: Input: nums = [1,2,3], goal = -7 Output: 7 Constraints: 1 <= nums.length <= 40 -107 <= nums[i] <= 107 -109 <= goal <= 109

Topics: Array, Two Pointers, Dynamic Programming, Bit Manipulation, Sorting, Bitmask

Problem #3: Count Zero Request Servers

You are given an integer n denoting the total number of servers and a 2D 0-indexed integer array logs, where logs[i] = [server_id, time] denotes that the server with id server_id received a request at time time. You are also given an integer x and a 0-indexed integer array queries. Return a 0-indexed integer array arr of length queries.length where arr[i] represents the number of servers that did not receive any requests during the time interval [queries[i] - x, queries[i]]. Note that the time intervals are inclusive. Example 1: Input: n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11] Output: [1,2] Explanation: For queries[0]: The servers with ids 1 and 2 get requests in the duration of [5, 10]. Hence, only server 3 gets zero requests. For queries[1]: Only the server with id 2 gets a request in duration of [6,11]. Hence, the servers with ids 1 and 3 are the only servers that do not receive any requests during that time period. Example 2: Input: n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4] Output: [0,1] Explanation: For queries[0]: All servers get at least one request in the duration of [1, 3]. For queries[1]: Only server with id 3 gets no request in the duration [2,4]. Constraints: 1 <= n <= 105 1 <= logs.length <= 105 1 <= queries.length <= 105 logs[i].length == 2 1 <= logs[i][0] <= n 1 <= logs[i][1] <= 106 1 <= x <= 105 x < queries[i] <= 106

Topics: Array, Hash Table, Sliding Window, Sorting