Uber's DSA rounds lean on dynamic programming, graphs, and shortest-path patterns — and interviewers regularly change the constraints mid-round with a live follow-up, so being able to adapt an already-working solution matters as much as solving it the first time. The three problems below are real, recently reported (2025) Uber questions with full solutions.
Given a set of keys with associated access weights, build a binary search tree over them that minimizes the total weighted search cost — a variation of the classic Optimal Binary Search Tree problem, with an extra constraint layered on top by the interviewer.
Input: keys = [10, 20, 30], weights = [3, 2, 5]
Output: 17
Put 30 (weight 5) at the root, 10 as its left child and 20 as 10's right child: cost = 5×1 + 3×2 + 2×3 = 17, the minimum total weighted depth-cost. The exact extra constraint the interviewer adds on top of the base OBST formulation varies by report; clarify it explicitly before coding.
Two players alternately pick a value from either end of a row of numbers, each trying to maximize their own total under optimal play from both sides — a variant of the classic 'Optimal Strategy for a Game' problem, with the interviewer changing how corner values are chosen.
Input: a = [5, 3, 7, 10]
Output: 15
The first player can guarantee 15 by picking 10, then 7, under optimal play from both sides.
Given a weighted graph and several designated source nodes, find the shortest distance from the nearest source to every other node, with a follow-up on optimizing the approach for very large graphs.
Input: n = 5, edges (undirected, [u, v, w]) = [[0,1,4],[1,2,1],[2,3,2],[3,4,7]], sources = [0, 3]
Output: [0,3,2,0,7]
Each node's answer is its distance to whichever source reaches it first: node 1 is 4 away from source 0 but only 3 away from source 3 (3 → 2 → 1), so its answer is 3; node 4 is only reachable via source 3 at distance 7.