Implement an LRU Cache with O(1) Get and Put

Prompt and Applicable Context

Implement LRUCache(capacity) for positive integer capacity. Keys and values are non-negative integers. get(key) returns the stored value or -1 when the key is absent. put(key, value) inserts or updates a key. A successful get and every put make that key the most recently used. Inserting a new key when the cache is full evicts exactly one least recently used key. Both public operations must take expected O(1) time.

This is a data-structure coding question, not a distributed-cache design. The implementation is single-process and single-threaded; it does not include TTL, persistence, size-based weights, or concurrent access. “Expected O(1)” relies on the usual average-performance assumption for hash-table operations. Pointer changes in the linked list are worst-case O(1).

The important result is not the phrase “hash map plus doubly linked list.” A complete answer derives why both structures are necessary, states the map–list invariant, handles an existing-key update without accidental eviction, and verifies ordering after each operation.

What the Interviewer Evaluates

The first signal is translating requirements into operations. A key must be found without scanning, which calls for a hash map. Recency must support moving an arbitrary hit to the most-recent end and removing the least-recent end. A doubly linked list can do both in constant pointer work when the map already provides the node.

The second signal is whether the two structures form one state. The map cannot store only values; it must map each key to its list node. Every real list node must have exactly one map entry, and every map entry must point to exactly one real node in the list. Eviction therefore removes the same key from both structures.

The third signal is pointer discipline. Dummy head and tail nodes make all real nodes interior nodes. Detach and insert need no special cases for the first, last, or only entry. A candidate should be able to state which side is most recent before coding and keep that convention unchanged.

Finally, the interviewer looks for tests that expose order, not just returned values. Updating an existing key at capacity, repeatedly reading one key, using capacity one, and inserting after a miss reveal bugs that a single happy-path example misses.

Questions to Clarify Before Answering

• Does get update recency? In this contract it does. A read-only peek would be a different operation and would not move the node.
• Does updating an existing key consume capacity? No. put changes the value and recency of the same entry; it must not evict another key.
• What does a miss return? This problem uses -1, so values should be constrained accordingly or the API should return an optional value. Here values are non-negative integers and -1 is reserved for a miss.
• Is zero capacity valid? This implementation rejects non-positive capacity. Supporting zero would require every insertion to disappear immediately and changes the constructor contract.
• Must the guarantee be strict worst-case O(1)? Hash tables normally provide expected constant time. A strict worst-case guarantee requires a different lookup structure or stronger assumptions.
• Can a standard ordered map be used? It may be acceptable in production or a short exercise, but the interviewer can still require the underlying linked-list implementation and its invariants.
• Is thread safety required? No. If it is added, remember that get mutates recency, so it is a write operation for synchronization purposes.

30-Second Answer Framework

“I need expected constant-time lookup and recency updates, so I’ll map each key to a node in a doubly linked list. The head side is most recent and the tail side least recent; sentinels make detach and insert uniform. A hit or update moves its node to the front. A new insert over capacity removes tail.prev from both structures. Because the map and list contain the same real nodes, get and put are expected O(1), with O(capacity) space.”

Step-by-Step Deep Answer

A list alone preserves recency, but finding a key or removing an arbitrary entry costs O(n). A map alone finds a value quickly, but it cannot identify the least recently used key without scanning or storing a second ordering structure. An array plus a map still has O(n) shifts or predecessor discovery. The two requirements force a lookup index and a mutable order.

Use this orientation throughout the answer:

head <-> most recent <-> ... <-> least recent <-> tail

The sentinels never enter the map and never count toward capacity. Each real node stores key, value, prev, and next; storing the key is necessary because eviction starts from tail.prev and must delete the matching map entry without a reverse scan.

Four invariants make the implementation reviewable:

1. head.next is the most recently used real node, and tail.prev is the least recently used real node when the cache is nonempty.
2. The map keys and the real list nodes describe the same set of entries, one-to-one.
3. For every adjacent pair, left.next is right and right.prev is left.
4. After each public operation, 0 <= len(nodes) <= capacity.

The implementation keeps pointer manipulation in two helpers because both get and put genuinely reuse it:

class Node:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("capacity must be positive")

        self.capacity = capacity
        self.nodes = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _detach(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _attach_after_head(self, node: Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _mark_recent(self, node: Node) -> None:
        self._detach(node)
        self._attach_after_head(node)

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1

        self._mark_recent(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._mark_recent(node)
            return

        node = Node(key, value)
        self.nodes[key] = node
        self._attach_after_head(node)

        if len(self.nodes) > self.capacity:
            victim = self.tail.prev
            self._detach(victim)
            del self.nodes[victim.key]

The order of pointer assignments in attachafter_head matters. The new node first captures the old first node, then that old node points back to the new node, and only then does head.next change. Overwriting head.next too early can lose the neighbor that still needs its prev updated.

Correctness follows by induction over operations. Initialization satisfies all four invariants. A miss changes nothing. A hit or existing-key update detaches one mapped node and reinserts the same node at the front, so membership and size do not change. A new insertion adds the node to both structures; if size becomes capacity + 1, removing tail.prev from the list and its key from the map restores the one-to-one set and the capacity bound. Positive capacity ensures the victim is a real node.

With a capacity of two, the trace put(1,10), put(2,20), get(1), put(3,30), put(1,15) produces recency orders [1], [2,1], [1,2], [3,1], [1,3]. Key 2 is evicted, while updating key 1 changes its value without evicting key 3.

Under average hash-table performance, each public method performs one lookup plus a fixed number of pointer and map operations, so expected time is O(1). The map and list contain at most capacity real nodes, so space is O(capacity). This is not a strict worst-case hash-table guarantee.

Validation should combine example traces with invariant checks. Test an empty cache miss, rejected zero capacity, capacity one, repeated values under different keys, an update at full capacity, repeated hits, alternating evictions, and a long random operation stream. For the random test, compare results and order with a simple O(n) reference model and after every operation assert reciprocal pointers, no duplicate nodes, map–list equality, and the capacity bound.

An access-ordered map can express the same policy more compactly when libraries are allowed. Java's LinkedHashMap supports access order and an eldest-entry removal hook. That is a useful production option, but it does not replace the interview proof. Also keep exact in-process LRU separate from production eviction: a server may use sampled approximate LRU to reduce global metadata and contention.

High-Quality Sample Answer

“I would first fix the contract: positive capacity, get returns -1 on a miss, and every hit or put updates recency. Updating an existing key does not increase size. The target is expected O(1), based on average hash-table lookup.

A hash map solves key lookup but not eviction order. A doubly linked list solves order and lets me unlink an arbitrary node in constant pointer work, provided I already have that node. I therefore store key -> node in the map and order the nodes from most recent after a dummy head to least recent before a dummy tail. Nodes store their key so tail eviction can also delete the map entry.

The key invariant is that the map and real list nodes are the same set. On a hit, I detach that node and insert it after the head. On an update, I change its value and do the same move. On a new put, I add it to both structures; if size exceeds capacity, I remove tail.prev from both. Sentinels make these operations identical for the first, last, and only entry.

I would test capacity one, an update while full, repeated gets that change the victim, and a miss that must not change order. I would also walk the list after each randomized operation and compare it with a slow reference model. The final complexity is expected O(1) per operation and O(capacity) space.”

Common Mistakes

• Store only values in the map → a hit still needs to search the order structure → map each key directly to its list node.
• Use a singly linked list → the map provides the node but not its predecessor, so arbitrary removal can require a scan → store both prev and next.
• Forget the key inside each node → tail eviction cannot remove the map entry without reverse lookup → store both key and value in the node.
• Treat insertion order as recency → a successful get then fails to change the future victim → move every hit to the most-recent end.
• Evict on an existing-key update → size did not grow, so an unrelated entry disappears → handle update and return before the new-entry capacity check.
• Remove a victim from only one structure → stale map entries or ghost list nodes break later operations → perform eviction symmetrically and test map–list equality.
• Write separate head, tail, and singleton branches → pointer cases multiply and one boundary eventually diverges → use two permanent sentinels.
• Claim strict O(1) → hash tables generally give an expected bound and can degrade under collisions → state the hashing assumption.
• Test only return values → correct values can hide a corrupted order until a later eviction → assert the full recency sequence and pointer invariants.

Follow-Up Questions and Responses

Follow-up 1: How would you make it thread-safe?

get is a write because it changes the list. The simplest correct extension puts one mutex around the entire get or put, keeping the map and list update atomic. Read–write locking does not make ordinary hits readers. Sharding reduces contention, but each shard then has its own LRU order; it no longer implements one exact global LRU unless a shared ordering mechanism is reintroduced.

Follow-up 2: How would you add TTL expiration?

TTL and recency are separate eviction rules. A hit must first reject expired entries, while put may need to remove expired entries before applying the capacity policy. A min-heap of expiration times supports lazy cleanup but adds O(log n) maintenance and stale heap records; a timing wheel changes the precision and implementation. Do not keep claiming both operations are O(1) without redefining the expiration mechanism and bound.

Follow-up 3: Can you provide strict worst-case O(1)?

The linked-list part already has a strict constant number of pointer operations. The lookup part depends on the hash table's guarantees. Achieving strict worst-case constant lookup requires a stronger dictionary model, bounded key universe with direct addressing, or specialized hashing assumptions. In a normal language hash map, describe the result as expected or amortized O(1) according to that implementation's contract.

Follow-up 4: Why not use LinkedHashMap or OrderedDict?

Use the library when its access-order and eviction semantics match the product and manual pointer code adds no value. In an interview, first explain the underlying map and linked-order invariant, then offer the library alternative. Verify whether updating, reading, iteration, and eldest removal count as accesses; similarly named ordered maps do not all share identical recency semantics.

Follow-up 5: Would you use exact LRU in a large cache server?

Not automatically. Maintaining one exact global access order adds metadata writes and a contention point on every hit. A production cache may shard the order, sample candidate keys, or choose LFU when frequency predicts reuse better. Those choices trade exact victim selection for memory and throughput. The interview object remains useful because it makes the exact policy and its invariants testable.