Q7 - Flash Sale Revenue (Dynamic Pricing Across Suppliers)

Scenario: Amazon is running a flash sale on one high-demand product, stocked by several suppliers at once. Pricing is dynamic: a unit sells for whatever that supplier has left on the shelf at that moment, and every sale walks that supplier's price down by one.

The rules, exactly as they play out:

• A sale takes one unit from one supplier.
• The revenue from that sale is that supplier's current stock level.
• Immediately after, that supplier's stock drops by one, so the next unit from them is worth one less.
• A supplier at zero stock is out of the sale.

You choose which supplier to sell from each time. Fill orders units so total revenue is as high as possible.

flash_sale_revenue(supplier_stock, orders)
    ->  the largest total revenue achievable

• supplier_stock is the list of stock levels, one entry per supplier. [3, 5] means supplier A has 3 units and supplier B has 5.
• orders is how many units the sale has to move in total, across all suppliers combined.
• Stock levels are whole numbers and may be 0, which just means that supplier has nothing to sell.
• If orders is larger than the total stock, sell every unit there is and stop. If there is nothing to sell, the revenue is 0.

supplier_stock = [3, 5]        orders = 6

   A has 3 units      B has 5 units

SALE  PRICE   WHY THAT PRICE                      STOCK AFTER
-------------------------------------------------------------
1     5       supplier B is the tallest pile at 5 [3, 4]
2     4       B again, now 4 high                 [3, 3]
3     3       tied at 3, take A                   [2, 3]
4     3       now B at 3                          [2, 2]
5     2       tied at 2, take A                   [1, 2]
6     2       now B at 2                          [1, 1]
-------------------------------------------------------------
      19      total revenue

answer:  5 + 4 + 3 + 3 + 2 + 2  =  19

The ties in sales 3 and 5 do not matter. Taking A or B first changes which supplier ends up with which leftover, but the prices collected are the same, so the revenue is the same.

supplier_stock = [2, 4, 4]     orders = 5

   A has 2 units      B has 4 units      C has 4 units

SALE  PRICE   WHY THAT PRICE                      STOCK AFTER
-------------------------------------------------------------
1     4       B and C are tied at 4, take B       [2, 3, 4]
2     4       now C at 4                          [2, 3, 3]
3     3       B and C tied at 3, take B           [2, 2, 3]
4     3       now C at 3                          [2, 2, 2]
5     2       everything is 2 now, take A         [1, 2, 2]
-------------------------------------------------------------
      16      total revenue

answer:  4 + 4 + 3 + 3 + 2  =  16

supplier_stock = [2, 3]        orders = 99

There are only 5 units in the whole sale, so all 5 sell and the sale ends:

   from A:  2 + 1        =  3
   from B:  3 + 2 + 1    =  6

answer:  9

Solution

Step 1: A supplier is a pile, and the price is its height

Draw each supplier as a stack of units. Selling takes the unit off the top, and what you are paid is how tall the pile was when you took it.

supplier_stock = [3, 5]

     A            B
                 [5]   <- taking this unit pays 5
                 [4]
    [3]          [3]
    [2]          [2]
    [1]          [1]   <- and this one pays 1

So supplier A can pay you 3, then 2, then 1. Supplier B can pay 5, then 4, 3, 2, 1. Nothing you do to one pile changes the other.

Step 2: Every price is decided before the sale starts

This is the step that turns the question from a simulation into a one-liner. A supplier holding s units will pay out exactly s, s-1, ..., 1 if you drain them, and in that order, always, no matter what you do elsewhere. Your choices never change the price list; they only change how far down each list you go.

Write out every price in the whole sale, from  supplier_stock = [3, 5]:

   from A:   3   2   1
   from B:   5   4   3   2   1

   the whole board:   5  4  3  3  2  2  1  1
                      |______________|
                      the 6 biggest, which is what orders = 6 buys

                      5 + 4 + 3 + 3 + 2 + 2  =  19

So the answer is just the sum of the orders largest numbers on that board. The only reason greedy works is sitting right there: each supplier's prices come out in decreasing order anyway, so taking the biggest number left on the board never breaks the rule that you have to sell a pile from the top down.

Step 3: A max-heap takes the biggest number every time

You do not have to build the board. Keep the suppliers in a max-heap keyed by current stock. Pop the tallest, add its height to the revenue, and push it back one shorter unless it just hit zero.

orders = 6,  heap starts as  [5, 3]

  pop 5   revenue 5    push 4    heap [4, 3]
  pop 4   revenue 9    push 3    heap [3, 3]
  pop 3   revenue 12   push 2    heap [3, 2]
  pop 3   revenue 15   push 2    heap [2, 2]
  pop 2   revenue 17   push 1    heap [2, 1]
  pop 2   revenue 19   push 1    heap [1, 1]

  revenue 19

import heapq


def flash_sale_revenue(supplier_stock, orders):
    # heapq is a min-heap, so store negatives to pop the tallest pile
    piles = [-units for units in supplier_stock if units > 0]
    heapq.heapify(piles)
    revenue = 0
    while orders > 0 and piles:
        price = -heapq.heappop(piles)  # the tallest pile sets this sale's price
        revenue += price
        orders -= 1
        if price - 1 > 0:
            heapq.heappush(piles, -(price - 1))
    return revenue

Complexity Analysis

With n suppliers and k orders, building the heap is O(n) and every sale costs one pop and one push: O(n + k log n) time, O(n) space.

That is the answer most candidates give, and on a normal input it is fine. The follow-up is where the round is won.

When the Order Count Runs Into the Millions

k log n stops being acceptable the moment orders is a billion, and online assessments like this one routinely set it there. One sale at a time is hopeless; you need to sell in blocks.

Step 4: Count how many units cost at least a given price

Go back to the board of prices from Step 2. A supplier with s units offers exactly one unit at every price from 1 to s, so it contributes a unit priced p or higher whenever s >= p, and it contributes s - p + 1 of them.

supplier_stock = [3, 5]

   units priced 3 or more?    A: 3-3+1 = 1    B: 5-3+1 = 3    total 4
   units priced 2 or more?    A: 3-2+1 = 2    B: 5-2+1 = 4    total 6
   units priced 1 or more?    A: 3            B: 5            total 8

That count only ever goes down as the price goes up, which is exactly the shape binary search needs.

Step 5: Binary search for the cut-off price

Find the highest price whose count still covers the whole order. Call it the cut-off. Every unit priced above the cut-off definitely sells, and the order is finished off with units sitting exactly at the cut-off.

orders = 6,  searching prices 1 through 5:

   price 3 -> only 4 units at or above it     not enough, look lower
   price 2 -> 6 units at or above it          enough, remember 2 and look higher
   price 1 -> 8 units                enough, but 2 is higher and also works

   cut-off = 2

Step 6: Sum each supplier's block in one arithmetic series

Above the cut-off, every supplier sells a solid run of prices with no gaps, from its stock level down to cut-off + 1. The sum of a run is the usual (first + last) * count / 2.

cut-off = 2, so take everything priced 3 or more:

   A (3 units):  just the 3           ->  3            1 unit
   B (5 units):  5 + 4 + 3            ->  12           3 units
                                          ----         ----
                                           15          4 units sold

   6 - 4 = 2 orders still to fill, all at the cut-off price of 2:   2 * 2 = 4

   total revenue  15 + 4  =  19      the same answer, no sale simulated

The top-up at the end is the part people forget. The cut-off price usually has more units sitting at it than you still need, so you take only as many as the order requires, at exactly that price.

The whole second solution in one picture, on Example 1:

The cut-off price across both supplier piles

def units_priced_at_least(supplier_stock, price):
    """How many units in the whole sale would go for `price` or more."""
    return sum(units - price + 1 for units in supplier_stock if units >= price)


def flash_sale_revenue(supplier_stock, orders):
    orders = min(orders, sum(supplier_stock))
    if orders == 0:
        return 0
    low, high, cutoff = 1, max(supplier_stock), 1
    while low <= high:  # highest price that still covers the order
        mid = (low + high) // 2
        if units_priced_at_least(supplier_stock, mid) >= orders:
            cutoff, low = mid, mid + 1
        else:
            high = mid - 1
    revenue = 0
    sold = 0
    for units in supplier_stock:  # whole blocks priced above the cut-off
        if units > cutoff:
            count = units - cutoff
            revenue += (units + cutoff + 1) * count // 2
            sold += count
    return revenue + (orders - sold) * cutoff    # top up at the cut-off price

Complexity Analysis

Let n be the number of suppliers and M the largest stock level.

• Binary search runs log M rounds, each scanning all suppliers: O(n log M).
• The final pass over the suppliers is O(n).
• Space is O(1) beyond the input.

Notice what dropped out: orders no longer appears anywhere in the running time. A billion orders costs exactly the same as six. That is the difference between a solution that passes and one that times out on the last three test cases.

Final Notes

1. The price list is fixed before you start. A supplier holding s units will pay s, s-1, ..., 1 in that order whatever you do elsewhere, so the question is only ever "which orders of these numbers are the biggest". Everything else follows from that one sentence, and saying it out loud early is the strongest signal in the round.

2. That sentence is also the proof that greedy is safe. You are not asked to trust a hunch. Because each supplier's prices already come out in decreasing order, taking the largest number left on the board can never violate the sell-from-the-top rule, so the greedy choice and the optimal choice are the same thing.

3. The heap is the honest first answer, so give it. It is correct, it is quick to write, and it shows you can reach for the right structure. Do not skip straight to the clever version and leave the interviewer unsure whether you could have coded the simple one.

4. Then ask what orders can be. That single clarifying question is what opens the second half of the problem. If the answer is "up to a billion", the heap is dead on arrival and the interviewer is waiting to see whether you notice.

5. Binary search on the price, not on the answer. The quantity that behaves monotonically here is "how many units cost at least p", which shrinks as p grows. Finding the thing that moves in one direction is most of the work in any binary-search problem.

6. The top-up at the cut-off is the bug everyone ships. There are usually more units sitting at the cut-off price than you still need, so you take only the shortfall, at exactly that price. Getting the blocks right and then over-counting the last price is the single most common way this solution fails its own examples.

7. Reach for a 64-bit accumulator before anyone asks. Large stock across many suppliers pushes the revenue past two billion easily, and a silent 32-bit overflow produces a confident, wrong number.

Work Example 1 by hand both ways, once with the heap and once with the cut-off, until the two land on 19 for the same reasons. The day this shows up with a billion orders attached, you will already know which half of the problem you are in.