Uber SWE OA Interview Experience (2026) - Prime Jumps & Rerooting DP, Offer

My approach:

1. Sieve of Eratosthenes up to `n-1`, then filter primes to those ending in digit 3.
2. `dp[i]` = max score achievable landing on cell `i`, with `dp[0] = cell[0]`.
3. Transition: `dp[i] = cell[i] + max(dp[i-1], max over valid p of dp[i-p])`.

With n <= 10^4 the inner loop is fine. The count of primes ending in 3 below 10000 is only 300, so total work is roughly 3 10^6 operations, comfortably under the time limit. Do not forget to handle the case where dp[i-1] itself is unreachable — use a negative-infinity sentinel and gate the transition on the incoming state being reachable.

Practice it: [[problem/872?company=12|Prime Jumps]]

Problem 2: Minimum Reversal

Problem: You have an undirected tree given as n-1 edges, but each edge has a stored direction. You must pick a root and flip edges so that every edge points away from the root (from parent to child). Return, for every possible root choice, the minimum number of flips required, then return the overall minimum.

Example: n = 4 , edges 1→4 , 2→4 , 3→4 . Rooting at 2 gives the minimum count of 2 flips.

This is a textbook rerooting problem. If you have never seen rerooting before, Problem 2 is where the OA eats you. I had seen the pattern three times before, so the 45-minute window was enough.

Phase 1: build the adjacency list storing the original direction of each edge. I encoded it as adj[u] = [(v, 0)] if the original edge was u → v , and adj[v] = [(u, 1)] for the reverse view, where the second tuple element is the flip cost from u to v .

Phase 2: pick any node (I used node 0), DFS to compute cost[0] = total flips needed when 0 is the root. While DFSing, also compute subtree cost[v] for every v .

Phase 3: second DFS, this time rerooting. When you move the root from u to adjacent v : - If the original edge was u → v (cost 0 from the u-rooted perspective), moving root to v flips that one edge, so cost[v] = cost[u] + 1 . - If the original edge was v → u (cost 1 from u-rooted), moving root to v unflips it, so cost[v] = cost[u] - 1 .

The final answer is min(cost) across all nodes. I used an explicit stack instead of recursion because Python recursion at n = 10^5 will hit the default limit; a RecursionError during the 89th minute will ruin you. The interviewer on a follow-up round asked about exactly this choice, so it was worth flagging.

Practice it: [[problem/873?company=12|Minimum Edge Reversals to Root a Tree]]

What I Learned from the OA

Two Hard DPs in 90 minutes is a very different test from Meta's two Mediums or Amazon's OA2 simulation. The questions reward pattern recognition over raw coding speed. If you have not seen rerooting before, you will spend most of Problem 2 rederiving the incremental update from scratch, and that is the gap between offer and reject.

Phone Screen (45 min)

One coding problem. I got a variant of Top K Frequent Elements with a twist: ties broken by lexicographic order of the element's string representation, and a streaming constraint where you only see elements one at a time. I solved it with a min-heap of size K plus a secondary comparator. The interviewer asked how I would handle a heavy hitter appearing after the heap is full. The answer is to compare incoming count against the heap min, then swap. Clean 25 minute solve, and then we talked about how it would change if K were dynamic, which turns it into a more interesting data structure problem that I sketched but did not code.

Onsite Preview

Four rounds: two coding, one system design (Design Uber Ride Matching), and a behavioral. The design round was exactly what you would expect, and I leaned on Haversine + geohashing + the dispatcher actor model. The coding rounds were easier than the OA, mostly medium stack and hashmap problems. The behavioral was light compared to Meta or Amazon.

Result

L4 offer. Compensation landed at the expected levels.fyi band for the role. Recruiter was fast, about 4 days from final round to verbal.

Tips

1. Drill rerooting specifically before Uber's OA. Uber has asked some version of "count edge flips to root a tree" multiple times this year. If you only know standard tree DP, you will get stuck computing the cost at a single root and run out of time. Practice the incremental update explicitly.
2. Sieve + digit filter is a repeat Uber trick. The prime-jumps variant has been reused with different digit filters and different jump rules. Precompute the primes once outside the DP loop, never inside.
3. Use iterative DFS in Python for HackerRank. Uber's HackerRank OA does not raise the recursion limit, and Problem 2 constraints are past the default 1000. A `RecursionError` during the 89th minute will ruin you.
4. Budget 40 and 45, not 45 and 45. Problem 1 is the closer shave for most people, so get it to a working brute force fast and come back to optimize. Do not start Problem 2 with less than 40 minutes on the clock.
5. Do not chase the optimal on both problems. Partial credit on a working O(n^2) rerooting beats a half-written O(n) one. HackerRank scores every visible test case.
6. After the OA, email the recruiter with your thinking. I wrote a short note explaining the approach for Problem 2 in case the judge was stricter than expected. It probably did not change anything but it felt like insurance.