Compute final prices with next smaller discount
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Quick Answer: This question evaluates array-processing and algorithmic problem-solving skills, focusing on reasoning about subsequent elements to compute element-wise discounts under input constraints.
Constraints
- 1 <= len(prices) <= 200000
- 1 <= prices[i] <= 1000000000
Examples
Input: ([8, 4, 6, 2, 3],)
Expected Output: [4, 2, 4, 2, 3]
Explanation: Item 0 gets discount 4, item 1 gets discount 2, item 2 gets discount 2, and the last two items have no later smaller-or-equal discount.
Input: ([1],)
Expected Output: [1]
Explanation: A single item has no later item to provide a discount.
Input: ([1, 2, 3, 4],)
Expected Output: [1, 2, 3, 4]
Explanation: Prices are strictly increasing, so no item has a later price less than or equal to itself.
Input: ([10, 7, 5, 3],)
Expected Output: [3, 2, 2, 3]
Explanation: Each item except the last receives the immediately following item's price as its discount.
Input: ([5, 5, 5],)
Expected Output: [0, 0, 5]
Explanation: Equal prices qualify as discounts. The first two items each use the next equal price as a discount.
Input: ([1000000000, 1, 1000000000],)
Expected Output: [999999999, 1, 1000000000]
Explanation: The first item is discounted by 1. The second and third items have no later smaller-or-equal price.
Solution
def solution(prices):
final_prices = prices[:]
stack = []
for i, price in enumerate(prices):
while stack and prices[stack[-1]] >= price:
idx = stack.pop()
final_prices[idx] -= price
stack.append(i)
return final_pricesTime complexity: O(n). Space complexity: O(n).
Hints
- A brute-force search for each item would be too slow for large inputs. Think about how to remember items that are still waiting for a discount.
- Use a monotonic stack of indices. When the current price is less than or equal to the price at the top index, it can serve as that item's discount.