LRU cache in O(1): hashmap plus doubly linked list, TTL, locking.

TL;DR: Combine a hashmap (key to node, O(1) lookup) with a doubly linked list ordered by recency (move-to-front on access, evict from the tail). Both get and put are O(1). For production use, guard it with a lock for thread safety and store an expiry timestamp per entry for TTL, checking it on read.

How to approach it. Lead with the hard constraint: both get and put must be O(1), which immediately kills any list scan for recency. Name the structure that hits it (hashmap plus doubly linked list) before you write a line. Mention OrderedDict as the idiomatic Python shortcut, but make clear you know the pointer machinery underneath.

A strong answer. The move is to pair two structures. A hashmap gives O(1) key lookup. A doubly linked list orders entries by recency, so you move a node to the front on access and evict from the tail, both O(1). The dict points straight at the node, so you never walk the list to find anything. Python's OrderedDict is exactly this under the hood:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.d = OrderedDict()             # key -> value, ordered by recency

    def get(self, key):
        if key not in self.d:
            return -1
        self.d.move_to_end(key)            # mark most-recently used
        return self.d[key]

    def put(self, key, value):
        if key in self.d:
            self.d.move_to_end(key)
        self.d[key] = value
        if len(self.d) > self.cap:
            self.d.popitem(last=False)     # evict least-recently used (front)

Both operations are O(1): the dict gives O(1) lookup, and move_to_end/popitem are O(1) on the linked structure. Narrate why the linked list earns its keep: a plain dict finds a key in O(1) but finding the least-recently-used to evict would be O(n) without the recency ordering baked into the list. When the interviewer takes OrderedDict away, what is left is the standard doubly linked list pointer surgery: sentinel head and tail, unlink a node from its neighbors, splice it back in behind the head.

For the usual follow-ups: wrap each public method in a threading.Lock for thread safety, and for TTL store (value, expires_at) and treat an entry as a miss (and delete it) if time.monotonic() > expires_at on read. Ordering by expiry rather than by recency is a different problem with the same flavor: a GPU credit ledger has to spend the grant that expires soonest first, so its eviction order is FIFO by expiry, not LRU.

The recency invariant in one picture, where the head is most-recently-used and the tail is the eviction target:

Key takeaways

• The hashmap buys O(1) lookup; the doubly linked list buys O(1) recency reordering and eviction. Neither alone is enough.
• A read counts as a use: get must move the node to the front, or your LRU degrades to a random-eviction cache.
• TTL is a per-entry expiry checked lazily on read; thread safety is a lock per method, sharded by key hash under contention.

What interviewers probe next.

• "Implement it without OrderedDict." A dict mapping key to a node in a hand-rolled doubly linked list with sentinel head/tail; show the unlink/insert-at-front pointer surgery.
• "Make it thread-safe." A lock around get/put; for high contention, shard by key hash so locks are independent.
• "Add TTL." Store expiry per entry, lazily evict on access; optionally a background sweep for memory.
• "LRU vs LFU vs ARC?" LRU evicts by recency; LFU by frequency (better for skewed access but heavier); ARC adapts between them. Choose by access pattern.

Common mistakes.

• Using a list/array for recency, making eviction O(n).
• Forgetting to update recency on get (a read must count as a use).
• Off-by-one on capacity (evicting before or after insert inconsistently).
• Claiming thread safety without a lock, then racing on the shared structure.