Katkat
Back

Allocate an Order from the Oldest Inventory Batches

AirbnbSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Implement a function to allocate an order across inventory batches using FIFO (oldest timestamp first, with batch ID tie-breaker), returning allocation details and any unfilled quantity without mutating the input.

Problem Statement

You are building an inventory fulfillment service for a marketplace. When a customer places an order for a given quantity of an item, inventory must be fulfilled using a First-In, First-Out (FIFO) strategy to ensure older stock is depleted first.

Write a function allocate_inventory(batches: list[dict], order_quantity: int) -> dict that fulfills the requested order quantity from available batches according to these rules:

  1. Allocation Priority: Batches must be consumed in ascending order of timestamp. If two batches have the identical timestamp, break ties by batch_id in lexicographical ascending order.
  2. Partial Allocation: A batch can be partially consumed if the remaining order quantity is less than the batch's available quantity.
  3. Output Format: Return a dictionary with two keys:
    • "allocations": A list of objects {"batch_id": str, "allocated_quantity": int} for each batch that provided at least 1 unit, ordered by allocation sequence.
    • "unfilled_quantity": An integer representing the quantity that could not be fulfilled if total available inventory is insufficient.
  4. Immutability: Do not mutate the input list batches or any of the dictionaries inside it.

Function Signature

def allocate_inventory(batches: list[dict], order_quantity: int) -> dict:
    pass

Input Format

  • batches: A list of dictionaries, where each dictionary contains:
    • "batch_id" (str): Unique identifier for the batch.
    • "timestamp" (int): Timestamp representing when the batch was received.
    • "quantity" (int): Current quantity available in this batch (quantity >= 0).
  • order_quantity: An integer representing the number of units requested (order_quantity >= 0).

Constraints

  • 0 <= len(batches) <= 10^5
  • 0 <= order_quantity <= 10^9
  • 0 <= batch["quantity"] <= 10^9
  • 0 <= batch["timestamp"] <= 2 * 10^9
  • Batch IDs are unique strings containing alphanumeric characters.

Examples

Example 1

batches = [
    {"batch_id": "b-3", "timestamp": 1600000020, "quantity": 5},
    {"batch_id": "b-1", "timestamp": 1600000010, "quantity": 10},
    {"batch_id": "b-2", "timestamp": 1600000010, "quantity": 8}
]
order_quantity = 15

output = allocate_inventory(batches, order_quantity)
# Returns:
# {
#     "allocations": [
#         {"batch_id": "b-1", "allocated_quantity": 10},
#         {"batch_id": "b-2", "allocated_quantity": 5}
#     ],
#     "unfilled_quantity": 0
# }

Explanation: b-1 and b-2 both have timestamp 1600000010. "b-1" < "b-2", so b-1 is used first (all 10 units). The remaining 5 units are taken from b-2.

Hints

Hint 1

Sort a shallow copy or sorted view of the batches using a composite sort key of `(timestamp, batch_id)` so the original data remains unmodified.

Hint 2

Iterate through the sorted batches, taking `min(batch['quantity'], remaining_order)` at each step until the order is satisfied or all batches are exhausted.

Hint 3

Only append a record to `allocations` if the allocated amount from that batch is strictly greater than zero.

Follow-up questions

  • How would you optimize the allocation if `batches` contains millions of elements but `order_quantity` is small and can typically be satisfied by the first few batches?
  • If batch quantities are updated concurrently across multiple worker threads, what concurrency control mechanisms would you introduce to prevent race conditions or double allocations?
  • How would you handle expiring inventory (e.g., each batch has an `expiration_date`), where expired batches must be skipped and batches closest to expiration must be consumed first?