Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Uber SWE interview with a scheduling/simulation problem that looked straightforward until the complexity requirement hit. The two-heap constraint was the whole point and I almost missed it.

Questions Asked (1)

You have a fixed pool of servers and a stream of requests each with an arrival time and a duration. Assign each request to the lowest-id available server, drop it if none are free, and return the total number of successfully assigned requests. Your solution must run in O((R + S) log S) time using two heaps.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was just to scan all servers on each request, which obviously blows up.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem constraints and edge cases, then outline a solution using two heaps: one min-heap for available server IDs and one min-heap for busy servers keyed by release time. Process requests in arrival order, releasing servers whose end time is <= current arrival, assign to the smallest available server, and count successful assignments.

Pro tip: Mention that if requests are not already sorted by arrival time, you must sort them first, which adds O(R log R) time; however, the problem likely assumes sorted input. Also, note that using a min-heap for available servers ensures the lowest-id server is chosen in O(log S) time.

1. Clarify requirements and assumptions

Confirm that requests are given in arrival order, that server IDs are 1 to S, and that a server becomes free exactly at the end time (so a request arriving at that time can use it). Ask about tie-breaking if multiple servers are free.

2. Design data structures

Use a min-heap for available server IDs (initialized with all servers) and a min-heap for busy servers keyed by release time (end time). Each entry in the busy heap stores (end_time, server_id).

3. Process each request

For each request (arrival, duration): first, release all servers from the busy heap whose end_time <= arrival, pushing their IDs back into the available heap. Then, if the available heap is non-empty, pop the smallest server ID, assign the request, and push (arrival + duration, server_id) into the busy heap. Increment the success count.

4. Handle edge cases and complexity

If no server is available, drop the request. After processing all requests, return the success count. Analyze time complexity: each request causes at most one push and one pop from each heap, leading to O((R + S) log S) time and O(S) space.

5. Test and validate

Walk through a small example to verify correctness, such as 2 servers and requests [(0,3), (1,2), (2,1)]. Check that servers are released properly and the lowest-id server is always chosen.

Key Points to Mention

Use two heaps: a min-heap for available server IDs and a min-heap for busy servers keyed by release time.
Process requests in arrival order, releasing servers before each assignment.
Always assign to the lowest-id available server by popping from the available heap.
Time complexity: O((R + S) log S) because each server is pushed/popped at most once and each request causes O(log S) heap operations.
Space complexity: O(S) for the heaps.
Edge cases: no available servers, simultaneous release and arrival, and multiple requests with the same arrival time.

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