JS Machine Coding Questions — Implementations You Must Know
LRU Cache
- Fixed-capacity key-value store; evict the least recently used entry when full.
- Key insight: In JavaScript, Map keeps insertion order. On get, delete and re-insert the key to move it to the end (most recently used). Evict the first key when over capacity.
- Gotcha: For interviews asking O(1) strictly, mention a doubly linked list + hash map — the Map trick is acceptable in many JS rounds.
- Gotcha: get on missing key should not mutate order.
1class LRUCache {
2 constructor(capacity) {
3 this.capacity = capacity;
4 this.cache = new Map();
5 }
6
7 get(key) {
8 if (!this.cache.has(key)) return undefined;
9 const val = this.cache.get(key);
10 this.cache.delete(key);
11 this.cache.set(key, val);
12 return val;
13 }
14
15 put(key, value) {
16 if (this.cache.has(key)) {
17 this.cache.delete(key);
18 } else if (this.cache.size >= this.capacity) {
19 const oldest = this.cache.keys().next().value;
20 this.cache.delete(oldest);
21 }
22 this.cache.set(key, value);
23 }
24}