Katkat
Back

Implement inventory allocation with backorders

AmazonApplied Scientist · Onsite
MediumApplied ScientistOnsiteCoding & Algorithms

Last updated

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.

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