Implement an LRU cache with O(1) get and set: which data structures, and what does the eviction order look like?

13.11.3 · L3 · Interview

Predict first

What is the recency order and which key is evicted?

struct LRUCache<Key: Hashable, Value> {
    private final class Node {
        var key: Key; var value: Value; var prev: Node?; var next: Node?
        init(_ k: Key, _ v: Value) { key = k; value = v }
    }
    private var map: [Key: Node] = [:]
    private var head: Node?, tail: Node?
    let capacity: Int
    init(capacity: Int) { self.capacity = capacity }

    private mutating func unlink(_ n: Node) {
        n.prev?.next = n.next; n.next?.prev = n.prev
        if head === n { head = n.next }
        if tail === n { tail = n.prev }
        n.prev = nil; n.next = nil
    }
    private mutating func pushFront(_ n: Node) {
        n.next = head; head?.prev = n; head = n
        if tail == nil { tail = n }
    }
    mutating func get(_ k: Key) -> Value? {
        guard let n = map[k] else { return nil }
        unlink(n); pushFront(n)
        return n.value
    }
    mutating func set(_ k: Key, _ v: Value) {
        if let n = map[k] { n.value = v; unlink(n); pushFront(n); return }
        let n = Node(k, v)
        map[k] = n; pushFront(n)
        if map.count > capacity, let last = tail { unlink(last); map[last.key] = nil }
    }
    var keysByRecency: [Key] {
        var r: [Key] = []; var n = head
        while let c = n { r.append(c.key); n = c.next }
        return r
    }
}

var cache = LRUCache<String, Int>(capacity: 3)
cache.set("a", 1); cache.set("b", 2); cache.set("c", 3)
_ = cache.get("a")
cache.set("d", 4)
print("order:", cache.keysByRecency)
print("b evicted:", cache.get("b") == nil, "| a kept:", cache.get("a") == 1)
cache.set("c", 30)
print("after update:", cache.keysByRecency, cache.get("c") ?? -1)

order: ["d", "a", "c"] / b evicted: true | a kept: true / after update: ["c", "a", "d"] 30
order: ["a", "b", "c"]
order: ["d", "c", "b"]

Mental model. A bookshelf at the front of a library: every time a book is used it goes back at the left end, and when the shelf is full the book at the far right end is sent to the stacks.

A least-recently-used cache needs two operations in constant time: find an entry by key, and move an entry to the “most recent” position or remove the “least recent” one. A dictionary alone finds fast but cannot order; a list orders but cannot find fast. The classic answer combines them: a dictionary from key to node plus a doubly linked list ordered by recency (head = most recent, tail = least recent). get looks up the node, unlinks it and pushes it to the front; set updates and moves an existing node, or inserts a new one at the front and, if the count exceeds the capacity, unlinks the tail and removes its key from the dictionary. The check fills a capacity-3 cache with a, b, c, reads a (so a is newest), then adds d: the order is ["d", "a", "c"] and b, the least recently used, was evicted; updating c moves it to the front.

Production caches add: thread safety (a lock or an actor around every operation, since even get mutates the order), cost-based limits (evict by bytes, not count; NSCache offers countLimit and totalCostLimit but gives no ordering guarantee and may evict at any time, and it responds to memory warnings), time-to-live (store an expiry and treat expired entries as misses), and metrics (hit rate, evictions). The interview traps: forgetting to update head and tail when unlinking, evicting from the wrong end, and leaking through reference cycles (use unowned or weak for the back pointer in a class-based list, or an index-based list in an array). Mention LFU and ARC-style alternatives for scan-heavy workloads, and that for images the right unit is decoded bytes (Q327, Q338).

Reading a refreshes it, so the least recently used key (b) is evicted when d arrives.

Common traps

Not moving an entry to the front on get. Then it is FIFO, not LRU.
Forgetting to update tail when removing the last node. The next eviction removes a dangling node.

They might follow up with

What is the complexity? O(1) for get and set, O(n) memory.
How do I make it safe across threads? Wrap it in an actor or guard every call with a lock; do not expose the structure.

Implement an LRU cache with O(1) get and set: which data structures, and what does the eviction order look like?

Predict first

Common traps

They might follow up with

Related questions