Implement inventory allocation with backorders
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: This question evaluates a candidate's ability to design and implement efficient data structures and algorithms for event-driven inventory allocation and backorder management, including analysis of time and space complexity and extensibility for operations like cancellation.
