Sum Prices Discounted by the Minimum Earlier Price
Company: PayPal
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Overview: Sum item costs discounted by the minimum earlier price with a prefix-minimum scan, preserving negative costs and avoiding current-item discount errors.
Read the full PayPal Software Engineer interview experience this question came from
Constraints
- prices contains 0 through 2^31 - 1 integers.
- Each price and the exact final total are between -(2^53 - 1) and 2^53 - 1, inclusive.
- Intermediate sums and item costs can extend beyond the final total's range.
Examples
Input: ([7, 5, 9, 4, 8],)
Expected Output: 12
Explanation: The individual costs in order are 7, -2, 4, -1, and 4.
Input: ([12, 9, 3],)
Expected Output: 3
Explanation: The costs are 12, -3, and -6. Both negative costs contribute to the sum.
Hints
- For an item that costs less than every earlier item, work out its contribution before moving to the next index.