Introduction

In this blog post, we'll share the most commonly asked coding interview questions at Uber. 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: Bus Routes

You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever. For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever. You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only. Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible. Example 1: Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6 Output: 2 Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6. Example 2: Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12 Output: -1 Constraints: 1 <= routes.length <= 500. 1 <= routes[i].length <= 105 All the values of routes[i] are unique. sum(routes[i].length) <= 105 0 <= routes[i][j] < 106 0 <= source, target < 106

Topics: Array, Hash Table, Breadth-First Search

Problem #2: Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit. Example 1: Input: nums = [8,2,4,7], limit = 4 Output: 2 Explanation: All subarrays are: [8] with maximum absolute diff |8-8| = 0 <= 4. [8,2] with maximum absolute diff |8-2| = 6 > 4. [8,2,4] with maximum absolute diff |8-2| = 6 > 4. [8,2,4,7] with maximum absolute diff |8-2| = 6 > 4. [2] with maximum absolute diff |2-2| = 0 <= 4. [2,4] with maximum absolute diff |2-4| = 2 <= 4. [2,4,7] with maximum absolute diff |2-7| = 5 > 4. [4] with maximum absolute diff |4-4| = 0 <= 4. [4,7] with maximum absolute diff |4-7| = 3 <= 4. [7] with maximum absolute diff |7-7| = 0 <= 4. Therefore, the size of the longest subarray is 2. Example 2: Input: nums = [10,1,2,4,7,2], limit = 5 Output: 4 Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5. Example 3: Input: nums = [4,2,2,2,4,4,2,2], limit = 0 Output: 3 Constraints: 1 <= nums.length <= 105 1 <= nums[i] <= 109 0 <= limit <= 109

Topics: Array, Queue, Sliding Window, Heap (Priority Queue), Ordered Set, Monotonic Queue

Problem #3: Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 Example 2: Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3 Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] is '0' or '1'.

Topics: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix

Problem #5: Block Placement Queries

There exists an infinite number line, with its origin at 0 and extending towards the positive x-axis. You are given a 2D array queries, which contains two types of queries: For a query of type 1, queries[i] = [1, x]. Build an obstacle at distance x from the origin. It is guaranteed that there is no obstacle at distance x when the query is asked. For a query of type 2, queries[i] = [2, x, sz]. Check if it is possible to place a block of size sz anywhere in the range [0, x] on the line, such that the block entirely lies in the range [0, x]. A block cannot be placed if it intersects with any obstacle, but it may touch it. Note that you do not actually place the block. Queries are separate. Return a boolean array results, where results[i] is true if you can place the block specified in the ith query of type 2, and false otherwise. Example 1: Input: queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]] Output: [false,true,true] Explanation: For query 0, place an obstacle at x = 2. A block of size at most 2 can be placed before x = 3. Example 2: Input: queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]] Output: [true,true,false] Explanation: Place an obstacle at x = 7 for query 0. A block of size at most 7 can be placed before x = 7. Place an obstacle at x = 2 for query 2. Now, a block of size at most 5 can be placed before x = 7, and a block of size at most 2 before x = 2. Constraints: 1 <= queries.length <= 15 104 2 <= queries[i].length <= 3 1 <= queries[i][0] <= 2 1 <= x, sz <= min(5 104, 3 * queries.length) The input is generated such that for queries of type 1, no obstacle exists at distance x when the query is asked. The input is generated such that there is at least one query of type 2.

Topics: Array, Binary Search, Binary Indexed Tree, Segment Tree

Problem #6: Text Justification

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters. Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right. For the last line of text, it should be left-justified, and no extra space is inserted between words. Note: A word is defined as a character sequence consisting of non-space characters only. Each word's length is guaranteed to be greater than 0 and not exceed maxWidth. The input array words contains at least one word. Example 1: Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 Output: [ "This is an", "example of text", "justification. " ] Example 2: Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16 Output: [ "What must be", "acknowledgment ", "shall be " ] Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified. Note that the second line is also left-justified because it contains only one word. Example 3: Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20 Output: [ "Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do " ] Constraints: 1 <= words.length <= 300 1 <= words[i].length <= 20 words[i] consists of only English letters and symbols. 1 <= maxWidth <= 100 words[i].length <= maxWidth

Topics: Array, String, Simulation

Problem #7: Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree. Example 1: Input: root = [3,1,4,null,2], k = 1 Output: 1 Example 2: Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3 Constraints: The number of nodes in the tree is n. 1 <= k <= n <= 104 0 <= Node.val <= 104 Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Problem #8: Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. Example 1: Input: nums = [-4,-1,0,3,10] Output: [0,1,9,16,100] Explanation: After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100]. Example 2: Input: nums = [-7,-3,2,3,11] Output: [4,9,9,49,121] Constraints: 1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums is sorted in non-decreasing order. Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

Topics: Array, Two Pointers, Sorting

Problem #9: Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation. Example 1: Input: nums = [1,2,3,4] Output: [24,12,8,6] Example 2: Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0] Constraints: 2 <= nums.length <= 105 -30 <= nums[i] <= 30 The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer. Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Topics: Array, Prefix Sum