The front display

A bakery's front display holds a fixed number of flavours. When a new batch arrives and the display is full, whatever nobody has asked for in the longest time goes back to the kitchen.

The problem

Build the display. It holds at most capacity flavours, and two instructions arrive:

• ("bake", flavour, trays) — that flavour goes out front with that many trays. If it is already on display, its tray count is updated. If it is new and the display is full, the least recently used flavour leaves. Reports nothing.
• ("ask", flavour) — report its tray count, or -1 if it is not on display.

Both instructions count as using a flavour. An ask that misses uses nothing and changes nothing. Every instruction must take constant time.

Input. capacity — a positive integer. ops — a list of instruction tuples.

Output. A list of tray counts, one per ask, in order.

Example.

capacity = 2
[("bake", "croissant", 12), ("bake", "rye", 8), ("ask", "croissant"),
 ("bake", "seeded", 5), ("ask", "rye"), ("bake", "croissant", 20),
 ("ask", "seeded"), ("ask", "croissant")]
  ->  [12, -1, 5, 20]

Asking for the croissant makes rye the oldest thing out front, so the seeded loaf pushes rye back to the kitchen.

A second example, where baking order and asking order disagree:

capacity = 3
[("bake", "brioche", 1), ("bake", "focaccia", 2), ("bake", "spelt", 3),
 ("ask", "brioche"), ("bake", "milkloaf", 4), ("ask", "focaccia"),
 ("ask", "brioche"), ("ask", "spelt"), ("ask", "milkloaf")]
  ->  [1, -1, 1, 3, 4]

Focaccia was baked after brioche and still leaves first: brioche was asked for later.

Constraints.

• 1 <= capacity <= 10^4
• 1 <= len(ops) <= 10^5
• 0 <= trays <= 10^3; a flavour name is 1 to 20 characters.

Hints

Approach

Brute force

Keep a list in use order, scan it on every instruction and move the flavour found to the front. Each move shifts up to capacity entries: 10⁵ instructions on a display of 10⁴ flavours cost 10⁹ moves.

The insight

A map from flavour to its node answers "where is it", and a doubly linked list of those nodes answers "which is stalest" — together every instruction is a handful of pointer writes.

The list must be doubly linked because unlinking a node needs the node before it, and with forward links only, finding that predecessor is the scan you are avoiding. The map must hold nodes, not tray counts: the node is what lets you unlink without knowing where in the line it sits. Sentinels at head and tail remove every empty-list and end-of-list special case.

Algorithm

1. Link a front and a back sentinel to each other; keep a map from flavour to node.
2. unlink(node) joins its neighbours; push_front(node) inserts it after front.
3. On ask, a flavour absent from the map answers -1; otherwise unlink its node, push it to the front and report its trays.
4. On bake of a flavour already in the map, overwrite its trays, unlink it and push it to the front.
5. On bake of a new flavour, evict back.prev first if the map is full — unlink it, delete its map entry — then create the node, push it to the front and record it.

Complexity

Time O(1) per instruction — a fixed number of pointer writes and one hash lookup. Space O(capacity) — one node and one map entry per flavour.

Solution

"""Bakery front display — a hash map for lookup, a doubly linked list for order."""


class Shelf:
    """One flavour on the display, linked to its neighbours in recency order."""

    __slots__ = ("flavour", "trays", "prev", "next")

    def __init__(self, flavour=None, trays=0):
        self.flavour = flavour
        self.trays = trays
        self.prev = None
        self.next = None


def solve(capacity, ops):
    # Invariant: the list runs newest -> oldest between two sentinels, and
    # `shelves` maps every flavour on display to its own node, so unlinking
    # never needs a scan.
    front = Shelf()        # sentinel: front.next is the most recently asked for
    back = Shelf()         # sentinel: back.prev is the first to be sent back
    front.next, back.prev = back, front
    shelves = {}
    answers = []

    def unlink(node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def push_front(node):
        node.next = front.next
        node.prev = front
        front.next.prev = node
        front.next = node

    for op in ops:
        if op[0] == "ask":
            flavour = op[1]
            node = shelves.get(flavour)
            if node is None:
                answers.append(-1)
            else:
                unlink(node)
                push_front(node)
                answers.append(node.trays)
        else:                                   # ("bake", flavour, trays)
            _, flavour, trays = op
            node = shelves.get(flavour)
            if node is not None:
                node.trays = trays              # a refill, not a new flavour
                unlink(node)
                push_front(node)
                continue
            if len(shelves) == capacity:
                stale = back.prev
                unlink(stale)
                del shelves[stale.flavour]
            node = Shelf(flavour, trays)
            shelves[flavour] = node
            push_front(node)

    return answers

TESTS = [
    (
        (
            2,
            [
                ("bake", "croissant", 12), ("bake", "rye", 8),
                ("ask", "croissant"),
                ("bake", "seeded", 5),
                ("ask", "rye"),
                ("bake", "croissant", 20),
                ("ask", "seeded"), ("ask", "croissant"),
            ],
        ),
        [12, -1, 5, 20],
    ),
    # Eviction follows the last ask, not the last bake.
    (
        (
            3,
            [
                ("bake", "brioche", 1), ("bake", "focaccia", 2), ("bake", "spelt", 3),
                ("ask", "brioche"),
                ("bake", "milkloaf", 4),
                ("ask", "focaccia"), ("ask", "brioche"), ("ask", "spelt"), ("ask", "milkloaf"),
            ],
        ),
        [1, -1, 1, 3, 4],
    ),
    # A refill of a flavour already on display must not evict anything.
    (
        (
            2,
            [
                ("bake", "sourdough", 1), ("bake", "sourdough", 5), ("bake", "bagel", 2),
                ("ask", "sourdough"), ("ask", "bagel"),
            ],
        ),
        [5, 2],
    ),
    # A display one flavour wide.
    (
        (
            1,
            [("bake", "pretzel", 1), ("ask", "pretzel"), ("bake", "stollen", 2), ("ask", "pretzel"), ("ask", "stollen")],
        ),
        [1, -1, 2],
    ),
    # Asking for a flavour that was never baked changes nothing.
    (
        (
            2,
            [
                ("ask", "danish"),
                ("bake", "danish", 6), ("bake", "eclair", 7),
                ("ask", "danish"), ("ask", "eclair"),
            ],
        ),
        [-1, 6, 7],
    ),
]

Pitfalls

• Treating a refill as a new flavour. Baking sourdough twice puts two nodes in the line for one map entry; the next eviction takes the older node and deletes sourdough from the map, so asking for it reports -1 while five trays sit out front.
• Testing the wrong size before evicting. Fullness is the map's size, not the number of bake instructions seen.
• Leaving the evicted flavour in the map. Its node is off the list, but the map still names it, so a later ask reports trays for bread that is back in the kitchen.

Variants

• Lightest bag in the tower — a simpler O(1) structure, where stack discipline does the ordering for you.
• The seed swap drum — a map beside a list again, but with the order thrown away rather than kept.