Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Uber SWE interview with a tricky optimization problem that looks like brute force bait but has a clean ternary search solution once you see the unimodal structure. Nothing behavioral, just the one algorithmic problem.

Questions Asked (1)

You're climbing N floors of a building. You take an elevator for the first x floors (each floor costs t1 time) and stairs for the remaining N-x floors (each stair floor costs e2 energy and takes ceil(c / current_energy) time, with a fixed energy budget E that can't go negative). Find the value of x that minimizes the maximum of the two phase times.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to just iterate over all x and pick the minimum, which works but the O(N^2) felt gross and I said so out loud which I think was fine.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and define the objective function f(x) = max(t1 * x, sum_{i=x+1}^{N} ceil(c / e_i)) where e_i is the energy at step i. Then use binary search on x to find the minimum f(x), leveraging monotonicity of the two phase times.

Pro tip: Mention that the energy budget E imposes a feasibility constraint: the stairs phase must not deplete energy below zero, so x must be at least the minimum floors needed to keep energy non-negative. This shows you consider practical limits.

1. Clarify the problem

Ask questions to confirm details: Is t1 constant per floor? How does energy decrease per stair floor? Is c constant? Is E the initial energy? What is current_energy? Ensure you understand the time formula for stairs.

2. Define the objective function

Express the total time for elevator phase as T1(x) = t1 * x. For stairs, simulate energy decrement per floor and compute T2(x) = sum of ceil(c / current_energy) for floors x+1 to N. The objective is f(x) = max(T1(x), T2(x)).

3. Analyze monotonicity and feasibility

Note that T1(x) increases with x, while T2(x) decreases as x increases (fewer stairs). Thus f(x) is unimodal (decreases then increases). Also, x must be ≥ x_min where x_min is the smallest x such that energy never goes negative during stairs.

4. Choose an algorithm

Use binary search on x in [x_min, N] to find the minimum f(x). For each mid, compute T1 and T2 efficiently (precompute prefix sums of stair times if energy is constant, else simulate). Compare f(mid) with f(mid+1) to decide direction.

5. Discuss complexity and edge cases

Time complexity: O(N log N) if simulating stairs each time, or O(N) with precomputation. Handle edge cases: x=0 (all stairs), x=N (all elevator), energy exactly zero, and large N.

Key Points to Mention

Binary search on the number of elevator floors x due to unimodal objective function.
Monotonicity: elevator time increases with x, stairs time decreases with x.
Energy constraint: stairs phase must not deplete energy below zero, so x must be at least a minimum feasible value.
Time complexity: O(N log N) with simulation, or O(N) with precomputation of stair times.
Edge cases: x=0, x=N, and cases where energy is insufficient for any stairs.
Trade-off: minimizing the maximum of two phases balances elevator and stair times.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.