Uber Previous Year Coding Questions
Uber hires software engineers who can think at the intersection of algorithms and real-world systems. The interview process tests deep fundamentals in data structures, graph algorithms, dynamic programming, and the ability to design scalable distributed systems. Problems are often framed around Uber's actual domain such as driver matching, route optimization, and surge pricing, though standard LeetCode-style problems appear in every round.
Hiring Process
Step 1: Resume Shortlisting Uber screens for relevant experience and a strong competitive programming or system design background. Open source contributions and previous product company experience improve shortlisting chances significantly.
Step 2: Online Assessment Conducted on HackerRank or CodeSignal. The assessment lasts 65 to 90 minutes with three questions ranging from medium to hard difficulty. Problems span sliding window, dynamic programming, and graph traversal. There is no partial scoring so submitting clean correct code matters more than partial attempts.
Step 3: Technical Phone Screen 1 A 45 to 60 minute round with one coding question and a discussion around your solution's complexity and edge cases. The interviewer typically follows up with variations to test how well you understand the underlying algorithm.
Step 4: Technical Phone Screen 2 Some candidates receive a second phone screen depending on the role and team. This round focuses on a medium to hard problem and may include early system design discussion for senior roles.
Step 5: Onsite Virtual Interviews Three to five back-to-back rounds covering coding, system design, and a behavioral interview. Coding rounds use a collaborative editor and interviewers expect you to think aloud, handle edge cases, and discuss trade-offs before coding.
Step 6: Bar Raiser and Offer A final behavioral or leadership round assesses culture fit and problem-solving mindset. Uber looks for candidates who demonstrate ownership, clarity of thought, and the ability to operate in ambiguity.
Tips: Prioritize graph algorithms including BFS, DFS, Dijkstra, and topological sort as they appear in almost every Uber loop. Practice designing systems like a ride-matching service or a real-time pricing engine. Always discuss time and space complexity before you start writing code.
Preparation Resources
Part 1 — OA Questions
1. Longest Bounded Subarray Medium
Given an integer array nums and an integer limit, return the length of the longest contiguous subarray such that the absolute difference between any two elements within that subarray is less than or equal to limit.
Input: nums = [8,2,4,7], limit = 4
Output: 2
Explanation: Subarray [2,4] has absolute difference 2 which is <= 4.
Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4
Approach: Use two monotonic deques, one tracking the current window maximum and one tracking the minimum. Expand the right pointer each step. When the difference between the front of the max deque and front of the min deque exceeds limit, advance the left pointer and remove stale entries from both deques. Track the maximum window size seen.
Complexity: Time O(n) · Space O(n)
Follow-up: How would your approach change if elements arrive in a stream and you need to report the answer after each new element?
2. Count Prefix Pairs Medium
Given an array of strings words, count the number of index pairs (i, j) where i is less than j and either words[i] is a prefix of words[j] or words[j] is a prefix of words[i].
Input: words = ["a","aba","ababa","aa"]
Output: 4
Explanation: Pairs (0,1), (0,2), (1,2), (0,3) satisfy the prefix condition.
Input: words = ["pa","papa","ma","mama"]
Output: 2
Approach: For the brute force pass iterate over all pairs and use the startsWith check in O(L) per pair where L is the average string length. For an optimized solution insert all words into a trie, then for each word query both its prefixes and check if any word in the trie matches.
Complexity: Time O(n^2 * L) brute force · O(n * L) with trie · Space O(n * L)
Follow-up: How would you handle a case insensitive prefix check efficiently?
3. Predict the Winner Medium
Given an integer array nums, two players take turns picking either the first or last element. Player 1 picks first. Both players play optimally. Return true if Player 1 can win or tie, otherwise return false.
Input: nums = [1,5,2]
Output: false
Explanation: Player 1 picks 1 or 2. Player 2 will always get 5. Player 1 cannot win.
Input: nums = [1,5,233,7]
Output: true
Approach: Define dp[i][j] as the maximum score advantage the current player can achieve over their opponent on the subarray from i to j. The recurrence is dp[i][j] = max(nums[i] minus dp[i+1][j], nums[j] minus dp[i][j-1]). Player 1 wins if dp[0][n-1] is greater than or equal to 0.
Complexity: Time O(n^2) · Space O(n^2), reducible to O(n) with rolling array
Follow-up: Extend to k players where each picks optimally to maximize their own score.
4. Jump Game II Medium
Given an integer array nums where nums[i] represents the maximum jump length from index i, return the minimum number of jumps needed to reach the last index. You may assume reaching the last index is always possible.
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: Jump from index 0 to 1, then from 1 to 4.
Input: nums = [2,3,0,1,4]
Output: 2
Approach: Track the current jump boundary and the farthest reachable index. When you reach the boundary, increment the jump count and update the boundary to the farthest index seen in the current window. Stop as soon as the boundary reaches or passes the last index.
Complexity: Time O(n) · Space O(1)
Follow-up: What if each jump has a cost proportional to the jump distance? Find the minimum cost path.
5. Group Anagrams Medium
Given an array of strings strs, group all anagrams together and return the groups in any order.
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Input: strs = [""]
Output: [[""]]
Approach: For each string compute a canonical key. The simplest key is the sorted characters of the string. Use a hash map from key to list of strings. All strings mapping to the same sorted key belong to the same anagram group. Return all values of the map.
Complexity: Time O(n * k log k) where k is the max string length · Space O(n * k)
Follow-up: Can you achieve O(n * k) time using a character frequency array as the key instead of sorting?
6. Minimum Operations to Make Array Equal Medium
You have an array of length n where arr[i] equals 1 plus 2 times i. In one operation you can choose two indices i and j and increment arr[i] by 1 while decrementing arr[j] by 1. Return the minimum number of operations to make all elements equal.
Input: n = 3
Output: 2
Input: n = 6
Output: 9
Approach: The target value for all elements is n itself (the mean of the arithmetic sequence). The total operations needed equals the sum of deficits for elements below the mean, which by symmetry equals n squared divided by 4. For odd n the answer is (n squared minus 1) divided by 4.
Complexity: Time O(1) · Space O(1)
Follow-up: What if the increment and decrement values are not equal but are given as separate parameters?
Part 2 — Phone Screen Questions
7. LRU Cache Medium
Design a data structure that follows the Least Recently Used cache eviction policy. Implement the LRUCache class with get(key) returning the value if it exists and put(key, value) inserting or updating the key. If the cache reaches its capacity, evict the least recently used key before inserting a new one. Both operations must run in O(1) average time.
Input: capacity = 2
put(1, 1), put(2, 2), get(1) -> 1
put(3, 3), get(2) -> -1 (evicted)
put(4, 4), get(1) -> -1, get(3) -> 3, get(4) -> 4
Approach: Combine a hash map for O(1) key lookup with a doubly linked list to maintain access order. The most recently used node stays at the head and the least recently used stays at the tail. On get, move the accessed node to the head. On put, add to the head and if capacity is exceeded remove the tail node and delete its key from the map.
Complexity: Time O(1) per operation · Space O(capacity)
Follow-up: Implement an LFU cache where eviction is based on access frequency rather than recency.
8. Number of Islands Medium
Given a 2D grid of characters where '1' represents land and '0' represents water, return the number of islands. An island is surrounded by water and formed by connecting adjacent land cells horizontally or vertically.
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Approach: Traverse every cell. When you encounter a '1', increment the island count and run BFS or DFS to mark all reachable land cells as visited (set to '0' to avoid revisiting). The total number of BFS or DFS initiations equals the island count.
Complexity: Time O(m * n) · Space O(min(m, n)) for BFS queue
Follow-up: How would this change if diagonal connections also count as part of the same island?
9. Sliding Window Maximum Hard
Given an integer array nums and an integer k, return an array of the maximum values of each sliding window of size k as it moves from left to right.
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Input: nums = [1], k = 1
Output: [1]
Approach: Use a monotonic deque storing indices in decreasing order of their values. For each new element, pop all indices from the back whose values are smaller than the current element since they can never be the maximum in any future window. Remove the front index if it is outside the current window. The front of the deque always holds the index of the current window maximum.
Complexity: Time O(n) · Space O(k)
Follow-up: How would you find both the minimum and maximum of each window in a single pass?
10. Top K Frequent Elements Medium
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. The algorithm must run in better than O(n log n) time.
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Input: nums = [1], k = 1
Output: [1]
Approach: Count frequencies with a hash map. Then use a min-heap of size k. Iterate over frequency entries and push each into the heap. When the heap exceeds size k, pop the minimum. The remaining k entries are the answer. Alternatively use bucket sort where bucket index equals frequency for O(n) time.
Complexity: Time O(n log k) heap · O(n) bucket sort · Space O(n)
Follow-up: Design a streaming version that can answer top-k queries as elements are inserted one at a time.
11. Course Schedule Medium
There are numCourses courses labeled from 0 to numCourses minus 1. Given prerequisites pairs where each pair [a, b] means you must take course b before course a, determine if it is possible to finish all courses.
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false (cycle exists)
Approach: Model as a directed graph. Use Kahn's algorithm (BFS topological sort) with an in-degree array. Start from all nodes with in-degree 0. Process nodes one by one, decrementing neighbors' in-degrees. If all nodes are processed the graph is acyclic and all courses can be finished.
Complexity: Time O(V + E) · Space O(V + E)
Follow-up: Return the actual order in which courses should be taken if such an order exists.
12. Design Hit Counter Medium
Design a hit counter that counts the number of hits received in the past 5 minutes (300 seconds). Implement hit(timestamp) which records a hit and getHits(timestamp) which returns the total hits in the last 300 seconds. Timestamps are in seconds and calls to hit are non-decreasing.
hit(1), hit(2), hit(3), getHits(4) -> 3
hit(300), getHits(300) -> 4
getHits(301) -> 3 (hit at timestamp 1 is now outside the window)
Approach: Use two arrays of size 300, one for timestamps and one for hit counts at each second slot (circular buffer). On hit, write the count to the bucket at timestamp mod 300. On getHits, sum all buckets whose stored timestamp is within the last 300 seconds.
Complexity: Time O(1) per hit · O(300) per getHits · Space O(1)
Follow-up: How would you handle concurrent hits at the same timestamp from multiple threads?
13. Find Median from Data Stream Hard
Design a data structure that supports addNum(num) to add a number from the data stream and findMedian() to return the current median. The median is the middle value in sorted order, or the mean of the two middle values for even-length streams.
addNum(1), addNum(2), findMedian() -> 1.5
addNum(3), findMedian() -> 2.0
Approach: Maintain two heaps. A max-heap for the lower half and a min-heap for the upper half. After each insertion rebalance so the heaps differ in size by at most one. The median is the top of the larger heap, or the average of both tops if sizes are equal.
Complexity: Time O(log n) per add · O(1) per query · Space O(n)
Follow-up: If 99% of numbers are in the range 0 to 100, can you exploit this to improve performance?
Part 3 — Onsite Questions
14. Two Sum Easy
Given an integer array nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution and you may not use the same element twice.
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Input: nums = [3,2,4], target = 6
Output: [1,2]
Approach: Use a hash map to store each number and its index as you iterate. For each number check if the complement (target minus current) already exists in the map. If it does, return the stored index and current index.
Complexity: Time O(n) · Space O(n)
Follow-up: What if the input is sorted and you need O(1) extra space?
15. Valid Parentheses Easy
Given a string s containing only the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if every opening bracket has a corresponding closing bracket in the correct order.
Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
Approach: Use a stack. Push every opening bracket onto the stack. For every closing bracket check if the top of the stack is the matching opener. If not, or if the stack is empty, return false. After processing the string the stack must be empty for the string to be valid.
Complexity: Time O(n) · Space O(n)
Follow-up: How would you handle a string where wildcard '*' can represent any single bracket or an empty string?
16. Merge Intervals Medium
Given an array of intervals where each interval is [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the input intervals.
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Approach: Sort intervals by start time. Initialize the result with the first interval. For each subsequent interval, if its start is less than or equal to the current result interval's end, merge by extending the end to the maximum of both ends. Otherwise add the interval as a new entry.
Complexity: Time O(n log n) · Space O(n)
Follow-up: Given a new interval, insert it into a sorted list of non-overlapping intervals maintaining the sorted merged state.
17. 3Sum Medium
Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i, j, and k are distinct indices and the three values sum to zero.
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Input: nums = [0,0,0]
Output: [[0,0,0]]
Approach: Sort the array. Fix one element with an outer loop and use two pointers for the remaining pair. If the sum is too large move the right pointer left. If too small move the left pointer right. Skip duplicate values at all three positions to avoid repeated triplets in the result.
Complexity: Time O(n^2) · Space O(1) excluding output
Follow-up: How would you modify this to find all quadruplets summing to a given target?
18. Container With Most Water Medium
Given n non-negative integers representing vertical lines where the width of each line is 1, find two lines that together with the x-axis form a container that holds the most water.
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Input: height = [1,1]
Output: 1
Approach: Use two pointers starting at the left and right ends. Compute the water as the product of width and the shorter height. Move the pointer pointing to the shorter line inward because moving the taller line can only decrease or maintain the width while gaining no height advantage.
Complexity: Time O(n) · Space O(1)
Follow-up: What if the container must use exactly three lines to form a 3D basin?
19. Longest Substring Without Repeating Characters Medium
Given a string s, find the length of the longest substring without repeating characters.
Input: s = "abcabcbb"
Output: 3 (substring "abc")
Input: s = "pwwkew"
Output: 3 (substring "wke")
Approach: Use a sliding window with a hash map tracking the last seen index of each character. When a repeating character is found, advance the left boundary to one position after its last occurrence. The window length at each step is a candidate answer.
Complexity: Time O(n) · Space O(min(n, 128))
Follow-up: What is the longest substring where each character appears at most k times?
20. Minimum Window Substring Hard
Given two strings s and t, return the minimum window substring of s that contains every character in t including duplicates. If no such substring exists return an empty string.
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Input: s = "a", t = "aa"
Output: ""
Approach: Use a sliding window. Count the required frequencies of all characters in t. Expand the right pointer until all required characters are satisfied. Then shrink the left pointer to minimize the window while maintaining satisfaction. Track the minimum valid window seen.
Complexity: Time O(|s| + |t|) · Space O(|s| + |t|)
Follow-up: What if you need to find the minimum window containing all words from a list rather than individual characters?
21. Trapping Rain Water Hard
Given n non-negative integers representing an elevation map where each bar has width 1, compute how much water it can trap after raining.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Input: height = [4,2,0,3,2,5]
Output: 9
Approach: Use two pointers at both ends. Maintain the running maximum from the left and right. At each step, process the side with the smaller maximum. The water trapped at that position is the running maximum minus the current height. This works because the water level is determined by the smaller of the two side maximums.
Complexity: Time O(n) · Space O(1)
Follow-up: Extend to a 2D height map and compute the total trapped water volume.
22. Next Permutation Medium
Given an array of integers nums, rearrange its elements into the next lexicographically greater permutation. If no such arrangement exists (the array is in descending order) rearrange to the lowest possible order (ascending). The replacement must be done in place.
Input: nums = [1,2,3]
Output: [1,3,2]
Input: nums = [3,2,1]
Output: [1,2,3]
Approach: Scan from right to find the first index i where nums[i] is less than nums[i+1]. Then find the smallest number to the right of i that is greater than nums[i], call it j. Swap i and j. Finally reverse the suffix starting at i+1 to get the smallest arrangement for that suffix.
Complexity: Time O(n) · Space O(1)
Follow-up: Given a number n, generate all permutations in lexicographic order without storing them all simultaneously.
23. Binary Tree Level Order Traversal Medium
Given the root of a binary tree, return the level order traversal of its node values as a list of lists, where each inner list contains all values at that depth.
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Approach: Use a queue initialized with the root. At each step record the current queue size to know how many nodes belong to the current level. Process exactly that many nodes, adding their children to the queue, and collect values into the current level's list.
Complexity: Time O(n) · Space O(n)
Follow-up: Return the zigzag level order traversal where odd levels are collected right to left.
24. Lowest Common Ancestor of a Binary Tree Medium
Given a binary tree and two nodes p and q, return their lowest common ancestor. The lowest common ancestor is the deepest node that has both p and q as descendants (a node can be a descendant of itself).
Input: root = [3,5,1,6,2,0,8], p = 5, q = 1
Output: 3
Input: root = [3,5,1,6,2,0,8], p = 5, q = 4
Output: 5
Approach: Use postorder DFS. If the current node is null or equals p or q, return it. Recursively search both subtrees. If both return a non-null value the current node is the LCA. If only one side returns non-null, propagate that result upward.
Complexity: Time O(n) · Space O(h) where h is tree height
Follow-up: How would this change if the tree has parent pointers and you cannot traverse the whole tree?
25. Validate Binary Search Tree Medium
Given the root of a binary tree, determine if it is a valid binary search tree. A valid BST requires that for every node the left subtree contains only values strictly less than the node and the right subtree contains only values strictly greater than the node, recursively.
Input: root = [2,1,3]
Output: true
Input: root = [5,1,4,null,null,3,6]
Output: false (4 is in right subtree of 5 but 4 < 5)
Approach: Pass down valid range bounds (min, max) for each node during DFS. The root starts with range (negative infinity, positive infinity). For a left child the upper bound tightens to the parent value. For a right child the lower bound tightens. Return false if the current node violates its bounds.
Complexity: Time O(n) · Space O(h)
Follow-up: Find the kth smallest element in a BST in O(h + k) time.
26. Clone Graph Medium
Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains a value and a list of its neighbors.
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]] (deep copy)
Approach: Use BFS or DFS with a hash map from original node to cloned node. When visiting a node for the first time create its clone and add to the map. For each neighbor if a clone already exists link to it, otherwise create and enqueue. The hash map also serves as the visited set.
Complexity: Time O(V + E) · Space O(V)
Follow-up: What if the graph can have cycles of length 1 (self loops)?
27. Word Ladder Hard
Given a begin word, end word, and a word list, return the length of the shortest transformation sequence from begin word to end word. Each step may change exactly one letter and every intermediate word must be in the word list. Return 0 if no such sequence exists.
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5 (hit -> hot -> dot -> dog -> cog)
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Approach: Use BFS from the begin word. At each step generate all words differing by one character and check if they exist in the word set. Add unvisited ones to the queue and remove them from the set to prevent revisiting. Return the level at which the end word is reached.
Complexity: Time O(M^2 * N) where M is word length and N is list size · Space O(M^2 * N)
Follow-up: Use bidirectional BFS starting from both ends to reduce the search space significantly.
28. Network Delay Time Medium
You are given a network of n nodes and a list of travel time edges [u, v, w] where w is the travel time from u to v. Starting from node k, return the minimum time for all nodes to receive the signal. If it is impossible, return -1. This directly models Uber's driver dispatch and ETA calculation systems.
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Approach: Run Dijkstra from source node k using a min-heap of (distance, node) pairs. Relax edges greedily taking the closest unvisited node first. After processing all reachable nodes return the maximum distance in the dist array. If any node is still at infinity return -1.
Complexity: Time O((V + E) log V) · Space O(V + E)
Follow-up: What if edge weights can be negative? Describe how Bellman-Ford would differ.
29. Rotten Oranges Medium
Given a grid where 0 is empty, 1 is a fresh orange, and 2 is a rotten orange, every minute all fresh oranges adjacent to a rotten orange become rotten. Return the minimum number of minutes until no fresh orange remains, or -1 if it is impossible.
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Approach: Use multi-source BFS. Enqueue all initially rotten oranges and count fresh oranges. Process level by level, converting adjacent fresh oranges to rotten and decrementing the fresh count. The number of BFS levels is the answer. If fresh count is still positive after BFS return -1.
Complexity: Time O(m * n) · Space O(m * n)
Follow-up: What if a fresh orange can be isolated by empty cells and you need to determine the minimum number of oranges to initially rot to make all others rot?
30. Alien Dictionary Hard
Given a list of words sorted lexicographically in an alien language, derive the ordering of letters in that language. If no valid ordering exists return an empty string. If multiple orderings are valid return any one.
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Input: words = ["z","x","z"]
Output: "" (cycle detected)
Approach: Compare adjacent word pairs to extract ordering constraints as directed edges. Build a graph of letter dependencies. Run topological sort using Kahn's algorithm. If the sort processes all unique characters return the order, otherwise a cycle exists and the input is invalid.
Complexity: Time O(C) where C is total character count · Space O(1) since alphabet is bounded
Follow-up: What if you also need to verify that the given word list is consistent with the derived ordering?
31. Serialize and Deserialize Binary Tree Hard
Design an algorithm to serialize a binary tree to a string and deserialize it back. Your serialization format is up to you as long as the tree can be reconstructed exactly.
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5] (after serialize then deserialize)
Approach: Use preorder traversal for serialization. Represent null pointers with a sentinel like "N". During deserialization consume values from a queue (split by delimiter). If the current value is the sentinel return null, otherwise create a node and recursively build left then right subtrees.
Complexity: Time O(n) · Space O(n)
Follow-up: How would you serialize a general n-ary tree with a variable number of children?
32. Binary Tree Maximum Path Sum Hard
Given the root of a binary tree, return the maximum sum of any path. A path is a sequence of nodes where each pair of adjacent nodes has an edge and no node appears more than once. The path does not need to pass through the root.
Input: root = [-10,9,20,null,null,15,7]
Output: 42 (path 15 -> 20 -> 7)
Input: root = [1,2,3]
Output: 6
Approach: Use postorder DFS. At each node compute the maximum gain from the left and right subtrees (clamped to 0 to ignore negative paths). Update the global maximum with the sum of left gain plus the node value plus right gain (this path uses both children). Return the node value plus the larger of the two gains for paths going through a parent.
Complexity: Time O(n) · Space O(h)
Follow-up: What if the path must start and end at leaves of the tree?
33. Climbing Stairs Easy
You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Input: n = 2
Output: 2 (1+1, 2)
Input: n = 3
Output: 3 (1+1+1, 1+2, 2+1)
Approach: The number of ways to reach step n equals the sum of ways to reach step n-1 and step n-2. This is the Fibonacci sequence. Use two variables instead of an array to compute iteratively with constant space.
Complexity: Time O(n) · Space O(1)
Follow-up: What if you can climb 1, 2, or 3 steps at a time?
34. Coin Change Medium
Given an array of coin denominations and a target amount, return the minimum number of coins needed to make up that amount. If the amount cannot be made up by any combination of coins, return -1.
Input: coins = [1,5,11], amount = 15
Output: 3 (5+5+5)
Input: coins = [2], amount = 3
Output: -1
Approach: Build a bottom-up DP array of size amount plus 1 initialized to infinity. Set dp[0] to 0. For each amount from 1 to target, try every coin and update dp[amount] as the minimum of its current value and dp[amount minus coin] plus 1. Return dp[amount] or -1 if it remains infinity.
Complexity: Time O(amount * n) · Space O(amount)
Follow-up: Return one valid combination of coins achieving the minimum, not just the count.
35. Longest Common Subsequence Medium
Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously.
Input: text1 = "abcde", text2 = "ace"
Output: 3 (subsequence "ace")
Input: text1 = "abc", text2 = "abc"
Output: 3
Approach: Build a 2D DP table where dp[i][j] represents the LCS of text1[0..i-1] and text2[0..j-1]. If the current characters match, dp[i][j] equals dp[i-1][j-1] plus 1. Otherwise it equals the maximum of dp[i-1][j] and dp[i][j-1]. The answer is dp[m][n].
Complexity: Time O(m * n) · Space O(m * n), reducible to O(min(m, n))
Follow-up: Print the actual LCS string by backtracking through the DP table.
36. Word Break Medium
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Approach: Use a boolean DP array of size n plus 1 where dp[i] is true if s[0..i-1] can be segmented. Initialize dp[0] to true. For each position i, check every position j less than i. If dp[j] is true and s[j..i-1] is in the dictionary, set dp[i] to true.
Complexity: Time O(n^2 * m) where m is average word length · Space O(n + W)
Follow-up: Return all possible segmentation sentences instead of just true or false.
37. Partition Equal Subset Sum Medium
Given an integer array nums, return true if you can partition it into two subsets with equal sum.
Input: nums = [1,5,11,5]
Output: true (subsets [1,5,5] and [11])
Input: nums = [1,2,3,5]
Output: false
Approach: This reduces to a subset sum problem targeting half the total. If the total is odd return false immediately. Use a boolean DP set of achievable sums. For each number update the set in reverse order (like 0-1 knapsack). Return true if the target sum appears in the set.
Complexity: Time O(n * sum) · Space O(sum)
Follow-up: Find the partition that minimizes the absolute difference between the two subset sums.
38. Decode Ways Medium
A message encoded as digits maps 'A' to 1, 'B' to 2, through 'Z' to 26. Given a string s of digits, return the number of ways to decode it.
Input: s = "12"
Output: 2 (decoded as "AB" or "L")
Input: s = "226"
Output: 3 ("BZ", "VF", "BBF")
Approach: Use bottom-up DP where dp[i] represents the number of ways to decode the first i characters. At each position check if the single digit is valid (1 to 9) and if the two-digit combination is valid (10 to 26). Add contributions from both cases.
Complexity: Time O(n) · Space O(n), reducible to O(1)
Follow-up: What if the encoding could also use a wildcard '*' representing any digit from 1 to 9?
39. Edit Distance Hard
Given two strings word1 and word2, return the minimum number of operations (insert, delete, replace) to convert word1 to word2.
Input: word1 = "horse", word2 = "ros"
Output: 3 (horse -> rorse -> rose -> ros)
Input: word1 = "intention", word2 = "execution"
Output: 5
Approach: Build a 2D DP table where dp[i][j] is the edit distance between the first i characters of word1 and first j characters of word2. If characters match, dp[i][j] equals dp[i-1][j-1]. Otherwise it equals 1 plus the minimum of insert (dp[i][j-1]), delete (dp[i-1][j]), and replace (dp[i-1][j-1]).
Complexity: Time O(m * n) · Space O(m * n), reducible to O(min(m, n))
Follow-up: What if certain edit operations have different costs?
40. Task Scheduler Medium
Given a list of tasks identified by uppercase letters and a cooldown interval n, each same task must be separated by at least n intervals. Return the least number of intervals to execute all tasks. This mirrors Uber's driver availability scheduling systems.
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8 (A B _ A B _ A B)
Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Approach: Find the most frequent task count f. Schedule f minus 1 full cycles each of size n plus 1, followed by a final partial cycle. The formula is (f - 1) (n + 1) + count of tasks with frequency equal to f. The answer is the maximum of this formula and the total number of tasks.
*Complexity: Time O(n) · Space O(1) since alphabet is bounded
Follow-up: Return one valid schedule achieving the minimum time rather than just the length.
41. Implement Trie Medium
Implement a trie (prefix tree) with insert(word), search(word) returning true if the exact word is stored, and startsWith(prefix) returning true if any stored word begins with the prefix.
insert("apple"), search("apple") -> true
search("app") -> false, startsWith("app") -> true
insert("app"), search("app") -> true
Approach: Each trie node holds an array of 26 child pointers and an isEnd boolean. Insert walks the tree creating nodes as needed and marks the final node. Search and startsWith both walk the tree following characters. Search additionally checks the isEnd flag.
Complexity: Time O(L) per operation where L is word length · Space O(L * n) for n words
Follow-up: Design a trie that supports wildcard '.' matching any single character in search.
42. Word Search II Hard
Given an m by n board of characters and a list of words, return all words that can be found by sequentially adjacent cells. Each cell may not be used more than once per word.
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
Approach: Insert all words into a trie. Then for each cell in the board run DFS while following the trie. When a trie node has isEnd set to true, add the found word to results and clear the flag to avoid duplicates. Mark cells as visited during DFS and restore them on backtrack.
Complexity: Time O(m * n * 4 * 3^(L-1)) · Space O(W * L) where W is word count
Follow-up: How would you prune branches of the trie during search to speed up subsequent queries?
43. Reorganize String Medium
Given a string s, rearrange its characters so that no two adjacent characters are the same. Return any valid rearrangement, or an empty string if it is not possible.
Input: s = "aab"
Output: "aba"
Input: s = "aaab"
Output: ""
Approach: Count frequencies. If any character's frequency exceeds (n plus 1) divided by 2 return empty. Use a max-heap. At each step pop the two most frequent characters, append them to the result, decrement their counts, and push back if still positive. This guarantees no two adjacent characters are the same.
Complexity: Time O(n log k) where k is unique characters · Space O(k)
Follow-up: What is the minimum number of additional characters needed to make an impossible rearrangement possible?
44. Basic Calculator II Medium
Given a string expression containing non-negative integers and the operators plus, minus, multiply, and divide (integer division truncating toward zero), evaluate and return the result. There are no parentheses.
Input: s = "3+2*2"
Output: 7
Input: s = " 3/2 "
Output: 1
Approach: Use a stack. Track the previous operator. When encountering plus or minus push the signed number. When encountering multiply or divide pop the top, apply the operation with the current number, and push the result. Sum the stack at the end. This correctly handles operator precedence without building an AST.
Complexity: Time O(n) · Space O(n)
Follow-up: Extend to handle parentheses for full expression evaluation.
45. Design Twitter Medium
Design a simplified Twitter with postTweet(userId, tweetId), getNewsFeed(userId) returning the 10 most recent tweet IDs in the user's news feed, follow(followerId, followeeId), and unfollow(followerId, followeeId).
postTweet(1, 5), getNewsFeed(1) -> [5]
follow(1, 2), postTweet(2, 6), getNewsFeed(1) -> [6, 5]
unfollow(1, 2), getNewsFeed(1) -> [5]
Approach: Store tweets per user as a list with a global timestamp. Store follow relationships in a hash set per user. For getNewsFeed merge tweet lists from the user and all followees using a max-heap on timestamps. Extract the 10 most recent.
Complexity: Time O(F log F) per feed query where F is number of followees · Space O(U + T)
Follow-up: Design the same system at Uber scale where millions of driver events need to be broadcast to millions of nearby riders in real time.
46. Kth Smallest Element in BST Medium
Given the root of a binary search tree and an integer k, return the kth smallest value among all nodes.
Input: root = [3,1,4,null,2], k = 1
Output: 1
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Approach: Perform an iterative inorder traversal using a stack. Inorder traversal of a BST visits nodes in ascending order. Decrement k at each visited node. When k reaches 0 the current node holds the answer. This avoids building the entire sorted list.
Complexity: Time O(h + k) · Space O(h)
Follow-up: If the BST is frequently modified by insertions and deletions, how would you augment it to answer kth-smallest queries in O(log n) time?
47. Largest Rectangle in Histogram Hard
Given an array of integers heights representing the histogram bar heights, return the area of the largest rectangle that can be formed.
Input: heights = [2,1,5,6,2,3]
Output: 10 (rectangle of height 5 width 2)
Input: heights = [2,4]
Output: 4
Approach: Use a monotonic stack storing indices of bars in increasing height order. When a shorter bar is encountered, pop taller bars and compute the area using the popped bar's height and the width determined by the current index and the new stack top. Append a zero sentinel to flush all remaining bars.
Complexity: Time O(n) · Space O(n)
Follow-up: Given a binary matrix, find the largest rectangle containing only 1s by treating each row as a histogram.
48. Palindrome Partitioning Medium
Given a string s, partition it such that every substring of the partition is a palindrome. Return all possible palindrome partitioning.
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Input: s = "a"
Output: [["a"]]
Approach: Use backtracking. At each position try every possible substring starting from the current index. If the substring is a palindrome add it to the current partition and recurse on the remainder. Use a DP table to precompute which substrings are palindromes to avoid redundant checks.
Complexity: Time O(n * 2^n) · Space O(n^2)
Follow-up: Instead of all partitions, return just the minimum number of cuts to partition s into all palindromes.
49. Number of Connected Components in Undirected Graph Medium
Given n nodes labeled 0 to n minus 1 and a list of undirected edges, return the number of connected components in the graph. At Uber, this models grouping of independent driver or rider clusters in a city zone.
Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
Approach: Use Union-Find with path compression and union by rank. Initialize each node as its own component. For each edge union the two nodes. After processing all edges count the number of distinct roots. This is more efficient than BFS or DFS for repeated connectivity queries.
Complexity: Time O(E * alpha(N)) near constant · Space O(N)
Follow-up: How would you handle dynamic edge additions and answer connectivity queries in real time?
50. Burst Balloons Hard
Given n balloons with values in array nums, bursting balloon i gives coins equal to nums[i-1] times nums[i] times nums[i+1]. After bursting, adjacent balloons become neighbors. Return the maximum coins you can collect by bursting all balloons. Treat nums[-1] and nums[n] as 1.
Input: nums = [3,1,5,8]
Output: 167 (burst order 1,5,3,8 gives 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167)
Input: nums = [1,5]
Output: 10
Approach: Think in reverse. Instead of which balloon to burst first, think of which balloon to burst last in each subproblem range. Define dp[i][j] as the max coins from balloons strictly between i and j. For each possible last balloon k in that range, dp[i][j] equals dp[i][k] plus dp[k][j] plus nums[i] times nums[k] times nums[j].
Complexity: Time O(n^3) · Space O(n^2)
Follow-up: What is the minimum number of balloons to burst to make all remaining balloon values equal?
Preparation Tips
Join the Let's Code Telegram group for Uber interview discussions, recent OA questions shared by candidates, and off-campus referral opportunities.