Maximize revenue from inventory sales
Company: Squarepoint
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
### Problem
A store has `n` different products. For each product `i` (0-indexed), you are given an integer `quantity[i]` representing how many units of that product are currently in stock.
The store will serve `m` customers. Each customer buys exactly one unit of some product, subject to availability (you cannot sell a product whose stock is 0).
**Pricing rule:**
- When a customer buys one unit of product `i`, the price they pay is equal to the **current** remaining stock of product `i` *before* the purchase.
- After the purchase, the stock of product `i` decreases by 1 (i.e., `quantity[i]--`).
- Thus, if product `i` has stock 5 when a customer arrives and they buy it, that customer pays 5, and the stock becomes 4 for future customers.
The store can choose, for each customer, which product to sell (among those with positive stock) in order to maximize total revenue.
If `m` is larger than the total number of units in stock, then at most the total stock many customers can be served; the remaining customers simply cannot buy anything.
### Input
- An integer `n` – the number of different products.
- An array `quantity` of length `n`, where `quantity[i]` is a non-negative integer representing the initial stock of product `i`.
- An integer `m` – the number of customers, where each customer buys at most one unit as described.
### Output
Return a single integer: the **maximum total revenue** the store can obtain by appropriately choosing which product to sell to each customer.
You should design an efficient algorithm suitable for large `n`, `m`, and quantities.
### Example
Suppose:
- `n = 2`
- `quantity = [2, 3]`
- `m = 3`
One optimal sequence of sales is:
- Customer 1 buys from product 1 (stock 3) → pays 3, stock becomes `[2, 2]`.
- Customer 2 buys from product 0 (stock 2) → pays 2, stock becomes `[1, 2]`.
- Customer 3 buys from product 1 (stock 2) → pays 2, stock becomes `[1, 1]`.
Total revenue = `3 + 2 + 2 = 7`, which is optimal.
Implement a function that computes this maximum revenue.
Quick Answer: This question evaluates algorithmic problem-solving and optimization competencies focused on dynamic resource allocation, revenue maximization, and designing efficient solutions that scale with large n, m, and quantities.
Each sale from a product earns its current stock before decrementing. Serve at most m customers and choose products to maximize total revenue. Return the maximum revenue.
Constraints
- quantity values are non-negative
- If m exceeds total stock, sell only available units
Examples
Input: ([2, 3], 3)
Expected Output: 7
Input: ([5], 10)
Expected Output: 15
Input: ([2, 8, 4, 10, 6], 20)
Expected Output: 110
Input: ([0, 0], 5)
Expected Output: 0
Input: ([3, 3], 4)
Expected Output: 10
Hints
- Always sell from a product with the current highest stock.
- Batch equal price levels instead of simulating every customer.