Uber·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate

Jun 2026

Summary

Uber SWE online assessment, one algorithmic problem centered on maximizing pipeline throughput under a budget constraint. Pretty clean problem once you see the binary search angle, but the edge cases in the predicate function are where people trip up.

Questions Asked (1)

You have a pipeline of services running in series. Each service has an initial throughput and a cost to scale it up. Given a total budget, find the maximum pipeline throughput you can achieve, where pipeline throughput is the minimum across all services.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I went greedy first, kept throwing budget at whatever the current bottleneck was.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that the problem is to maximize the minimum throughput across services given a budget for scaling. Use binary search on the target throughput T, and for each T, check if the total cost to bring all services up to at least T is within budget. The answer is the largest feasible T.

Pro tip: Clarify that scaling costs are linear and that we can scale each service independently; then emphasize that binary search is optimal because the feasibility predicate is monotonic. Also mention that if costs are not linear, the approach may need adjustment.

1. Understand the problem

Restate the problem: we have n services in series, each with initial throughput t_i and cost per unit increase c_i. Given budget B, maximize min_i (t_i + x_i) where x_i >= 0 and sum(c_i * x_i) <= B.

2. Define feasibility check

For a candidate throughput T, compute the required scaling for each service: if t_i < T, need x_i = T - t_i, costing c_i*(T - t_i). Sum these costs and check if <= B.

3. Apply binary search

Binary search on T between min(t_i) and min(t_i) + B / min(c_i) (or a safe upper bound). For each mid, run the feasibility check. If feasible, search higher; else search lower.

4. Handle edge cases and complexity

Consider cases where budget is insufficient to scale any service, or where scaling one service is much cheaper. Analyze time complexity: O(n log(range)) and space O(1).

5. Discuss trade-offs and alternatives

Mention that if costs are not linear, we might need a different approach (e.g., greedy or DP). Also discuss whether we can scale down services (not needed here) and the impact of discrete scaling.

Key Points to Mention

Binary search on the answer (throughput) with a monotonic feasibility check.
Feasibility check: sum of costs to raise each service to target T must be <= budget.
Time complexity: O(n log(max_throughput)) and space O(1).
Assumption of linear scaling costs; if not, problem becomes more complex.
Edge cases: budget too small to increase any service, or all services already above target.
Potential optimization: precompute prefix sums or sort services by cost for faster checks, but not necessary for binary search.

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