Cake order fulfillment check

Question: Cake order fulfillment check

Companies: Google, Amazon

Difficulty: Easy

Problem statement

A bakery keeps three kinds of cake. Its stock is an array stock of length 3, where stock[i] is how many cakes of type i are on hand.

Orders arrive one at a time in the list orders. Each order is also an array of length 3: order[i] is how many cakes of type i the customer wants.

Serve the orders in the order they arrive. An order is fully completed only if the current stock covers every type it asks for. When that happens, remove all of its cakes from stock. If any type is short, reject the whole order: nothing is taken from stock, and you move on to the next order.

Implement:

def process_orders(stock: list[int], orders: list[list[int]]) -> list[bool]

Return one boolean per order, True if it was fully completed. Also be ready to return just the count of completed orders.

Constraints

• 0 <= stock[i] <= 10^9
• 0 <= len(orders) <= 10^5
• Every order has length 3 and 0 <= order[i] <= 10^9

Example 1

stock  = [5, 6, 7]
orders = [[2, 1, 3], [1, 1, 5], [3, 5, 4]]

• Order 0 fits. Stock becomes [3, 5, 4].
• Order 1 needs 5 of type 2, but only 4 are left. Rejected, stock stays [3, 5, 4].
• Order 2 fits exactly. Stock becomes [0, 0, 0].

Output: [True, False, True] (2 orders completed).

Example 2

stock  = [4, 4, 4]
orders = [[1, 1, 1], [1, 1, 9], [3, 3, 3]]

Output: [True, False, True]. The second order must not take any type-0 or type-1 cakes before it fails on type 2; otherwise the third order would wrongly be rejected.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

This is a simulation problem. Do exactly what the statement says, in order, and watch for one trap: an order is all or nothing.

The trap. The naive loop subtracts each cake type as it checks it. If type 0 fits but type 2 doesn't, type 0 has already been taken out, and the stock is now wrong for every later order. Checking and committing must be two separate steps:

1. Check. For every type i, confirm order[i] <= stock[i]. Don't change anything yet.
2. Commit. Only if every check passes, subtract the whole order and count it.

An order that fails is skipped. It leaves the stock untouched, and the next order is checked against the same stock.

Invariant. After each order, stock equals the starting stock minus the sum of all orders accepted so far, and every entry is >= 0. Because a rejected order changes nothing, the result for order j depends only on which earlier orders were accepted.

Why no cleverer method. Orders arrive in a fixed sequence and each one's outcome depends on the stock left by the ones before it, so you have to look at every order once. A single pass is already optimal: O(n * k) time, where k = 3 here. Sorting or reordering would change the answer, because the problem asks what happens when orders are served in arrival order.

Write the check with all(...) over the types instead of hard-coding three comparisons. Then the solution works for any number of cake types, which is the usual first follow-up.

Code

from typing import List, Sequence


def can_fulfill(stock: Sequence[int], order: Sequence[int]) -> bool:
    """True if every requested quantity is available. Does not modify stock."""
    if len(order) != len(stock):
        raise ValueError("order and stock must list the same cake types")
    return all(need <= have for need, have in zip(order, stock))


def process_orders(stock: List[int], orders: List[List[int]]) -> List[bool]:
    """Serve orders in arrival order, all or nothing.

    Returns one flag per order (True = fully completed). `stock` is
    updated in place to the quantities left at the end.
    """
    results: List[bool] = []
    for order in orders:
        if any(q < 0 for q in order):
            raise ValueError(f"negative quantity in order {order}")
        if can_fulfill(stock, order):           # check every type first
            for i, need in enumerate(order):    # then commit the whole order
                stock[i] -= need
            results.append(True)
        else:
            results.append(False)               # rejected: stock unchanged
    return results


def count_completed(stock: List[int], orders: List[List[int]]) -> int:
    """Number of fully completed orders. Works on a copy of stock."""
    return sum(process_orders(list(stock), orders))


if __name__ == "__main__":
    # Second order needs 5 of type 2 but only 4 remain: rejected whole.
    s = [5, 6, 7]
    assert process_orders(s, [[2, 1, 3], [1, 1, 5], [3, 5, 4]]) == [True, False, True]
    assert s == [0, 0, 0]

    # The partial-subtraction bug would make the third order fail.
    assert count_completed([4, 4, 4], [[1, 1, 1], [1, 1, 9], [3, 3, 3]]) == 2

    # Zero-quantity orders always succeed; empty input gives 0.
    assert count_completed([0, 0, 0], [[0, 0, 0], [0, 0, 1]]) == 1
    assert count_completed([1, 2, 3], []) == 0

    # Exactly enough stock is enough.
    assert count_completed([2, 2, 2], [[2, 2, 2], [1, 0, 0]]) == 1

    # Works for any number of types.
    assert count_completed([10, 1], [[5, 1], [5, 1], [5, 0]]) == 2

    print("all tests passed")

Complexity

• can_fulfill: O(k) time, O(1) extra space, where k is the number of cake types (3 here).
• process_orders: O(n * k) time for n orders, O(n) space for the result flags. With k fixed at 3 this is O(n).
• count_completed: O(n * k) time, O(k) extra space for the copied stock (plus the O(n) flags, which a counting-only version can drop).

Test cases

• stock = [5, 6, 7], orders [[2,1,3], [1,1,5], [3,5,4]] → [True, False, True], 2 completed, stock ends [0, 0, 0].
• stock = [4, 4, 4], orders [[1,1,1], [1,1,9], [3,3,3]] → 2. A version that subtracts before checking every type returns 1.
• Exact fit: stock = [2, 2, 2], orders [[2,2,2], [1,0,0]] → 1.
• All-zero order on empty stock: stock = [0, 0, 0], orders [[0,0,0]] → 1.
• No orders: any stock, [] → 0.
• Every order too big: stock = [1, 1, 1], orders [[2,0,0], [0,2,0]] → 0, stock unchanged.
• An early rejection lets a later order succeed: stock = [3, 3, 3], orders [[4,0,0], [3,3,3]] → 1.
• Invalid input: an order with a negative quantity or the wrong length raises ValueError.

Follow-ups

1. Any number of cake types. Already handled: the check is a loop over the types. Validate that each order has the same length as stock.
2. Maximize the number of completed orders (any order allowed). With one cake type, sort orders by quantity and take the smallest first; that greedy is optimal. With two or more types it becomes multi-dimensional knapsack, which is NP-hard. Discuss exact search (backtracking or DP over remaining stock, feasible only when stock values are small) versus heuristics such as sorting by total or by the largest share of any type's stock.
3. Restock events mixed into the stream. Process events in time order: a restock adds to stock, an order is checked and committed as before. The all-or-nothing rule does not change. If rejected orders should be retried after a restock, keep them in a FIFO waiting queue and re-check from the front after each restock.
4. Partial fulfillment allowed. Ship min(order[i], stock[i]) of each type and record what is still owed. The return value becomes a per-order shipped/backordered breakdown instead of a flag.
5. Concurrent orders (inventory service). The check and the commit must be one atomic step. Use a lock around both, or a conditional update (UPDATE ... SET qty = qty - x WHERE qty >= x for each type inside one transaction). Without that, two orders can both pass the check and drive the stock negative.

Interviewer expectations

Mid-level (L4)

• Reads the "fully completed" rule correctly and checks every type before subtracting anything.
• Writes a clean single pass with correct results on the exact-fit and all-zero cases.
• States O(n) time and constant extra space.

Senior (L5)

• Names the partial-subtraction bug before coding and writes a test that would catch it.
• Generalizes to k types without being asked; validates lengths and negative quantities.
• Handles the restock and partial-fulfillment follow-ups by changing the data model, not by bolting on special cases.

Staff (L6+)

• Explains why maximizing completed orders is easy with one type (greedy) and NP-hard with several (multi-dimensional knapsack), and proposes a practical approach.
• Turns the check-then-commit step into an atomic operation for a concurrent inventory service, and discusses lock scope, transactions, and fairness for queued orders.
• Asks what the business wants for rejected orders (drop, backorder, retry), since that choice drives the design.