Queue + Hash Map Hybrids (Monotone or Window Tracking)

Queue + hash map hybrids appear in LRU caches, sliding window uniqueness with FIFO tie-break, or monotonic queue problems paired with frequency validity checks.

Why this shows up in the real world

Web server connection pools map fd→state; music players queue with lookup by id.

Core idea (explained for students)

collections.deque for O(1) ends plus dict for O(1) lookup of location or existence. LRU: move to end on access—often doubly linked list + map (concept) or OrderedDict legacy patterns.

Try this in Python

from collections import deque, OrderedDict


class LRU:
    def __init__(self, cap: int) -> None:
        self.cap = cap
        self.od: OrderedDict[int, str] = OrderedDict()

    def get(self, k: int) -> str | None:
        if k not in self.od:
            return None
        self.od.move_to_end(k)
        return self.od[k]

    def put(self, k: int, v: str) -> None:
        if k in self.od:
            self.od.move_to_end(k)
        self.od[k] = v
        if len(self.od) > self.cap:
            self.od.popitem(last=False)


l = LRU(2)
l.put(1, 'a')
l.put(2, 'b')
l.get(1)
l.put(3, 'c')
print(list(l.od.keys()))

Common mistakes

• Stale references in map when deque pops without updating map.
• Thread safety—CPython GIL not a correctness guarantee for your own structures.

Key takeaways

• Sketch invariants: len(d)==len(q) when bijection required.
• Practice implement LRU with OrderedDict move_to_end for interviews if allowed.