Uber Data Structures and Algorithms Interview Questions &amp; Answers

Show answer

def permutations(nums): result, path = [], [] used = [False] * len(nums) def backtrack(): if len(path) == len(nums): result.append(path[:]) return for i, x in enumerate(nums): if used[i]: continue used[i] = True path.append(x) backtrack() path.pop() # undo the choice used[i] = False backtrack() return result # n! permutations: O(n * n!) time

Implement fast exponentiation to compute x to the power n in O(log n).

Uber Complexity Analysis and RecursionMedium

Show answer

def power(x, n): if n < 0: x, n = 1 / x, -n result = 1 while n > 0: if n & 1: # odd bit set: multiply current base in result *= x x *= x # square the base n >>= 1 # move to next bit return result # power(2, 10) == 1024; use % mod after each multiply for modular power

Implement Dijkstra's algorithm with a priority queue.

Show answer

import heapq def dijkstra(graph, src): # graph: {node: [(neighbour, weight), ...]} dist = {src: 0} heap = [(0, src)] while heap: d, u = heapq.heappop(heap) if d > dist.get(u, float('inf')): continue # stale entry for v, w in graph.get(u, []): nd = d + w if nd < dist.get(v, float('inf')): dist[v] = nd heapq.heappush(heap, (nd, v)) return dist # O((V + E) log V); weights must be non-negative

A recursive DFS in Python crashes with RecursionError on a deep input. How do you fix it?

Uber Complexity Analysis and RecursionMedium

Show answer

CPython limits recursion depth to about 1000 by default. Raising the limit with sys.setrecursionlimit works for moderate depth but can crash the interpreter on very deep inputs because the C stack is limited. The reliable fix is to rewrite the DFS iteratively with an explicit stack, pushing nodes and processing them in a loop. In Java the same issue appears as StackOverflowError and has the same solution.

An application needs sorted data with frequent inserts, deletes and range queries such as all orders between two timestamps. Which structure fits?

Show answer

A balanced BST, such as Java TreeMap or a sorted container in Python, gives O(log n) insert and delete and O(log n plus k) range queries using floor, ceiling or subMap operations. A sorted array has fast range queries but O(n) inserts, and a hash map cannot do ranges at all. If the data lives in a database, a B-tree index on the timestamp column solves the same problem.

What is quickselect and when is it better than sorting?

Uber Sorting, Searching and BacktrackingHard

Show answer

Quickselect finds the kth smallest element by partitioning like quicksort but recursing only into the side that contains position k. On average it does about n plus n over 2 plus n over 4 work, which is O(n), compared with O(n log n) for sorting. The worst case is O(n squared), reduced by random pivots or median of medians for guaranteed O(n). C++ nth_element uses this idea.

You must build autocomplete for a search box over one million product names. Which data structure would you use?

Show answer

I would use a trie where each node stores, besides children, the top few most popular completions under that prefix. Then typing a prefix walks L nodes and returns precomputed suggestions instantly, without exploring the whole subtree. Memory can be reduced with a compressed radix trie. For typo tolerance or ranking by many signals, a search engine with prefix indexes is more practical at large scale.

Compute the edit distance between two words.

Uber Dynamic ProgrammingHard

Show answer

def edit_distance(a, b): m, n = len(a), len(b) prev = list(range(n + 1)) # distances from empty prefix of a for i in range(1, m + 1): cur = [i] + [0] * n for j in range(1, n + 1): if a[i - 1] == b[j - 1]: cur[j] = prev[j - 1] else: cur[j] = 1 + min(prev[j], # delete cur[j - 1], # insert prev[j - 1]) # replace prev = cur return prev[n] # edit_distance('horse', 'ros') -> 3; O(m * n) time, O(n) space

Rotate an array to the right by k steps in place.

Show answer

def rotate(nums, k): n = len(nums) k %= n def reverse(l, r): while l < r: nums[l], nums[r] = nums[r], nums[l] l += 1 r -= 1 reverse(0, n - 1) # reverse all reverse(0, k - 1) # reverse first k reverse(k, n - 1) # reverse the rest # [1,2,3,4,5,6,7], k=3 -> [5,6,7,1,2,3,4]; O(n) time, O(1) space

Design a rate limiter that allows at most 100 requests per user in any rolling 60-second window.

Uber Linked Lists, Stacks and QueuesHard

Show answer

For each user keep a deque of request timestamps. On a request, pop timestamps older than now minus 60 seconds from the front, then allow the request only if fewer than 100 remain, pushing the new timestamp at the back. This sliding window log is exact but uses memory per request. At scale I would use a sliding window counter or token bucket stored in Redis with atomic operations to save memory and work across servers.

How would you generate friend suggestions as friends of friends in a social network?

Show answer

Run a BFS limited to depth 2 from the user. For every friend, look at their friends, skip the user and existing friends, and count how many mutual friends each candidate has using a hash map. Rank candidates by mutual friend count and other signals. For users with thousands of friends this gets expensive, so production systems precompute suggestions offline in batch jobs and cache them.

What are the trade-offs between recursion and iteration?

Uber Complexity Analysis and RecursionMedium

Show answer

Recursion expresses tree traversal, divide and conquer and backtracking naturally and with less code. However each call uses stack memory and has call overhead, and deep recursion can overflow the stack, about 1000 frames by default in Python. Iteration with an explicit stack or loop uses heap memory and is usually faster. Many interviewers accept recursive solutions but may ask for an iterative version for very deep inputs.

Packages with given weights must be shipped in order within D days. How do you find the minimum ship capacity?

Show answer

The capacity lies between the heaviest package and the total weight, and if a capacity works, any larger one also works, so binary search the answer. For a candidate capacity, greedily load packages day by day, starting a new day when the next package does not fit, and count days. If the days are within D, try smaller; otherwise try larger. Time is O(n log of total weight).

Implement 0/1 knapsack using a one-dimensional DP array.

Uber Dynamic ProgrammingMedium

Show answer

def knapsack(weights, values, capacity): dp = [0] * (capacity + 1) # dp[w] = best value with capacity w for wt, val in zip(weights, values): for w in range(capacity, wt - 1, -1): # go downwards: each item once dp[w] = max(dp[w], dp[w - wt] + val) return dp[capacity] # knapsack([1, 3, 4], [15, 20, 30], 4) -> 35 # O(n * W) time, O(W) space

What is the load factor of a hash table and why does it matter?

Show answer

Load factor is the number of stored entries divided by the number of buckets. As it rises, collisions increase and operations slow down. Java HashMap resizes when the load factor passes 0.75, doubling buckets and rehashing every entry, which costs O(n) occasionally but keeps operations O(1) amortised. If you know the final size, set the initial capacity to avoid repeated resizing in performance-sensitive code.

What is a bipartite graph and how do you check for one?

Show answer

A graph is bipartite if its vertices can be split into two groups so every edge connects vertices from different groups, which is equivalent to having no odd-length cycle. To check, colour vertices with BFS or DFS: give the start vertex colour 0, its neighbours colour 1 and so on; if any edge connects two vertices of the same colour, it is not bipartite. Run it on each component, O(V plus E).

How do the KMP and Rabin-Karp string matching algorithms work?

Uber Arrays, Strings and HashingHard

Show answer

Naive matching is O(n times m). KMP precomputes a longest prefix-suffix array for the pattern, so after a mismatch it shifts the pattern without re-reading text characters, giving O(n plus m) worst case. Rabin-Karp computes a rolling hash of each text window and compares characters only when hashes match, averaging O(n plus m) and extending well to multiple patterns, but collisions can make the worst case O(n times m).

Why are you looking for a change from your current job?

Show answer

Situation: in my current role I have learned a lot maintaining internal tools for two years. Task: I want to grow into harder engineering problems. Action: I have been strengthening my data structures, system design and backend skills through projects and by taking ownership of performance work in my team. Result: I am now ready for a role with larger scale and more technical depth, which is why this position appeals to me.

What is a greedy algorithm and when does it give the optimal answer?

Uber Heaps, Priority Queues and GreedyMedium

Show answer

A greedy algorithm builds a solution step by step, always taking the choice that looks best right now and never revisiting it. It is optimal only when the problem has the greedy choice property, meaning a locally best choice is part of some optimal solution, and optimal substructure. Examples where greedy works are activity selection, Huffman coding, Dijkstra and Kruskal. For many problems, such as 0/1 knapsack, it fails.

Detect whether a linked list has a cycle and return the node where the cycle begins.

Uber Linked Lists, Stacks and QueuesMedium

Show answer

def detect_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: # cycle found slow = head while slow is not fast: # move both one step slow = slow.next fast = fast.next return slow # start of the cycle return None # O(n) time, O(1) space

Design a simple scheduler that gives each job a fixed time slice in turn.

Uber Linked Lists, Stacks and QueuesMedium

Show answer

Round-robin scheduling fits a queue. Put all jobs in a FIFO queue. Repeatedly dequeue a job, run it for one time slice, and if it is not finished, enqueue it at the back with its remaining time. Each step is O(1). For priorities, keep one queue per priority level or use a priority queue. A circular buffer works well if the number of jobs is bounded, avoiding allocations.

Find the lowest common ancestor of two nodes in a binary tree.

Show answer

def lca(root, p, q): if root is None or root is p or root is q: return root left = lca(root.left, p, q) right = lca(root.right, p, q) if left and right: # p and q are on different sides return root return left or right # O(n) time, O(h) space; assumes both nodes exist in the tree

You must merge two sorted arrays where the first array has enough empty space at the end for the second. How would you do it in place?

Show answer

Merging from the front would overwrite unread elements, so merge from the back. Use three pointers: the last real element of the first array, the last element of the second, and the last slot of the first array. Repeatedly place the larger of the two candidates at the write position and move pointers left. When the second array is exhausted, the rest is already in place. This takes O(m plus n) time and O(1) space.

A build system hangs because some services depend on each other in a loop. How would you detect and report the cycle?

Show answer

Model services as a directed graph and run DFS with three colours. When DFS reaches a node that is still on the current stack, it has found a back edge, and walking the parent pointers from the current node back to that node gives the exact cycle to report, such as A to B to C to A. Running this check in CI before every build prevents the problem, and Kahn's algorithm can list all nodes involved.

Find the first and last position of a target in a sorted array.

Show answer

from bisect import bisect_left, bisect_right def search_range(nums, target): lo = bisect_left(nums, target) # first index >= target if lo == len(nums) or nums[lo] != target: return [-1, -1] hi = bisect_right(nums, target) - 1 # last index <= target return [lo, hi] # [5,7,7,8,8,10], 8 -> [3, 4]; two binary searches: O(log n)

Tell me about a time you made slow code significantly faster at work.

Uber Sorting, Searching and BacktrackingHard

Show answer

Situation: a search API for our catalogue took two seconds because it filtered and sorted all items on every request. Task: bring p95 latency under 200 milliseconds. Action: I profiled it, pre-sorted items by the main key at load time, replaced linear filtering with binary search on sorted ranges and cached popular queries, validating results against the old code. Result: p95 dropped to 120 milliseconds and server costs fell by about a third.

Your knapsack DP has n equal to 100 items but capacity up to 10 to the power 9, so the table does not fit in memory. What do you do?

Uber Dynamic ProgrammingHard

Show answer

A table indexed by capacity is impossible, so I change the state. If item values are small, use dp[v] as the minimum weight needed to achieve value v, then pick the largest v whose weight fits the capacity; that is O(n times total value). If n is about 40, meet in the middle: enumerate subsets of each half, sort one side and binary search. Otherwise approximation or branch and bound are options.

Explain the sliding window technique with fixed and variable windows.

Show answer

A sliding window keeps a contiguous range and updates its result incrementally instead of recomputing. A fixed window of size k, such as the maximum sum of k consecutive elements, adds the new element and removes the old one each step in O(n). A variable window grows the right end and shrinks the left end while a condition is violated, as in the longest substring without repeating characters. Both turn O(n squared) into O(n).

Write a function to validate a binary search tree.