## Problem An order requests a quantity of one item, and inventory is stored in batches. Each batch has a unique reference ID, an arrival timestamp, and a positive available quantity. Allocate inventory from the oldest batches first. Return the quantity taken from each batch in allocation order and the unfilled quantity. Do not mutate the input. A batch may be partially consumed. When two batches have the same arrival timestamp, use the lexicographically smaller reference ID first. ### Function Contract Implement `allocateOldestFirst(requestedQuantity, batches)`. Each batch is represented as `[referenceId, arrivedAt, availableQuantity]`, where `arrivedAt` is an integer timestamp. Return `[allocations, unfilled]`, where every allocation is `[referenceId, quantityTaken]`. ### Constraints & Assumptions - `0 <= requestedQuantity <= 10^12`. - `0 <= len(batches) <= 200,000`. - Batch reference IDs are unique nonempty ASCII strings. - Arrival timestamps and quantities are integers; every available quantity is positive. - Omit batches from which no quantity is taken. - If inventory is insufficient, consume all eligible stock and report the remainder in `unfilled`. ### Clarifying Questions to Ask - Does oldest-first use input order? No, use `(arrivedAt, referenceId)`. - May the last selected batch be partially consumed? Yes. - What should a zero-sized order return? Empty allocations and zero unfilled quantity. - Should the function update stock balances? No, it only computes an allocation plan. ```hint Sort once, then consume After ordering the batches by age and reference ID, every allocation decision is local: take the smaller of the remaining request and the current batch quantity. ``` ### Examples ```text requestedQuantity = 8 batches = [ ["B", 20, 10], ["A", 10, 3], ["C", 10, 4] ] result = [ [["A", 3], ["C", 4], ["B", 1]], 0 ] ``` ```text requestedQuantity = 7 batches = [["x", 1, 2]] result = [[ ["x", 2] ], 5] ``` ### Evaluation Focus - Uses the exact oldest-first and tie-break ordering. - Never allocates more than a batch contains or more than the order needs. - Produces a deterministic plan and correct unfilled remainder. - Handles zero quantity, empty inventory, and values beyond 32-bit range. - Runs in `O(n log n)` time and `O(n)` output or sorting space. ### Extensions to Discuss 1. How would you make allocation atomic when concurrent orders consume the same stock? 2. What index would support repeated oldest-first allocations without sorting every time? 3. How would expiration dates alter the eligibility and ordering rules?