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

Intermediate

Apr 2026

Summary

Uber SWE online assessment, one coding problem that's basically a twist on a well-known LeetCode problem. The extra output requirements tripped me up more than the core algorithm did.

Questions Asked (1)

Given an array of prices, for each item find the first later item whose price is less than or equal to it and apply that as a discount. Return the total sum of all final prices, plus the 0-based indices (ascending, space-separated) of items that received no discount and sold at full price.

Algorithms & Data Structures

Author's notes

The base problem is LC 1475 so I felt fine at first, but the OA version asks for two things: the total and the list of undiscounted indices.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a monotonic stack to efficiently find the next smaller or equal element for each price in O(n) time. Compute the discounted price for each item, sum them, and collect indices of items with no discount. Return the total sum and the space-separated indices.

Pro tip: Clarify edge cases like empty array or all increasing prices, and mention that the stack approach avoids O(n^2) brute force, which is crucial for large inputs.

1. Understand the problem

Restate the problem: for each item, find the first later item with price <= current; if found, discount = that price, else no discount. Need total sum of final prices and indices of items with no discount.

2. Choose efficient algorithm

Use a monotonic stack to find the next smaller or equal element for each price in a single pass. This gives O(n) time and O(n) space.

3. Implement stack logic

Iterate through prices, maintaining a stack of indices with decreasing prices. For each price, pop indices where price <= stack top's price, assign discount, and push current index.

4. Compute results

After processing, sum discounted prices (or original if no discount) and collect indices of items with no discount. Format indices as space-separated string.

5. Test and verify

Test with edge cases: empty array, single item, strictly increasing, strictly decreasing, duplicates. Ensure time and space complexity are optimal.

Key Points to Mention

Monotonic stack for next smaller or equal element
Time complexity O(n) and space complexity O(n)
Handling duplicates correctly (<= condition)
Edge cases: empty array, all increasing, all decreasing
Return format: total sum and space-separated indices
Avoiding brute force O(n^2) solution

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