Implement an LRU cache with O(1) get and put, then make it thread-safe with TTL.

TL;DR: Pair a hashmap (key to node, O(1) lookup) with a doubly linked list kept in recency order (move-to-front on access, evict at the tail). get and put are both O(1). In production, protect it with a lock for thread safety and hold a per-entry expiry timestamp for TTL, checked on read.

How to approach it. Open with the hard constraint: get and put both have to be O(1), which rules out any list scan for recency. Name the structure that delivers it (hashmap plus doubly linked list) before writing a line. Note OrderedDict as the idiomatic Python shortcut, while showing you understand the pointer machinery beneath it.

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.

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.

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.