Katkat
Back

Compute discounted prices in a queue

PlaidSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates proficiency in array processing, algorithm design, use of auxiliary data structures such as monotonic stacks, and formal complexity and correctness reasoning.

Given an integer array prices where prices[i] is the price of the i-th item in a checkout line, apply the following rule: for each i, find the first j > i such that prices[j] <= prices[i]; if such j exists, the item's discount is prices[j], so its final price is prices[i] - prices[j]; otherwise, no discount applies. Return both (

  1. the array of final prices and (
  2. the total savings across all items. Solve in O(n) time using an appropriate data structure, prove correctness, analyze time/space complexity, and provide code in a language of your choice along with brief tests.