LRU Cache

Q: Can you build an LRU cache with an ordered dictionary?

Yes. A map that keeps insertion order, such as Python's OrderedDict or Java's LinkedHashMap , can replace the list: move a key to the end on every use and evict from the front, still in O(1). Interviewers usually want the list built by hand.

MediumHashing Linked list

+10

Build a cache that holds at most capacity keys. get key returns the key's value, or -1 if it is not cached. put key value stores the value, replacing any older one; if the key is new and the cache is full, it first evicts the least recently used key. A get that finds its key, and every put, counts as a use.

Operation i is ops[i] ("get" or "put") on key keys[i], with value values[i] (0 for a get). Run them in order on an empty cache and return one string each: "null" for a put, the value or "-1" for a get.

Function

lruCacheOps(capacity: integer, ops: string-array, keys: integer-array, values: integer-array) → string-array

capacityinteger: the most keys the cache can hold at once
opsstring-array: the operations, in the order they run
keysinteger-array: the key each operation works on
valuesinteger-array: the value for each put, 0 for each get
Returnsstring-array: one answer per operation, as text

Constraints

1 ≤ capacity ≤ 3000
1 ≤ ops.length ≤ 3000
keys.length == values.length == ops.length
Every ops[i] is get or put.
0 ≤ keys[i] ≤ 10⁹
0 ≤ values[i] ≤ 10⁹ for a put, and values[i] == 0 for a get.

Examples

Input: capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
Output: ["null", "null", "10", "null", "-1", "30"]
Explanation: The get makes key 1 the most recently used, so put 3 evicts key 2: get 2 returns "-1" and get 3 returns "30".

Input: capacity = 2ops = ["put", "put", "put", "put", "get", "get", "get"]keys = [5, 6, 5, 7, 5, 6, 7]values = [1, 2, 3, 4, 0, 0, 0]
Output: ["null", "null", "null", "null", "3", "-1", "4"]
Explanation: The third put updates key 5, which is already cached: nothing is evicted and key 5 becomes the most recently used. So put 7 evicts key 6, not key 5.

Input: capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
Output: ["-1", "null", "0", "null", "-1", "8"]
Explanation: With room for one key, each new key evicts the one before it. The first get misses on an empty cache; key 0 then holds the real value 0 until put 8 evicts it.

Follow-up

How would you change the cache to evict the least frequently used key instead, breaking ties by the least recent use, still in O(1) per operation?

Solution

A get must find a key fast, and an eviction must find the least recently used key fast. A hash map does the first, a list kept in order of use does the second. Use both: map each key to its node in a doubly linked list ordered by use.

Scan a table of entries with last-used times

Intuition

Store up to capacity entries in arrays: key, value, and a last-use stamp from a counter that goes up on every operation. A new key in a full cache overwrites the entry with the smallest stamp, the key unused longest. In the first example, at put 3 key 1 has stamp 3 and key 2 has stamp 2, so key 2 goes.

Every operation scans up to capacity entries: O(n × capacity) for n operations, millions of comparisons at 3,000 operations on a cache of 1,500 keys.

Algorithm

Keep arrays keys, values and used, a fill count, and a clock at 0.
Each operation adds 1 to the clock and scans the filled entries for its key.
get: on a miss return -1; on a hit set used to the clock and return the value.
put: on a hit, store the value and the clock. On a miss, write key, value and clock into a free entry, or into the entry with the smallest used.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        # Entry i holds keys[i] -> values[i] and was last used at time used[i].
        self.keys = [0] * capacity
        self.values = [0] * capacity
        self.used = [0] * capacity
        self.size = 0
        self.time = 0

    def _find(self, key):
        for i in range(self.size):
            if self.keys[i] == key:
                return i
        return -1

    def get(self, key):
        self.time += 1
        i = self._find(key)
        if i == -1:
            return -1
        self.used[i] = self.time
        return self.values[i]

    def put(self, key, value):
        self.time += 1
        i = self._find(key)
        if i == -1:
            if self.size < self.capacity:
                i = self.size
                self.size += 1
            else:
                # Full: scan for the entry used longest ago and take its place.
                i = 0
                for j in range(1, self.capacity):
                    if self.used[j] < self.used[i]:
                        i = j
            self.keys[i] = key
        self.values[i] = value
        self.used[i] = self.time

def lruCacheOps(capacity, ops, keys, values):
    cache = LRUCache(capacity)
    result = []
    for op, key, value in zip(ops, keys, values):
        if op == "put":
            cache.put(key, value)
            result.append("null")
        else:
            result.append(str(cache.get(key)))
    return result

Hash map plus a doubly linked list

Intuition

Each list node links to both neighbours, so with the node in hand you can unlink it, or insert it at the front, by changing four links. The map hands you the node, so no operation walks the list.

A get hit, or a put of a cached key, moves the node to the front. A new key in a full cache removes the back node and deletes its key from the map, which is why each node stores its own key. Sentinel nodes head and tail stay at the ends, so unlink and insert never check for a missing neighbour. Each operation is one lookup plus a few link changes: O(1).

Algorithm

Link sentinels head and tail; start an empty map from key to node.
get key: return -1 if the key is not in the map; otherwise move its node after head and return its value.
put of a cached key: store the value and move the node after head.
put of a new key: if the map holds capacity keys, unlink the node before tail and delete its key from the map. Insert a new node after head and map the key to it.

class ListNode:
    __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):
        self.capacity = capacity
        self.nodes = {}            # key -> its node in the list
        # Sentinels: head.next is the most recently used node,
        # tail.prev the least recently used one.
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _unlink(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _push_front(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.nodes.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value):
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
        else:
            if len(self.nodes) == self.capacity:
                # Full: drop the least recently used node.
                oldest = self.tail.prev
                self._unlink(oldest)
                del self.nodes[oldest.key]
            node = ListNode(key, value)
            self.nodes[key] = node
        self._push_front(node)

def lruCacheOps(capacity, ops, keys, values):
    cache = LRUCache(capacity)
    result = []
    for op, key, value in zip(ops, keys, values):
        if op == "put":
            cache.put(key, value)
            result.append("null")
        else:
            result.append(str(cache.get(key)))
    return result

Pitfalls and edge cases

Not moving a key to the front on a get hit. In the first example, put 3 would then evict key 1, not key 2.
Evicting before checking whether the key is cached. With capacity 2, put 1, put 2, put 2 would throw out key 1.
Unlinking a node but leaving its key in the map, or the reverse. The map then returns a detached node, and moving it corrupts its old neighbours' links.
Treating a stored 0 as a miss. In the third example, get 0 must return "0".

Frequently asked questions3

What is the time complexity of an LRU cache?

With a hash map and a doubly linked list, get and put both run in O(1): one lookup plus a few link changes. The space is O(capacity), one node and one map entry per key.

Why does an LRU cache use a doubly linked list?

The cache moves keys from anywhere in the order to the front and drops the key at the back. A doubly linked list does both with a few link changes, because each node knows the node before it. A singly linked list needs a walk from the head to find that node, which is O(capacity).

Can you build an LRU cache with an ordered dictionary?

Yes. A map that keeps insertion order, such as Python's OrderedDict or Java's LinkedHashMap, can replace the list: move a key to the end on every use and evict from the front, still in O(1). Interviewers usually want the list built by hand.

def lruCacheOps(capacity, ops, keys, values):
    # Write code here

Test #1

Test #2

Test #3

Arguments

capacity = 2
ops = ["put", "put", "get", "put", "get", "get"]
keys = [1, 2, 1, 3, 2, 3]
values = [10, 20, 0, 30, 0, 0]

Expected Output

["null", "null", "10", "null", "-1", "30"]