A least-recently-used cache keeps a fixed number of entries and throws out the one unused for longest. Build it as a generic class on top of Map.
What to build
A program that runs put and get commands against an LRU cache.
Requirements
- Write
class LruCache<K, V>with a capacity,get(key: K): V | undefinedandput(key: K, value: V): K | undefined, which returns the key it evicted, if any. - Both
get(when the key is present) andputmake the key the most recently used. put KEY VALUEprintsevicted KEYwhen an entry had to go;get KEYprints the value ormiss. At the end printcache: KEY=VALUE ...from least to most recently used.
Input
Line 1: capacity and n. Then n commands; keys are words and values whole numbers.
Output
One line per get and per eviction, then the cache.
Constraints
1 ≤ capacity ≤ 10; 1 ≤ n ≤ 100.
Example
Input:
2 6
put a 1
put b 2
get a
put c 3
get b
get c
Output:
1
evicted b
miss
3
cache: a=1 c=3
Why it works
Map keeps keys in insertion order, so moving a key to the end on every use leaves the least recently used one first, which makes both operations fast and keeps the class short.
Examples
Example 1 · Input
2 6 put a 1 put b 2 get a put c 3 get b get c
Expected output
1 evicted b miss 3 cache: a=1 c=3
Example 2 · Input
1 4 put x 5 put x 6 get x put y 7
Expected output
6 evicted x cache: y=7
Hints
Hint 1
A Map remembers insertion order: delete a key and set it again to move it to the end.
Hint 2
The first key of map.keys() is the least recently used one.
Solution
Show one correct solution (try it yourself first)
const read = (): string => prompt() ?? "";
class LruCache<K, V> {
private entries = new Map<K, V>();
constructor(private capacity: number) {}
get(key: K): V | undefined {
if (!this.entries.has(key)) return undefined;
const value = this.entries.get(key) as V;
this.entries.delete(key);
this.entries.set(key, value);
return value;
}
put(key: K, value: V): K | undefined {
let evicted: K | undefined;
if (this.entries.has(key)) this.entries.delete(key);
else if (this.entries.size >= this.capacity) {
evicted = this.entries.keys().next().value as K;
this.entries.delete(evicted);
}
this.entries.set(key, value);
return evicted;
}
list(): [K, V][] {
return [...this.entries];
}
}
const [capacity, n] = read().split(" ").map(Number);
const cache = new LruCache<string, number>(capacity);
for (let i = 0; i < n; i++) {
const [command, key, value] = read().split(" ");
if (command === "put") {
const evicted = cache.put(key, Number(value));
if (evicted !== undefined) console.log("evicted " + evicted);
} else {
const found = cache.get(key);
console.log(found === undefined ? "miss" : String(found));
}
}
console.log("cache: " + cache.list().map(([k, v]) => k + "=" + v).join(" "));