Implement inventory allocation with backorders

Design and implement a function to process an event stream for an e-commerce marketplace. Input: (1) initial inventory as a list of (sku: string, qty: int); (2) events ordered by timestamp, each either Order(orderId: string, items: [(sku, qty)]) or Restock(items: [(sku, qty)]). Rules: For each Order, allocate from current inventory by SKU; if insufficient, fulfill what you can and record the remainder as a backorder for that order. When a Restock arrives, allocate to outstanding backorders in FIFO order before increasing on-hand inventory. Output: after all events, return (a) per-order fulfillment details (fulfilled and backordered quantities per SKU and whether fully fulfilled) and (b) final on-hand inventory by SKU. Constraints: up to 1e5 events and 1e5 distinct SKUs; target time O(E log S) and space O(S + B). Describe the data structures you would use (e.g., hash maps, heaps, queues) and analyze complexity. How would you extend this to support order cancellation in O(log S)?

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Implement inventory allocation with backorders

Process an ordered event stream for an e-commerce marketplace.

Inputs

• initial_inventory: a list of [sku, qty] pairs giving starting on-hand stock.
• events: a list of events in timestamp order. Each event is one of:
  • ["order", orderId, [[sku, qty], ...]]
  • ["restock", [[sku, qty], ...]]

Rules

• For each Order, allocate from current on-hand inventory per SKU. If on-hand is insufficient, fulfill what you can and record the remainder as a backorder for that order/SKU.
• When a Restock arrives for a SKU, first allocate to that SKU's outstanding backorders in FIFO order (oldest backorder first); only the leftover increases on-hand inventory.
• An order id may appear more than once; accumulate its lines. Duplicate SKU lines within an order accumulate too.

Output — return [order_details, final_inventory]:

• order_details: one entry per order (in first-seen order): [orderId, [[sku, fulfilled, backordered], ...], fully_fulfilled], with the SKU lines sorted by SKU and fully_fulfilled true iff no SKU is backordered.
• final_inventory: [[sku, qty], ...] for SKUs with qty > 0, sorted by SKU.

Target time O(E log S) overall (per-event work is amortized O(1) per affected SKU via hash maps + FIFO queues); space O(S + B) for S distinct SKUs and B outstanding backorder lines.

Constraints

• Up to 1e5 events and up to 1e5 distinct SKUs.
• Quantities are non-negative integers; an order line may request more than is on hand.
• Events are already sorted by timestamp.
• Restock allocates to a SKU's backorders strictly FIFO before adding to on-hand stock.
• An order id may recur across events; its lines accumulate.

Examples

Example 1

Input: ([['A', 5], ['B', 3]], [['order', 'o1', [['A', 2], ['B', 1]]]])
Output: [[['o1', [['A', 2, 0], ['B', 1, 0]], True]], [['A', 3], ['B', 2]]]

Explanation: Order o1 fully fulfilled from initial stock; remaining inventory A=3, B=2.

Example 2

Input: ([['A', 1]], [['order', 'o1', [['A', 3]]], ['order', 'o2', [['A', 2]]], ['restock', [['A', 3]]]])
Output: [[['o1', [['A', 3, 0]], True], ['o2', [['A', 1, 1]], False]], []]

Explanation: o1 gets 1 then 2 on restock (full); o2 gets 1 of 2 (1 backordered); no leftover inventory.

Hints

1. Keep on-hand stock in a hash map sku -> qty, and a per-SKU FIFO queue of (orderId, remaining) backorders.
2. On an Order, take min(on_hand, requested); push any shortfall onto that SKU's backorder queue.
3. On a Restock, drain the SKU's backorder queue front-to-back, updating each affected order's fulfilled/backordered counts, then add only the leftover to on-hand stock.
4. Track orders in first-seen insertion order so the output is deterministic; mark an order fully fulfilled only when none of its SKUs has a positive backordered count.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Design and implement a function to process an event stream for an e-commerce marketplace. Input: ( 1) initial inventory as a list of (sku: string, qty: int); ( 2) events ordered by timestamp, each either Order(orderId: string, items: [(sku, qty)]) or Restock(items: [(sku, qty)]). Rules: For each Order, allocate from current inventory by SKU; if insufficient, fulfill what you can and record the remainder as a backorder for that order. When a Restock arrives, allocate to outstanding backorders in FIFO order before increasing on-hand inventory. Output: after all events, return (a) per-order fulfillment details (fulfilled and backordered quantities per SKU and whether fully fulfilled) and (b) fi...

Recommended Approach

When repeatedly combining the two smallest available values, use a min-heap. Pop the two smallest, add their sum to the total cost, and push the combined value back until one value remains. This is the same greedy structure as Huffman merging.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Time: O(n log n). Space: O(n).

Edge Cases and Tests

No values, one value, duplicate values, very large sums, and proving the greedy choice by exchange argument.