#98 · Design

LRU Cache

Design a data structure for a Least Recently Used cache with get(key) and put(key, value) running in O(1) average time. When the capacity is exceeded, evict the least recently used key.

MediumLeetCode

Current node
Link just rewired
Done / in result
Marked
Rejected
Dummy head

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Hash map (key → node)

Finds the entry for a key in O(1) and, if the value is the list node itself, gives direct access to the position in the recency order, so no searching is needed.

Memory layout

A hash table with at most capacity entries; each value is a pointer or index of a list node.

Operation	Cost
lookup / insert / delete	O(1) average

Doubly linked list with dummy ends

Keeps entries ordered by recency: the node after the head dummy is most recent, the node before the tail dummy is the next to evict. A node knows both neighbours, so it can be removed in O(1) without a search; dummy nodes make insertion and removal uniform.

Memory layout

Nodes with key, value, prev and next. An array-backed version stores them as parallel arrays and links by index.

Operation	Cost
unlink / insert at front / read tail	O(1)

Free list of slots (array version)

With all nodes preallocated in arrays, a stack of unused slot numbers replaces allocation and garbage collection: evicting returns a slot, inserting takes one.

Memory layout

An integer stack of at most capacity entries.

Operation	Cost
push / pop	O(1)

Why it fits

Each of the two needs (find by key, reorder by recency) has a structure that does it in O(1); the trick is wiring them together so each points into the other.
A singly linked list or an array cannot remove an arbitrary node in O(1); the back pointer of a doubly linked list can.
The hash map stores nodes (not values) so a hit leads directly to the node that must be moved to the front.

Why alternatives degrade

Array of entries:: Finding and reordering costs O(n) per operation.
Hash map + array of keys:: Lookups are fast but moving a key to the front shifts the array: O(n).
Min-heap by timestamp:: Updating a timestamp on every hit costs O(log n), and a heap cannot delete by key without extra indexing.

Four approaches, from naive to production

1 · beginner

Array of entries, scan on every call

time O(n) per operationspace O(capacity)

Keep [key, value] pairs in an array ordered by recency. get and put scan for the key, remove it, and re-insert at the front; when full, drop the last entry.

class LRUCache {
    list<pair<int, int>> entries; // front = most recently used
    int capacity;
public:
    LRUCache(int capacity) : capacity(capacity) {}
    int get(int key) {
        auto it = find_if(entries.begin(), entries.end(), [&](const pair<int, int>& e) { return e.first == key; });
        if (it == entries.end()) return -1;
        pair<int, int> entry = *it; entries.erase(it);
        entries.push_front(entry);
        return entry.second;
    }
    void put(int key, int value) {
        auto it = find_if(entries.begin(), entries.end(), [&](const pair<int, int>& e) { return e.first == key; });
        if (it != entries.end()) entries.erase(it);
        else if ((int)entries.size() == capacity) entries.pop_back();
        entries.push_front({key, value});
    }
};

class LRUCache {
    private List<int[]> entries = new ArrayList<>(); // index 0 = most recently used
    private int capacity;
    public LRUCache(int capacity) { this.capacity = capacity; }
    private int indexOf(int key) {
        for (int i = 0; i < entries.size(); i++) if (entries.get(i)[0] == key) return i;
        return -1;
    }
    public int get(int key) {
        int i = indexOf(key);
        if (i == -1) return -1;
        int[] entry = entries.remove(i);
        entries.add(0, entry);
        return entry[1];
    }
    public void put(int key, int value) {
        int i = indexOf(key);
        if (i != -1) entries.remove(i);
        else if (entries.size() == capacity) entries.remove(entries.size() - 1);
        entries.add(0, new int[]{key, value});
    }
}

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.entries = []  # index 0 = most recently used
    def _index_of(self, key):
        for i, e in enumerate(self.entries):
            if e[0] == key: return i
        return -1
    def get(self, key):
        i = self._index_of(key)
        if i == -1: return -1
        entry = self.entries.pop(i)
        self.entries.insert(0, entry)
        return entry[1]
    def put(self, key, value):
        i = self._index_of(key)
        if i != -1: self.entries.pop(i)
        elif len(self.entries) == self.capacity: self.entries.pop()
        self.entries.insert(0, [key, value])

class LRUCache {
  private entries: [number, number][] = [];
  constructor(private capacity: number) {}
  get(key: number): number {
    const i = this.entries.findIndex((e) => e[0] === key);
    if (i === -1) return -1;
    const [entry] = this.entries.splice(i, 1);
    this.entries.unshift(entry);
    return entry[1];
  }
  put(key: number, value: number): void {
    const i = this.entries.findIndex((e) => e[0] === key);
    if (i !== -1) this.entries.splice(i, 1);
    else if (this.entries.length === this.capacity) this.entries.pop();
    this.entries.unshift([key, value]);
  }
}

Flaws & bottlenecks

Every call scans the array and shifts elements: O(n).
Capacity 10⁵ with 10⁵ operations is about 10¹⁰ steps.
No separate fast path for misses (they still scan everything).

Interviewer cross-questions

Why order by recency instead of storing timestamps?

Say: The position encodes recency, so the victim is simply the last element; timestamps would need a scan or a heap to find the oldest.

Does put on an existing key count as a use?

Say: Yes: it updates the value and makes the key the most recently used, as in this code.

How do you make lookups fast?

Say: Add a hash map from key to value (or node).

2 · intermediate

Hash map for values + array for recency

time O(1) lookup, O(n) reorderspace O(capacity)

A map answers get hits and misses in O(1) and holds the values; a separate array of keys records recency. touch() finds the key in the array, removes it and puts it at the front.

class LRUCache {
    unordered_map<int, int> values;
    list<int> order; // front = most recently used
    int capacity;
    void touch(int key) {
        auto it = find(order.begin(), order.end(), key);
        if (it != order.end()) order.erase(it);
        order.push_front(key);
    }
public:
    LRUCache(int capacity) : capacity(capacity) {}
    int get(int key) {
        if (!values.count(key)) return -1;
        touch(key);
        return values[key];
    }
    void put(int key, int value) {
        if (!values.count(key) && (int)values.size() == capacity) {
            int victim = order.back(); order.pop_back();
            values.erase(victim);
        }
        values[key] = value;
        touch(key);
    }
};

class LRUCache {
    private Map<Integer, Integer> values = new HashMap<>();
    private List<Integer> order = new ArrayList<>(); // index 0 = most recently used
    private int capacity;
    public LRUCache(int capacity) { this.capacity = capacity; }
    private void touch(int key) {
        int i = order.indexOf(key);
        if (i != -1) order.remove(i);
        order.add(0, key);
    }
    public int get(int key) {
        if (!values.containsKey(key)) return -1;
        touch(key);
        return values.get(key);
    }
    public void put(int key, int value) {
        if (!values.containsKey(key) && values.size() == capacity) {
            int victim = order.remove(order.size() - 1);
            values.remove(victim);
        }
        values.put(key, value);
        touch(key);
    }
}

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.values = {}
        self.order = []  # index 0 = most recently used
    def _touch(self, key):
        i = self.order.index(key) if key in self.order else -1
        if i != -1: self.order.pop(i)
        self.order.insert(0, key)
    def get(self, key):
        if key not in self.values: return -1
        self._touch(key)
        return self.values[key]
    def put(self, key, value):
        if key not in self.values and len(self.values) == self.capacity:
            victim = self.order.pop()
            del self.values[victim]
        self.values[key] = value
        self._touch(key)

class LRUCache {
  private values = new Map<number, number>();
  private order: number[] = [];
  constructor(private capacity: number) {}
  private touch(key: number): void {
    const i = this.order.indexOf(key);
    if (i !== -1) this.order.splice(i, 1);
    this.order.unshift(key);
  }
  get(key: number): number {
    if (!this.values.has(key)) return -1;
    this.touch(key);
    return this.values.get(key)!;
  }
  put(key: number, value: number): void {
    if (!this.values.has(key) && this.values.size === this.capacity) {
      const victim = this.order.pop()!;
      this.values.delete(victim);
    }
    this.values.set(key, value);
    this.touch(key);
  }
}

Flaws & bottlenecks

touch() still searches and shifts the order array: O(n).
Two structures that must be kept in sync (map and order).
A miss is O(1), but a hit is O(n).

Interviewer cross-questions

Why is a miss cheaper than a hit?

Say: A miss ends at the hash map check; a hit must also move the key in the order array.

How can the reorder be O(1)?

Say: Replace the order array by a doubly linked list and store the list node in the map, so no search is needed.

Could a language-provided ordered map do this?

Say: Yes: structures that keep insertion order (JavaScript Map, Python OrderedDict, Java LinkedHashMap) are exactly this combination internally.

3 · advanced

Hash map + doubly linked list

time O(1) per operationspace O(capacity)

The map stores key → node. The list holds nodes from most to least recent between dummy head and tail. get unlinks the node and re-inserts it after the head; put evicts tail.prev when full.

struct Node {
    int key, value; Node *prev, *next;
    Node(int k = 0, int v = 0) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
class LRUCache {
    unordered_map<int, Node*> map_;
    Node* head = new Node();
    Node* tail = new Node();
    int capacity;
    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void addFront(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
public:
    LRUCache(int capacity) : capacity(capacity) {
        head->next = tail;
        tail->prev = head;
    }
    int get(int key) {
        auto it = map_.find(key);
        Node* node = it == map_.end() ? nullptr : it->second;
        if (!node) return -1;
        remove(node);
        addFront(node);
        return node->value;
    }
    void put(int key, int value) {
        auto it = map_.find(key);
        Node* existing = it == map_.end() ? nullptr : it->second;
        if (existing) {
            existing->value = value;
            remove(existing);
            addFront(existing);
            return;
        }
        if ((int)map_.size() == capacity) {
            Node* victim = tail->prev;
            remove(victim);
            map_.erase(victim->key);
            delete victim;
        }
        Node* node = new Node(key, value);
        map_[key] = node;
        addFront(node);
    }
};

class Node {
    int key, value; Node prev, next;
    Node(int key, int value) { this.key = key; this.value = value; }
}
class LRUCache {
    private Map<Integer, Node> map = new HashMap<>();
    private Node head = new Node(0, 0);
    private Node tail = new Node(0, 0);
    private int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void addFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        remove(node);
        addFront(node);
        return node.value;
    }
    public void put(int key, int value) {
        Node existing = map.get(key);
        if (existing != null) {
            existing.value = value;
            remove(existing);
            addFront(existing);
            return;
        }
        if (map.size() == capacity) {
            Node victim = tail.prev;
            remove(victim);
            map.remove(victim.key);
        }
        Node node = new Node(key, value);
        map.put(key, node);
        addFront(node);
    }
}

class Node:
    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.map = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
    def get(self, key):
        node = self.map.get(key)
        if node is None: return -1
        self._remove(node)
        self._add_front(node)
        return node.value
    def put(self, key, value):
        existing = self.map.get(key)
        if existing is not None:
            existing.value = value
            self._remove(existing)
            self._add_front(existing)
            return
        if len(self.map) == self.capacity:
            victim = self.tail.prev
            self._remove(victim)
            del self.map[victim.key]
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)

class Node {
  constructor(public key = 0, public value = 0, public prev: Node | null = null, public next: Node | null = null) {}
}
class LRUCache {
  private map = new Map<number, Node>();
  private head = new Node();
  private tail = new Node();
  constructor(private capacity: number) {
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  private remove(node: Node): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }
  private addFront(node: Node): void {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }
  get(key: number): number {
    const node = this.map.get(key);
    if (!node) return -1;
    this.remove(node);
    this.addFront(node);
    return node.value;
  }
  put(key: number, value: number): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.remove(existing);
      this.addFront(existing);
      return;
    }
    if (this.map.size === this.capacity) {
      const victim = this.tail.prev!;
      this.remove(victim);
      this.map.delete(victim.key);
    }
    const node = new Node(key, value);
    this.map.set(key, node);
    this.addFront(node);
  }
}

Flaws & bottlenecks

One heap-allocated node per entry: allocation and garbage-collection cost.
Pointer surgery is easy to get wrong (order of the four assignments).
Not thread safe: concurrent hits would race on the list.

Interviewer cross-questions

Why dummy head and tail nodes?

Say: They guarantee every real node has a prev and a next, so remove and addFront need no null checks or special cases for the first and last node.

Why store the key inside the node?

Say: When the tail node is evicted we must also delete its key from the hash map; the node tells us which key that is.

How would you make it thread safe?

Say: Guard every get and put with one lock (both mutate the list), or shard the cache by key hash so each shard has its own lock.

4 · expert

Array-backed list with a free list

time O(1) per operationspace O(capacity), allocated once

Store nodes in preallocated arrays (key, value, prev, next) addressed by slot number; link them by index; recycle slots through a free stack. Clamp non-positive capacity so put does nothing and get always misses.

class LRUCache {
    unordered_map<int, int> slotOf;
    vector<int> keyAt;
    vector<int> valAt;
    vector<int> prev;
    vector<int> next;
    vector<int> freeSlots;
    int head, tail;
    int capacity;
    void unlink(int s) {
        next[prev[s]] = next[s];
        prev[next[s]] = prev[s];
    }
    void linkFront(int s) {
        int first = next[head];
        next[s] = first;
        prev[s] = head;
        prev[first] = s;
        next[head] = s;
    }
public:
    LRUCache(int capacity) : capacity(capacity) {
        int slots = max(capacity, 0) + 2;
        keyAt.assign(slots, 0);
        valAt.assign(slots, 0);
        prev.assign(slots, -1);
        next.assign(slots, -1);
        head = slots - 2;
        tail = slots - 1;
        next[head] = tail;
        prev[tail] = head;
        for (int s = slots - 3; s >= 0; s--) freeSlots.push_back(s);
    }
    int get(int key) {
        auto it = slotOf.find(key);
        int s = it == slotOf.end() ? -1 : it->second;
        if (s == -1) return -1;
        unlink(s);
        linkFront(s);
        return valAt[s];
    }
    void put(int key, int value) {
        if (capacity <= 0) return;
        auto it = slotOf.find(key);
        int s = it == slotOf.end() ? -1 : it->second;
        if (s != -1) {
            valAt[s] = value;
            unlink(s);
            linkFront(s);
            return;
        }
        if (freeSlots.empty()) {
            int victim = prev[tail];
            unlink(victim);
            slotOf.erase(keyAt[victim]);
            freeSlots.push_back(victim);
        }
        s = freeSlots.back(); freeSlots.pop_back();
        keyAt[s] = key;
        valAt[s] = value;
        slotOf[key] = s;
        linkFront(s);
    }
};

class LRUCache {
    private Map<Integer, Integer> slotOf = new HashMap<>();
    private int[] keyAt;
    private int[] valAt;
    private int[] prev;
    private int[] next;
    private ArrayDeque<Integer> free = new ArrayDeque<>();
    private int head, tail;
    private int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        int slots = Math.max(capacity, 0) + 2;
        keyAt = new int[slots];
        valAt = new int[slots];
        prev = new int[slots]; Arrays.fill(prev, -1);
        next = new int[slots]; Arrays.fill(next, -1);
        head = slots - 2;
        tail = slots - 1;
        next[head] = tail;
        prev[tail] = head;
        for (int s = slots - 3; s >= 0; s--) free.push(s);
    }
    private void unlink(int s) {
        next[prev[s]] = next[s];
        prev[next[s]] = prev[s];
    }
    private void linkFront(int s) {
        int first = next[head];
        next[s] = first;
        prev[s] = head;
        prev[first] = s;
        next[head] = s;
    }
    public int get(int key) {
        Integer s = slotOf.get(key);
        if (s == null) return -1;
        unlink(s);
        linkFront(s);
        return valAt[s];
    }
    public void put(int key, int value) {
        if (capacity <= 0) return;
        Integer s = slotOf.get(key);
        if (s != null) {
            valAt[s] = value;
            unlink(s);
            linkFront(s);
            return;
        }
        if (free.isEmpty()) {
            int victim = prev[tail];
            unlink(victim);
            slotOf.remove(keyAt[victim]);
            free.push(victim);
        }
        s = free.pop();
        keyAt[s] = key;
        valAt[s] = value;
        slotOf.put(key, s);
        linkFront(s);
    }
}

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        slots = max(capacity, 0) + 2
        self.slot_of = {}
        self.key_at = [0] * slots
        self.val_at = [0] * slots
        self.prev = [-1] * slots
        self.next = [-1] * slots
        self.head = slots - 2
        self.tail = slots - 1
        self.next[self.head] = self.tail
        self.prev[self.tail] = self.head
        self.free = list(range(slots - 3, -1, -1))
    def _unlink(self, s):
        self.next[self.prev[s]] = self.next[s]
        self.prev[self.next[s]] = self.prev[s]
    def _link_front(self, s):
        first = self.next[self.head]
        self.next[s] = first
        self.prev[s] = self.head
        self.prev[first] = s
        self.next[self.head] = s
    def get(self, key):
        s = self.slot_of.get(key)
        if s is None: return -1
        self._unlink(s)
        self._link_front(s)
        return self.val_at[s]
    def put(self, key, value):
        if self.capacity <= 0: return
        s = self.slot_of.get(key)
        if s is not None:
            self.val_at[s] = value
            self._unlink(s)
            self._link_front(s)
            return
        if not self.free:
            victim = self.prev[self.tail]
            self._unlink(victim)
            del self.slot_of[self.key_at[victim]]
            self.free.append(victim)
        s = self.free.pop()
        self.key_at[s] = key
        self.val_at[s] = value
        self.slot_of[key] = s
        self._link_front(s)

class LRUCache {
  private slotOf = new Map<number, number>();
  private keyAt: number[];
  private valAt: number[];
  private prev: number[];
  private next: number[];
  private free: number[] = [];
  private readonly head: number;
  private readonly tail: number;
  constructor(private capacity: number) {
    const slots = Math.max(capacity, 0) + 2;
    this.keyAt = new Array<number>(slots).fill(0);
    this.valAt = new Array<number>(slots).fill(0);
    this.prev = new Array<number>(slots).fill(-1);
    this.next = new Array<number>(slots).fill(-1);
    this.head = slots - 2;
    this.tail = slots - 1;
    this.next[this.head] = this.tail;
    this.prev[this.tail] = this.head;
    for (let s = slots - 3; s >= 0; s--) this.free.push(s);
  }
  private unlink(s: number): void {
    this.next[this.prev[s]] = this.next[s];
    this.prev[this.next[s]] = this.prev[s];
  }
  private linkFront(s: number): void {
    const first = this.next[this.head];
    this.next[s] = first;
    this.prev[s] = this.head;
    this.prev[first] = s;
    this.next[this.head] = s;
  }
  get(key: number): number {
    const s = this.slotOf.get(key);
    if (s === undefined) return -1;
    this.unlink(s);
    this.linkFront(s);
    return this.valAt[s];
  }
  put(key: number, value: number): void {
    if (this.capacity <= 0) return;
    let s = this.slotOf.get(key);
    if (s !== undefined) {
      this.valAt[s] = value;
      this.unlink(s);
      this.linkFront(s);
      return;
    }
    if (this.free.length === 0) {
      const victim = this.prev[this.tail];
      this.unlink(victim);
      this.slotOf.delete(this.keyAt[victim]);
      this.free.push(victim);
    }
    s = this.free.pop()!;
    this.keyAt[s] = key;
    this.valAt[s] = value;
    this.slotOf.set(key, s);
    this.linkFront(s);
  }
}

Flaws & bottlenecks

More code and index bookkeeping than the pointer version.
Fixed capacity: resizing would need a rebuild.
The hash map is still a general-purpose map; an open-addressing table would remove the last allocations.

Interviewer cross-questions

Why use arrays instead of node objects?

Say: No allocation or GC pauses on the hot path, better cache locality, and a compact, predictable memory footprint.

What does the free list do?

Say: It holds slot numbers not currently used. Eviction pushes the victim's slot; insertion pops one, so exactly capacity slots are ever needed.

What are the edge cases?

Say: Capacity 1 (every new key evicts the previous), capacity 0 (nothing is stored), updating an existing key (no eviction), and reading a key just after it was evicted (miss).

Synchronized code walkthrough

Showing: Array of entries, scan on every call — shares the player above; click any step to jump.

class LRUCache {
    list<pair<int, int>> entries; // front = most recently used
    int capacity;
public:
    LRUCache(int capacity) : capacity(capacity) {}
    int get(int key) {
        auto it = find_if(entries.begin(), entries.end(), [&](const pair<int, int>& e) { return e.first == key; });
        if (it == entries.end()) return -1;
        pair<int, int> entry = *it; entries.erase(it);
        entries.push_front(entry);
        return entry.second;
    }
    void put(int key, int value) {
        auto it = find_if(entries.begin(), entries.end(), [&](const pair<int, int>& e) { return e.first == key; });
        if (it != entries.end()) entries.erase(it);
        else if ((int)entries.size() == capacity) entries.pop_back();
        entries.push_front({key, value});
    }
};

class LRUCache {
    private List<int[]> entries = new ArrayList<>(); // index 0 = most recently used
    private int capacity;
    public LRUCache(int capacity) { this.capacity = capacity; }
    private int indexOf(int key) {
        for (int i = 0; i < entries.size(); i++) if (entries.get(i)[0] == key) return i;
        return -1;
    }
    public int get(int key) {
        int i = indexOf(key);
        if (i == -1) return -1;
        int[] entry = entries.remove(i);
        entries.add(0, entry);
        return entry[1];
    }
    public void put(int key, int value) {
        int i = indexOf(key);
        if (i != -1) entries.remove(i);
        else if (entries.size() == capacity) entries.remove(entries.size() - 1);
        entries.add(0, new int[]{key, value});
    }
}

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.entries = []  # index 0 = most recently used
    def _index_of(self, key):
        for i, e in enumerate(self.entries):
            if e[0] == key: return i
        return -1
    def get(self, key):
        i = self._index_of(key)
        if i == -1: return -1
        entry = self.entries.pop(i)
        self.entries.insert(0, entry)
        return entry[1]
    def put(self, key, value):
        i = self._index_of(key)
        if i != -1: self.entries.pop(i)
        elif len(self.entries) == self.capacity: self.entries.pop()
        self.entries.insert(0, [key, value])

class LRUCache {
  private entries: [number, number][] = [];
  constructor(private capacity: number) {}
  get(key: number): number {
    const i = this.entries.findIndex((e) => e[0] === key);
    if (i === -1) return -1;
    const [entry] = this.entries.splice(i, 1);
    this.entries.unshift(entry);
    return entry[1];
  }
  put(key: number, value: number): void {
    const i = this.entries.findIndex((e) => e[0] === key);
    if (i !== -1) this.entries.splice(i, 1);
    else if (this.entries.length === this.capacity) this.entries.pop();
    this.entries.unshift([key, value]);
  }
}

class LRUCache {
    unordered_map<int, int> values;
    list<int> order; // front = most recently used
    int capacity;
    void touch(int key) {
        auto it = find(order.begin(), order.end(), key);
        if (it != order.end()) order.erase(it);
        order.push_front(key);
    }
public:
    LRUCache(int capacity) : capacity(capacity) {}
    int get(int key) {
        if (!values.count(key)) return -1;
        touch(key);
        return values[key];
    }
    void put(int key, int value) {
        if (!values.count(key) && (int)values.size() == capacity) {
            int victim = order.back(); order.pop_back();
            values.erase(victim);
        }
        values[key] = value;
        touch(key);
    }
};

class LRUCache {
    private Map<Integer, Integer> values = new HashMap<>();
    private List<Integer> order = new ArrayList<>(); // index 0 = most recently used
    private int capacity;
    public LRUCache(int capacity) { this.capacity = capacity; }
    private void touch(int key) {
        int i = order.indexOf(key);
        if (i != -1) order.remove(i);
        order.add(0, key);
    }
    public int get(int key) {
        if (!values.containsKey(key)) return -1;
        touch(key);
        return values.get(key);
    }
    public void put(int key, int value) {
        if (!values.containsKey(key) && values.size() == capacity) {
            int victim = order.remove(order.size() - 1);
            values.remove(victim);
        }
        values.put(key, value);
        touch(key);
    }
}

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.values = {}
        self.order = []  # index 0 = most recently used
    def _touch(self, key):
        i = self.order.index(key) if key in self.order else -1
        if i != -1: self.order.pop(i)
        self.order.insert(0, key)
    def get(self, key):
        if key not in self.values: return -1
        self._touch(key)
        return self.values[key]
    def put(self, key, value):
        if key not in self.values and len(self.values) == self.capacity:
            victim = self.order.pop()
            del self.values[victim]
        self.values[key] = value
        self._touch(key)

class LRUCache {
  private values = new Map<number, number>();
  private order: number[] = [];
  constructor(private capacity: number) {}
  private touch(key: number): void {
    const i = this.order.indexOf(key);
    if (i !== -1) this.order.splice(i, 1);
    this.order.unshift(key);
  }
  get(key: number): number {
    if (!this.values.has(key)) return -1;
    this.touch(key);
    return this.values.get(key)!;
  }
  put(key: number, value: number): void {
    if (!this.values.has(key) && this.values.size === this.capacity) {
      const victim = this.order.pop()!;
      this.values.delete(victim);
    }
    this.values.set(key, value);
    this.touch(key);
  }
}

struct Node {
    int key, value; Node *prev, *next;
    Node(int k = 0, int v = 0) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
class LRUCache {
    unordered_map<int, Node*> map_;
    Node* head = new Node();
    Node* tail = new Node();
    int capacity;
    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void addFront(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
public:
    LRUCache(int capacity) : capacity(capacity) {
        head->next = tail;
        tail->prev = head;
    }
    int get(int key) {
        auto it = map_.find(key);
        Node* node = it == map_.end() ? nullptr : it->second;
        if (!node) return -1;
        remove(node);
        addFront(node);
        return node->value;
    }
    void put(int key, int value) {
        auto it = map_.find(key);
        Node* existing = it == map_.end() ? nullptr : it->second;
        if (existing) {
            existing->value = value;
            remove(existing);
            addFront(existing);
            return;
        }
        if ((int)map_.size() == capacity) {
            Node* victim = tail->prev;
            remove(victim);
            map_.erase(victim->key);
            delete victim;
        }
        Node* node = new Node(key, value);
        map_[key] = node;
        addFront(node);
    }
};

class Node {
    int key, value; Node prev, next;
    Node(int key, int value) { this.key = key; this.value = value; }
}
class LRUCache {
    private Map<Integer, Node> map = new HashMap<>();
    private Node head = new Node(0, 0);
    private Node tail = new Node(0, 0);
    private int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void addFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        remove(node);
        addFront(node);
        return node.value;
    }
    public void put(int key, int value) {
        Node existing = map.get(key);
        if (existing != null) {
            existing.value = value;
            remove(existing);
            addFront(existing);
            return;
        }
        if (map.size() == capacity) {
            Node victim = tail.prev;
            remove(victim);
            map.remove(victim.key);
        }
        Node node = new Node(key, value);
        map.put(key, node);
        addFront(node);
    }
}

class Node:
    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.map = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
    def get(self, key):
        node = self.map.get(key)
        if node is None: return -1
        self._remove(node)
        self._add_front(node)
        return node.value
    def put(self, key, value):
        existing = self.map.get(key)
        if existing is not None:
            existing.value = value
            self._remove(existing)
            self._add_front(existing)
            return
        if len(self.map) == self.capacity:
            victim = self.tail.prev
            self._remove(victim)
            del self.map[victim.key]
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)

class Node {
  constructor(public key = 0, public value = 0, public prev: Node | null = null, public next: Node | null = null) {}
}
class LRUCache {
  private map = new Map<number, Node>();
  private head = new Node();
  private tail = new Node();
  constructor(private capacity: number) {
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  private remove(node: Node): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }
  private addFront(node: Node): void {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }
  get(key: number): number {
    const node = this.map.get(key);
    if (!node) return -1;
    this.remove(node);
    this.addFront(node);
    return node.value;
  }
  put(key: number, value: number): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.remove(existing);
      this.addFront(existing);
      return;
    }
    if (this.map.size === this.capacity) {
      const victim = this.tail.prev!;
      this.remove(victim);
      this.map.delete(victim.key);
    }
    const node = new Node(key, value);
    this.map.set(key, node);
    this.addFront(node);
  }
}

class LRUCache {
    unordered_map<int, int> slotOf;
    vector<int> keyAt;
    vector<int> valAt;
    vector<int> prev;
    vector<int> next;
    vector<int> freeSlots;
    int head, tail;
    int capacity;
    void unlink(int s) {
        next[prev[s]] = next[s];
        prev[next[s]] = prev[s];
    }
    void linkFront(int s) {
        int first = next[head];
        next[s] = first;
        prev[s] = head;
        prev[first] = s;
        next[head] = s;
    }
public:
    LRUCache(int capacity) : capacity(capacity) {
        int slots = max(capacity, 0) + 2;
        keyAt.assign(slots, 0);
        valAt.assign(slots, 0);
        prev.assign(slots, -1);
        next.assign(slots, -1);
        head = slots - 2;
        tail = slots - 1;
        next[head] = tail;
        prev[tail] = head;
        for (int s = slots - 3; s >= 0; s--) freeSlots.push_back(s);
    }
    int get(int key) {
        auto it = slotOf.find(key);
        int s = it == slotOf.end() ? -1 : it->second;
        if (s == -1) return -1;
        unlink(s);
        linkFront(s);
        return valAt[s];
    }
    void put(int key, int value) {
        if (capacity <= 0) return;
        auto it = slotOf.find(key);
        int s = it == slotOf.end() ? -1 : it->second;
        if (s != -1) {
            valAt[s] = value;
            unlink(s);
            linkFront(s);
            return;
        }
        if (freeSlots.empty()) {
            int victim = prev[tail];
            unlink(victim);
            slotOf.erase(keyAt[victim]);
            freeSlots.push_back(victim);
        }
        s = freeSlots.back(); freeSlots.pop_back();
        keyAt[s] = key;
        valAt[s] = value;
        slotOf[key] = s;
        linkFront(s);
    }
};

class LRUCache {
    private Map<Integer, Integer> slotOf = new HashMap<>();
    private int[] keyAt;
    private int[] valAt;
    private int[] prev;
    private int[] next;
    private ArrayDeque<Integer> free = new ArrayDeque<>();
    private int head, tail;
    private int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        int slots = Math.max(capacity, 0) + 2;
        keyAt = new int[slots];
        valAt = new int[slots];
        prev = new int[slots]; Arrays.fill(prev, -1);
        next = new int[slots]; Arrays.fill(next, -1);
        head = slots - 2;
        tail = slots - 1;
        next[head] = tail;
        prev[tail] = head;
        for (int s = slots - 3; s >= 0; s--) free.push(s);
    }
    private void unlink(int s) {
        next[prev[s]] = next[s];
        prev[next[s]] = prev[s];
    }
    private void linkFront(int s) {
        int first = next[head];
        next[s] = first;
        prev[s] = head;
        prev[first] = s;
        next[head] = s;
    }
    public int get(int key) {
        Integer s = slotOf.get(key);
        if (s == null) return -1;
        unlink(s);
        linkFront(s);
        return valAt[s];
    }
    public void put(int key, int value) {
        if (capacity <= 0) return;
        Integer s = slotOf.get(key);
        if (s != null) {
            valAt[s] = value;
            unlink(s);
            linkFront(s);
            return;
        }
        if (free.isEmpty()) {
            int victim = prev[tail];
            unlink(victim);
            slotOf.remove(keyAt[victim]);
            free.push(victim);
        }
        s = free.pop();
        keyAt[s] = key;
        valAt[s] = value;
        slotOf.put(key, s);
        linkFront(s);
    }
}

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        slots = max(capacity, 0) + 2
        self.slot_of = {}
        self.key_at = [0] * slots
        self.val_at = [0] * slots
        self.prev = [-1] * slots
        self.next = [-1] * slots
        self.head = slots - 2
        self.tail = slots - 1
        self.next[self.head] = self.tail
        self.prev[self.tail] = self.head
        self.free = list(range(slots - 3, -1, -1))
    def _unlink(self, s):
        self.next[self.prev[s]] = self.next[s]
        self.prev[self.next[s]] = self.prev[s]
    def _link_front(self, s):
        first = self.next[self.head]
        self.next[s] = first
        self.prev[s] = self.head
        self.prev[first] = s
        self.next[self.head] = s
    def get(self, key):
        s = self.slot_of.get(key)
        if s is None: return -1
        self._unlink(s)
        self._link_front(s)
        return self.val_at[s]
    def put(self, key, value):
        if self.capacity <= 0: return
        s = self.slot_of.get(key)
        if s is not None:
            self.val_at[s] = value
            self._unlink(s)
            self._link_front(s)
            return
        if not self.free:
            victim = self.prev[self.tail]
            self._unlink(victim)
            del self.slot_of[self.key_at[victim]]
            self.free.append(victim)
        s = self.free.pop()
        self.key_at[s] = key
        self.val_at[s] = value
        self.slot_of[key] = s
        self._link_front(s)

class LRUCache {
  private slotOf = new Map<number, number>();
  private keyAt: number[];
  private valAt: number[];
  private prev: number[];
  private next: number[];
  private free: number[] = [];
  private readonly head: number;
  private readonly tail: number;
  constructor(private capacity: number) {
    const slots = Math.max(capacity, 0) + 2;
    this.keyAt = new Array<number>(slots).fill(0);
    this.valAt = new Array<number>(slots).fill(0);
    this.prev = new Array<number>(slots).fill(-1);
    this.next = new Array<number>(slots).fill(-1);
    this.head = slots - 2;
    this.tail = slots - 1;
    this.next[this.head] = this.tail;
    this.prev[this.tail] = this.head;
    for (let s = slots - 3; s >= 0; s--) this.free.push(s);
  }
  private unlink(s: number): void {
    this.next[this.prev[s]] = this.next[s];
    this.prev[this.next[s]] = this.prev[s];
  }
  private linkFront(s: number): void {
    const first = this.next[this.head];
    this.next[s] = first;
    this.prev[s] = this.head;
    this.prev[first] = s;
    this.next[this.head] = s;
  }
  get(key: number): number {
    const s = this.slotOf.get(key);
    if (s === undefined) return -1;
    this.unlink(s);
    this.linkFront(s);
    return this.valAt[s];
  }
  put(key: number, value: number): void {
    if (this.capacity <= 0) return;
    let s = this.slotOf.get(key);
    if (s !== undefined) {
      this.valAt[s] = value;
      this.unlink(s);
      this.linkFront(s);
      return;
    }
    if (this.free.length === 0) {
      const victim = this.prev[this.tail];
      this.unlink(victim);
      this.slotOf.delete(this.keyAt[victim]);
      this.free.push(victim);
    }
    s = this.free.pop()!;
    this.keyAt[s] = key;
    this.valAt[s] = value;
    this.slotOf.set(key, s);
    this.linkFront(s);
  }
}