Practice › Stack & Queue
LRU Cache
Hard · Stack & Queue · Asked at Amazon, Microsoft, Google, Meta, Flipkart
Implement a Least Recently Used cache with capacity c and process the operations:
get k— print the value stored for key k, or-1if it is not in the cache. A successful get makes k the most recently used key.put k v— insert or update key k with value v (it becomes the most recently used). If this makes the cache hold more thanckeys, evict the least recently used key. Both operations must run in O(1).
Input
First line: c q. Next q lines: one operation each.
Output
One line for every get.
Constraints
- 1 ≤ c ≤ 3000
- 1 ≤ q ≤ 2 · 10^5
- 0 ≤ k, v ≤ 10^9
A hash map from key to a node of a doubly linked list ordered by recency: move a node to the front on use, evict from the back.
Example 1
Input
2 9 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4
Output
1 -1 -1 3 4
Example 2
Input
1 4 put 2 1 get 2 put 3 2 get 2
Output
1 -1
Hints
- You need O(1) lookup by key (hash map) and O(1) "move to most recent" / "remove least recent" (doubly linked list).
- Store list nodes in the map. On get/put, unlink the node and insert it at the front; on overflow, remove the node at the back and delete its key from the map.
Approach
A doubly linked list with sentinel head and tail keeps keys in recency order (front = most recent). The hash map stores key → node. get: if present, move its node to the front and return its value. put: if present, update and move to front; otherwise create a node at the front, and if the size exceeds the capacity, remove tail.prev and erase its key. Every step is O(1). (In Python, OrderedDict.move_to_end / popitem(last=False) implements the same structure; in Java, LinkedHashMap with access order does too.)
Complexity: O(1) per operation · O(capacity) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int cap, q;
cin >> cap >> q;
list<pair<long long, long long>> order; // front = most recently used
unordered_map<long long, list<pair<long long, long long>>::iterator> pos;
string op;
while (q--) {
cin >> op;
if (op == "get") {
long long k;
cin >> k;
auto it = pos.find(k);
if (it == pos.end()) cout << -1 << "\n";
else {
order.splice(order.begin(), order, it->second);
cout << it->second->second << "\n";
}
} else {
long long k, v;
cin >> k >> v;
auto it = pos.find(k);
if (it != pos.end()) {
it->second->second = v;
order.splice(order.begin(), order, it->second);
} else {
order.emplace_front(k, v);
pos[k] = order.begin();
if ((int)pos.size() > cap) {
pos.erase(order.back().first);
order.pop_back();
}
}
}
}
return 0;
}Python solution
import sys
from collections import OrderedDict
data = sys.stdin.read().split()
cap, q = int(data[0]), int(data[1])
cache = OrderedDict() # last = most recently used
out, i = [], 2
for _ in range(q):
if data[i] == "get":
k = data[i + 1]
i += 2
if k in cache:
cache.move_to_end(k)
out.append(cache[k])
else:
out.append("-1")
else:
k, v = data[i + 1], data[i + 2]
i += 3
if k in cache:
cache.move_to_end(k)
cache[k] = v
if len(cache) > cap:
cache.popitem(last=False)
print("\n".join(out))Java solution
import java.util.*;
import java.io.*;
public class Main {
static class Node {
long key, val;
Node prev, next;
Node(long k, long v) { key = k; val = v; }
}
static Node head = new Node(0, 0), tail = new Node(0, 0);
static void unlink(Node x) {
x.prev.next = x.next;
x.next.prev = x.prev;
}
static void addFront(Node x) {
x.next = head.next;
x.prev = head;
head.next.prev = x;
head.next = x;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int cap = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken());
head.next = tail;
tail.prev = head;
HashMap<Long, Node> map = new HashMap<>();
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
st = new StringTokenizer(br.readLine());
String op = st.nextToken();
long k = Long.parseLong(st.nextToken());
Node x = map.get(k);
if (op.equals("get")) {
if (x == null) sb.append(-1).append('\n');
else {
unlink(x);
addFront(x);
sb.append(x.val).append('\n');
}
} else {
long v = Long.parseLong(st.nextToken());
if (x != null) {
x.val = v;
unlink(x);
addFront(x);
} else {
x = new Node(k, v);
map.put(k, x);
addFront(x);
if (map.size() > cap) {
Node lru = tail.prev;
unlink(lru);
map.remove(lru.key);
}
}
}
}
System.out.print(sb);
}
}