Uber Interview Questions

Given a starting currency and amount, and two separate days' worth of currency-conversion rates (each convertible in both directions), find the maximum amount of the initial currency obtainable after converting through day one's rates, holding, then converting back through day two's rates. It tests whether a candidate can model each day's rates as a graph and use DFS to propagate reachable amounts for every currency, then combine the two days' results — day one forward from the initial currency, day two effectively in reverse — to find the best round trip. It's a solid test of graph traversal with multiplicative, rather than additive, edge weights.

A hard graph problem: given bus routes as sets of stops, find the minimum number of buses needed to travel from a source stop to a target stop. It tests whether a candidate can reframe the problem as BFS over buses (not stops) — building a graph where routes are connected if they share a stop — since naive stop-by-stop BFS is far less efficient. It's a strong signal for graph-modeling creativity, since the natural-seeming approach isn't the efficient one.

Given a list of words sorted according to an unknown alphabet's ordering, the task is to reconstruct a valid character ordering: build a directed graph of precedence constraints from adjacent word comparisons, then topologically sort it (Kahn's algorithm or DFS-based), detecting cycles as an invalid/impossible ordering. The task is conceptually similar to inferring a token ordering from partial, pairwise evidence, which is plausibly why it resonates with companies doing tokenizer/vocabulary-adjacent ML work. It's a solid test of translating a word-comparison problem into a graph and correctly handling topological sort edge cases (cycles, ties, unreachable characters).

This is an online version of the classic islands problem: land cells are added one at a time and you must report the island count after each addition, so recomputing a full BFS/DFS every step is too slow. The intended solution is a Union-Find (Disjoint Set Union) structure with path compression and union by rank, merging newly added land with its already-land neighbors. It's a strong signal for whether a candidate recognizes when a dynamic, incremental connectivity problem calls for DSU instead of repeated graph traversal.

This design problem asks for a counter that records hits with timestamps and can report the number of hits in the past 300 seconds. It's typically implemented with a queue (or a fixed-size circular buffer of timestamp/count pairs) that evicts entries falling outside the trailing time window as new hits arrive. It tests whether a candidate can design a data structure for a sliding time window under both single-hit and (in a common follow-up) batched-hit conditions.

A grid graph-traversal problem: count connected components of '1' cells using DFS, BFS, or Union-Find, being careful with boundary checks and marking visited cells so you don't recount. It's one of the most common entry points into grid-based graph problems and is often used as a warm-up before harder multi-source or Union-Find variants. The core signal is whether a candidate can translate a 2D grid into an implicit graph and correctly implement flood-fill without off-by-one or infinite-loop bugs.

The task is to return all elements of a matrix visited in spiral order, typically implemented by maintaining four shrinking boundaries (top, bottom, left, right) and walking each edge in turn before tightening the boundaries inward. It's less about algorithmic complexity and more about careful index management and avoiding off-by-one errors or double-counting the last row/column when the matrix isn't square. It's a common signal for whether a candidate can translate a visual/spatial pattern into precise, boundary-safe loop logic.

A classic backtracking problem: search a 2D letter grid for a given word by trying each cell as a starting point and exploring adjacent cells via DFS, marking cells visited during the current path and unmarking them (backtracking) before trying alternate paths. It tests whether a candidate can correctly manage mutable visited state across a recursive search and prune paths early when a character mismatch occurs. It's a strong signal for general backtracking competence, a technique that generalizes to many other constraint-search problems.

A design problem requiring O(1) get and put operations with least-recently-used eviction, implemented by combining a hash map (for O(1) lookup) with a doubly linked list (for O(1) reordering and eviction from either end). This exact structure underlies real inference key-value caches — it's reportedly one of the most frequently asked design questions at companies building LLM inference systems, since eviction policy for a bounded cache maps directly onto managing GPU memory for attention KV caches. It's a strong test of whether a candidate can compose two data structures to get O(1) across every required operation, not just some of them.

You're given equations like a / b = k and must answer queries of the form c / d using those relationships, including through chains of intermediate variables. It's modeled as a weighted graph (or weighted Union-Find) where an edge a→b has weight k, and each query is answered via a DFS/BFS path search accumulating the product of edge weights along the way. It tests whether a candidate can translate an algebraic relationship into a graph-traversal problem rather than trying to solve it purely with equations.

This is a weighted random sampling design problem: given an array of weights, repeatedly return an index with probability proportional to its weight. The standard solution builds a prefix-sum array and then binary searches a random value into that prefix-sum range, so it tests whether a candidate can connect probability weighting to cumulative sums and then apply binary search correctly on that derived array. It's a common signal for services that need weighted load distribution or randomized selection, such as routing or recommendation systems.

A streaming-median design problem solved with two heaps: a max-heap holding the smaller half of seen values and a min-heap holding the larger half, rebalanced after each insertion so the median is always derivable from the heaps' tops in O(log n) per insert and O(1) per query. It tests whether a candidate can design a data structure that supports an evolving statistic under continuous insertion, a pattern that generalizes to other streaming-aggregate problems. Correctly maintaining the size invariant between the two heaps is the main source of bugs.

Given a collection of intervals, merge all overlapping ones. The standard approach sorts intervals by start time, then does a single linear pass, extending the current merged interval whenever the next one overlaps and starting a new one otherwise. It's a foundational interval problem that shows up across many companies because interval merging underlies a large family of harder scheduling and calendar-style questions.

This is a classic interval-scheduling problem: given a list of meeting time intervals, find the minimum number of rooms required so no two overlapping meetings share a room. The standard approach sorts start and end times separately (or uses a min-heap of end times) and sweeps through them, tracking how many meetings are simultaneously active to determine the peak concurrent overlap, which equals the answer. It's a strong, well-known signal for interval-scheduling reasoning, and its overlap-counting technique generalizes directly to resource-allocation and scheduling problems in real systems.

A sliding-window problem where the window's validity condition — the difference between the max and min values inside it must stay within a given limit — is maintained using two monotonic deques (one tracking max candidates, one tracking min candidates) as the window's right edge expands and its left edge contracts. Getting O(n) performance requires recognizing that a naive per-window max/min scan is too slow, making this a solid test of combining the sliding-window pattern with monotonic-deque bookkeeping rather than either technique in isolation.

A classic topological-sort problem: given courses and prerequisite pairs, return a valid ordering (or detect that no valid ordering exists due to a cycle). It tests whether a candidate can build an adjacency list, track in-degrees, and run Kahn's BFS algorithm (or DFS with visited/in-progress marking) to order and cycle-detect simultaneously. Its broad company reach reflects how often real systems need this exact shape of problem — resolving build or package dependency order, or task scheduling graphs — making it a reliable signal for graph traversal fluency.

Given a list of strings, group the ones that are anagrams of each other. The typical solution hashes each string to a canonical key (either its sorted characters or a fixed-length character-count signature) and groups strings sharing a key in a hash map. It's a straightforward but reliable test of whether a candidate reaches for the right canonicalization strategy and understands the tradeoffs between sorting-based and counting-based keys.

Find the k-th smallest value in a binary search tree, which follows directly from the property that an in-order traversal of a BST visits nodes in sorted order — so the k-th element visited during an in-order walk is the answer. The straightforward solution uses O(h) space for the traversal stack/recursion; Uber reportedly pushes senior (L5+) candidates on a follow-up requiring O(1) auxiliary space via Morris traversal, which threads temporary links through the tree's null pointers instead of using a call stack, then undoes them as it goes. That follow-up is a meaningfully harder test of whether a candidate actually understands Morris traversal versus having only practiced the standard recursive or iterative in-order pattern.

A design problem: encode a binary tree into a string and reconstruct an identical tree from that string, typically via a preorder traversal with explicit null markers, or a BFS-based level encoding. The candidate must design a format that's unambiguous enough for deserialization to rebuild structure without extra information. Interview relevance frequently maps to data persistence — serializing structured data for storage or transmission and reliably reconstructing it — which is why it shows up across companies handling tree-like or hierarchical data on disk or over the wire.

This design problem asks for a system that, as a user types characters one at a time, returns the top 3 historical sentences matching the current prefix, ranked by frequency (and lexicographically to break ties). It's commonly implemented with a trie augmented with sentence frequency counts at terminal nodes, combined with a traversal or small heap to extract the top matches at each keystroke. It's a good test of whether a candidate can combine a trie for prefix matching with a ranking mechanism, and manage incremental state across a sequence of calls.