Quick Overview

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.

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

Hints

  1. Always sell from a product with the current highest stock.
  2. Batch equal price levels instead of simulating every customer.

Loading coding console...