Copy<\/button><\/div>\n\nfrom collections import deque\ndef longest_subarray(nums, k):\n\n max_dq, min_dq = deque(), deque()\n\n left = 0\n\n result = 0\n for right in range(len(nums)):\n\n # maintain decreasing deque for max\n\n while max_dq and nums[max_dq[-1]] <= nums[right]:\n\n max_dq.pop()\n\n max_dq.append(right)\n # maintain increasing deque for min\n\n while min_dq and nums[min_dq[-1]] >= nums[right]:\n\n min_dq.pop()\n\n min_dq.append(right)\n # shrink window if invalid\n\n while nums[max_dq[0]] \u2013 nums[min_dq[0]] > k:\n\n left += 1\n\n if max_dq[0] < left:\n\n max_dq.popleft()\n\n if min_dq[0] < left:\n\n min_dq.popleft()\n result = max(result, right \u2013 left + 1)\n return result\n<\/code><\/pre><\/div>Find the K nearest drivers to a rider's location<\/span>Heap \/ Geospatial<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Compute Euclidean distances from each driver to the rider and maintain a max-heap of size K. For each driver, if the heap has fewer than K entries, push it. If the current distance is less than the max in the heap, pop the max and push the current driver. Return the heap contents when done.<\/p>\n
Reported from multiple phone screens and onsite coding rounds. The real test comes in the follow-up: “How would you handle 500,000 active drivers?” The expected answer introduces geohashing to pre-partition drivers into geographic buckets, so you’re only running the heap comparison within the relevant bucket and its immediate neighbors, not against the full driver set. Candidates who go straight to heap without addressing scale get pushed on it.<\/p>\n
python<\/span>Copy<\/button><\/div>\n\nimport heapq\n\nimport math\ndef k_nearest_drivers(drivers, rider, k):\n\n # drivers: list of (id, x, y), rider: (x, y)\n\n max_heap = [] # (-distance, id)\n for driver_id, dx, dy in drivers:\n\n dist = math.sqrt((dx \u2013 rider[0])**2 + (dy \u2013 rider[1])**2)\n\n heapq.heappush(max_heap, (-dist, driver_id))\n\n if len(max_heap) > k:\n\n heapq.heappop(max_heap)\n return [driver_id for _, driver_id in max_heap]\n<\/code><\/pre><\/div>Implement an LRU cache<\/span>Data Structures<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
HashMap for O(1) key lookups combined with a doubly linked list to track recency. The head holds the most recently used entry; the tail holds the least recently used. On a get, move the accessed node to the head. On a put that exceeds capacity, evict the tail node and delete its key from the map.<\/p>\n
A classic that shows up in Uber phone screens and OAs. Uber’s follow-up here is usually: “How would you scale this to a distributed cache shared across multiple ride-matching servers?” That leads into a discussion of consistent hashing, cache invalidation on price updates, and whether you can tolerate stale driver availability data for a few hundred milliseconds.<\/p>\n
java<\/span>Copy<\/button><\/div>\n\nimport java.util.LinkedHashMap;\n\nimport java.util.Map;\nclass LRUCache extends LinkedHashMap<Integer, Integer> {\n\n private final int capacity;\n public LRUCache(int capacity) {\n\n super(capacity, 0.75f, true);\n\n this.capacity = capacity;\n\n }\n public int get(int key) {\n\n return super.getOrDefault(key, -1);\n\n }\n public void put(int key, int value) {\n\n super.put(key, value);\n\n }\n @Override\n\n protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {\n\n return size() > capacity;\n\n }\n\n}\n<\/code><\/pre><\/div>Find the minimum absolute difference in all K-sized windows of an array<\/span>Sliding Window \/ Heap<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Use a sorted multiset (or a balanced BST equivalent) to maintain the current window of K elements. For each new element added and each element removed as the window slides, update the sorted structure in O(log K) time. The minimum absolute difference in the current window is found by checking adjacent elements in the sorted order. Overall time complexity is O(n log K).<\/p>\n
Reported in an Uber phone screen. The brute force is O(n * K log K), which is too slow for large inputs. The key insight interviewers want to see is that you need a data structure that supports ordered insertion and deletion, not just a simple min or max query.<\/p>\n
<\/div><\/div><\/div>\n
Reconstruct an array from given subsequences (topological sort)<\/span>Graphs<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Build a directed graph where an edge from A to B means A appears before B in at least one of the given subsequences. Run topological sort (Kahn’s algorithm using BFS). If the sorted output matches the original array and the topological order is unique (exactly one node with in-degree zero at each step), return true.<\/p>\n
Reported from a 2024 Uber onsite. The uniqueness check is the gotcha: standard topological sort implementations don’t verify uniqueness, you have to check at each BFS step that exactly one node has zero in-degree to confirm the sequence is determined.<\/p>\n
python<\/span>Copy<\/button><\/div>\n\nfrom collections import defaultdict, deque\ndef can_reconstruct(original, seqs):\n\n graph = defaultdict(set)\n\n in_degree = {x: 0 for x in original}\n for seq in seqs:\n\n for i in range(len(seq) \u2013 1):\n\n u, v = seq[i], seq[i+1]\n\n if v not in graph[u]:\n\n graph[u].add(v)\n\n in_degree[v] = in_degree.get(v, 0) + 1\n queue = deque([n for n in in_degree if in_degree[n] == 0])\n\n idx = 0\n while queue:\n\n if len(queue) > 1:\n\n return False # not unique\n\n node = queue.popleft()\n\n if idx >= len(original) or node != original[idx]:\n\n return False\n\n idx += 1\n\n for neighbor in graph[node]:\n\n in_degree[neighbor] -= 1\n\n if in_degree[neighbor] == 0:\n\n queue.append(neighbor)\n return idx == len(original)\n<\/code><\/pre><\/div>Find the largest square sub-grid where all border cells are 1s<\/span>Dynamic Programming<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Precompute prefix sums for horizontal and vertical runs of consecutive 1s. For each cell (i, j), you know the maximum rightward and downward streak of 1s starting from that cell. Then iterate over all possible square sizes k from large to small: check if the top row, bottom row, left column, and right column all have at least k consecutive 1s using the precomputed streaks. First match is the answer.<\/p>\n
Reported in the initial screening round for an L4 backend role in December 2024. The interviewer accepted an O(n^3) solution but asked for the optimization. The key observation is that you don’t need to check all four sides independently once you have the streak arrays; the four corner-based lookups determine validity in O(1) per cell per size.<\/p>\n
<\/div><\/div><\/div>\n
Count the number of islands (connected regions of land) in a 2D grid<\/span>Graphs \/ Grid<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
DFS or BFS from every unvisited land cell, marking every connected land cell you reach as visited so it doesn’t get counted again. Each DFS or BFS call accounts for exactly one island. Time complexity is O(rows x cols) since every cell is visited once.<\/p>\n
A warmup-tier problem at most companies, but Uber’s version usually adds a twist: “now do it for a grid that updates in real time as new zones come online.” That’s Number of Islands II, which needs union-find instead of a fresh DFS pass every time land is added. The union-find follow-up is the actual bar here; the base DFS version is just the entry point.<\/p>\n
<\/div><\/div><\/div>\n
Word Ladder: minimum number of transformations from source to target word<\/span>BFS \/ Graphs<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
BFS where each node is a word and edges connect words that differ by exactly one character. Build adjacency as you go: for each word in the queue, generate all one-character mutations and check if they exist in the dictionary. Track visited words to avoid cycles. The BFS level count when you reach the target is the answer.<\/p>\n
Reported from Uber phone screens multiple times across 2024 to 2025 community threads. The optimization that comes up in follow-ups is bidirectional BFS, starting from both the source and target simultaneously and meeting in the middle, which can dramatically reduce the branching factor in large word dictionaries.<\/p>\n
<\/div><\/div><\/div>\n
Longest increasing path in a matrix<\/span>DFS \/ Memoization<\/span>Medium<\/span><\/span><\/span><\/button>