How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Amazon during technical interviews.

Implement inventory allocation with backorders

Quick Overview

Implement inventory allocation with backorders evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Amazon

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

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)?

Quick Answer: Implement inventory allocation with backorders evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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

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

Expected 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.

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

Expected 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.

Input: ([], [['order', 'o1', [['X', 2]]], ['restock', [['X', 5]]]])

Expected Output: [[['o1', [['X', 2, 0]], True]], [['X', 3]]]

Explanation: Restock of 5 X: 2 clear o1's backorder, remaining 3 become on-hand inventory.

Input: ([], [])

Expected Output: [[], []]

Explanation: No inventory and no events: empty order details and empty inventory.

Input: ([['A', 2], ['B', 0]], [['order', 'o1', [['A', 5], ['B', 4]]], ['restock', [['A', 1]]]])

Expected Output: [[['o1', [['A', 3, 2], ['B', 0, 4]], False]], []]

Explanation: o1: A fulfilled 3 (2 initial +1 restock), 2 backordered; B fully backordered 4; not fully fulfilled.

Input: ([['A', 10]], [['order', 'o1', [['A', 3], ['A', 2]]], ['order', 'o1', [['A', 1]]]])

Expected Output: [[['o1', [['A', 6, 0]], True]], [['A', 4]]]

Explanation: Order o1 referenced twice with duplicate sku lines; A fulfilled total 6, no backorder.

Hints

Keep on-hand stock in a hash map sku -> qty, and a per-SKU FIFO queue of (orderId, remaining) backorders.
On an Order, take min(on_hand, requested); push any shortfall onto that SKU's backorder queue.
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.
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.

Quick Overview