Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Uber coding screen, one algorithmic problem the whole time. Pretty focused session, no fluff.

Questions Asked (1)

You're given an array of item prices. For each item, find the first subsequent item whose price is less than or equal to the current one and apply that as a discount. Return the final prices after discounts. Solve it in O(n).

Algorithms & Data Structures

Author's notes

The brute force clicks immediately but they want O(n) so you know a stack is coming.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as a classic 'next smaller or equal element' problem and use a monotonic increasing stack to find the next smaller-or-equal price for each item in a single pass. Iterate through the array, maintaining the stack of indices with non-decreasing prices; when the current price is less than or equal to the price at the stack top, pop and apply the discount. This yields O(n) time and O(n) space.

Pro tip: Clarify the discount rule upfront: 'less than or equal to' means equal prices also trigger a discount, so the stack must pop on <=, not just <. Also mention that you can mutate the input array in place to save space, but confirm with the interviewer if that's acceptable.

1. Clarify the problem and constraints

Restate the problem: for each item, find the first subsequent item with price <= current, subtract it as discount. Confirm edge cases: empty array, single item, all increasing, all equal, and that discounts are applied only once per item.

2. Identify the pattern and choose the data structure

Recognize this as a 'next smaller or equal element' problem. Explain that a monotonic stack (increasing order of prices) efficiently tracks unresolved items waiting for a smaller-or-equal price.

3. Walk through the algorithm

Iterate through the array with index i. While the stack is non-empty and prices[i] <= prices[stack.top], pop the top index j and set prices[j] -= prices[i]. Then push i onto the stack. After the loop, any remaining indices have no discount.

4. Analyze complexity and edge cases

State that each index is pushed and popped at most once, giving O(n) time and O(n) space. Discuss edge cases: empty array returns empty, single item returns unchanged, and equal prices trigger discounts.

5. Test with examples and consider optimizations

Run through a small example like [8,4,6,2,3] to verify. Mention that the stack can be implemented with a simple array for performance, and that in-place modification is possible if allowed.

Key Points to Mention

Monotonic stack (increasing) to track indices of items awaiting a smaller-or-equal price.
Condition uses <= (not <) because equal prices also qualify as discounts.
Time complexity O(n) because each element is pushed and popped at most once.
Space complexity O(n) for the stack, but can be O(1) extra if mutating input is allowed.
Edge cases: empty array, single element, strictly increasing, strictly decreasing, all equal.
Alternative approaches like brute force O(n^2) are less efficient; monotonic stack is optimal.

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