Uber·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Uber SWE technical phone screen, one meaty algorithmic problem about merging step functions with a divide-and-conquer follow-up. The core question sounds approachable until you actually try to track two pointers and keep the active values straight.

Questions Asked (1)

You're given two step functions, each represented as a sorted list of [timestamp, value] checkpoints. Return the checkpoints of their pointwise sum, with one entry per distinct timestamp across both inputs. No coalescing even if adjacent merged values are equal. Follow-up: extend the solution to k step functions using divide-and-conquer.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Two-pointer merge is the obvious starting point but the tricky part is maintaining the 'current active value' for each function as you advance.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a two-pointer merge to traverse both sorted lists simultaneously, computing the sum of current values at each distinct timestamp. For the follow-up, apply divide-and-conquer: recursively merge pairs of step functions until one remains, leveraging the same two-pointer merge as the base operation.

Pro tip: Clarify upfront that the output should include every distinct timestamp from both inputs, even if the summed value equals the previous one—this shows attention to the 'no coalescing' requirement. For the follow-up, mention that divide-and-conquer reduces the problem to O(N log k) time where N is total checkpoints, and discuss trade-offs with a k-way merge approach.

1. Understand the problem and edge cases

Restate the problem to confirm you understand that each step function is a sorted list of checkpoints, and the output must have one entry per distinct timestamp without coalescing. Ask about edge cases: empty lists, single checkpoint, duplicate timestamps, and negative values.

2. Design the two-pointer merge algorithm

Explain that you will use two pointers, one for each list, to iterate through timestamps in sorted order. At each step, compare the current timestamps, advance the pointer with the smaller timestamp, and compute the sum of the current values from both lists.

3. Handle value propagation and output construction

Maintain the current value from each list as you advance pointers. When timestamps match, sum the values and advance both pointers; otherwise, use the value from the list whose timestamp is smaller and keep the other list's current value. Append the summed value to the result at each distinct timestamp.

4. Extend to k step functions with divide-and-conquer

For k lists, recursively divide the set of lists into two halves, compute the sum for each half, and then merge the two resulting step functions using the two-pointer approach. Continue until one step function remains.

5. Analyze complexity and discuss trade-offs

State that the two-pointer merge runs in O(m+n) time and O(m+n) space for output. For k lists, divide-and-conquer yields O(N log k) time where N is total checkpoints, compared to O(Nk) for naive sequential merging. Discuss trade-offs with a k-way merge using a heap.

Key Points to Mention

Two-pointer technique for merging sorted lists efficiently.
Handling distinct timestamps and value propagation without coalescing.
Divide-and-conquer strategy for k step functions.
Time and space complexity analysis: O(m+n) for two, O(N log k) for k with divide-and-conquer.
Edge cases: empty inputs, single checkpoint, duplicate timestamps, negative values.
Trade-offs between divide-and-conquer and k-way merge (e.g., heap-based) for k lists.

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