Quick Overview

This question evaluates array-processing and algorithmic problem-solving skills, focusing on reasoning about subsequent elements to compute element-wise discounts under input constraints.

Compute final prices with next smaller discount

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given an integer array `prices` of length `n`, where `prices[i]` is the original price of the `i`-th item. For each item `i`, find the first index `j > i` such that `prices[j] <= prices[i]`. That `prices[j]` becomes the discount for item `i`, so the final price of item `i` is: - `prices[i] - prices[j]` if such `j` exists - otherwise `prices[i]` Return an array `finalPrices` of length `n` containing the final price for each item. #### Input - `prices`: array of integers #### Output - `finalPrices`: array of integers #### Example - Input: `prices = [8, 4, 6, 2, 3]` - Output: `[4, 2, 4, 2, 3]` #### Constraints (typical) - `1 <= n <= 2e5` - `1 <= prices[i] <= 1e9`

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.

You are given an integer array prices where prices[i] is the original price of the i-th item. For each item i, find the first index j > i such that prices[j] <= prices[i]. If such an index exists, prices[j] is used as the discount for item i, and the final price is prices[i] - prices[j]. If no such index exists, the final price remains prices[i]. Return an array finalPrices containing the final price of each item.

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.

Hints

  1. 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.
  2. 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.

Loading coding console...