A cache keeps a few recent results close at hand so they are quick to read again. It can only hold a limited number of entries, so when it is full it must throw one away. An LRU (Least Recently Used) cache throws away the entry that was used longest ago. Build a class LRUCache that stores integer keys with integer values.
The class keeps: capacity: number, a Map<number, number> called map (key to value) and a number[] called order (the keys, least recently used first).
Create it: new LRUCache(capacity) makes an empty cache that holds at most capacity entries.
Methods and rules:
get(key: number): numberreturns the value stored forkey. A hit counts as a use: the key becomes the most recently used. If the key is not in the cache (never stored, or already evicted), return-1and change nothing.put(key: number, value: number): voidstores the value forkey, and the key becomes the most recently used.- If the key is already in the cache, replace its value. Nothing is evicted.
- If the key is new and the cache already holds
capacityentries, first evict the least recently used entry (remove it from the map and fromorder), then store the new one.
- Keep
ordersorted by use: the least recently used key at the front, the most recently used at the end. Every use moves the key to the end.
Tools for this language:
- In
constructor(capacity: number), savethis.capacity; declare the typed fieldsmap: Map<number, number> = new Map()andorder: number[] = []. this.map.has(key)tells whether a key is stored;this.map.set(key, value)stores or replaces a value;this.map.delete(key)deletes an entry;this.map.sizecounts the entries.this.order.filter((k) => k !== key)builds an array without the key,push(key)adds at the end, andshift()removes and returns the first item.
This version walks over the list of keys for each operation, which is fine for learning. Interview solutions reach O(1) with a hash map plus a doubly linked list.
You start with the code that tests your class (write LRUCache above it):
let c = new LRUCache(2);
c.put(1, 10);
c.put(2, 20);
console.log("Get 1: " + c.get(1));
c.put(3, 30);
console.log("Get 2: " + c.get(2));
console.log("Get 3: " + c.get(3));
console.log("Miss 9: " + c.get(9));
c.put(1, 11);
console.log("Update 1: " + c.get(1));
c.put(4, 40);
console.log("Evicted 3: " + c.get(3));
console.log("Kept 1: " + c.get(1));
console.log("Kept 4: " + c.get(4));
let s = new LRUCache(1);
s.put(1, 100);
s.put(2, 200);
console.log("Small 1: " + s.get(1));
console.log("Small 2: " + s.get(2));
Expected output:
Get 1: 10
Get 2: -1
Get 3: 30
Miss 9: -1
Update 1: 11
Evicted 3: -1
Kept 1: 11
Kept 4: 40
Small 1: -1
Small 2: 200Check it against the rules: Get 2 is -1 because key 2 was the least recently used when key 3 arrived (key 1 had just been read). Updating key 1 to 11 does not evict anything. With capacity 1, the second put evicts the first key.
Two structures work together: the map gives a fast lookup of the value, and
order remembers which key was used when. Both must always hold the same keys.
this.order = this.order.filter((k) => k !== key) then this.order.push(key) moves a key to the end. this.order.shift()! gives the least recently used key.
class LRUCache {
capacity: number;
map: Map<number, number> = new Map();
order: number[] = [];
constructor(capacity: number) {
this.capacity = capacity;
}
get(key: number): number {
if (!this.map.has(key)) return -1;
this.order = this.order.filter((k) => k !== key);
this.order.push(key);
return this.map.get(key)!;
}
put(key: number, value: number): void {
if (this.map.has(key)) {
this.order = this.order.filter((k) => k !== key);
} else if (this.map.size >= this.capacity) {
const evict = this.order.shift()!;
this.map.delete(evict);
}
this.map.set(key, value);
this.order.push(key);
}
}
Free plan: 30 tutor messages. Premium is unlimited.
