Page Cache

lru-page-cacheproblem-lablrucachemap

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Page Cache

Applied Patterns

Cache the last K pages and evict the least-recently-used. A JS Map preserves insertion order, so re-inserting a key on every access keeps the order from oldest to newest — the first key is the LRU victim, and every operation stays O(1).

A renderer caches up to K rendered pages. When a new page arrives and the cache is full, the page nobody has touched in the longest time should be dropped.

The LRU pattern leans on one fact: a JavaScript Map iterates keys in insertion order. On a get, deleting the key and setting it again moves it to the end, marking it most-recently-used.

On a put you do the same refresh, then if size exceeds capacity you delete keys().next().value — the very first key, which is the least-recently-used. Every step is O(1).

Map iteration order is insertion order.

delete + set refreshes a key to most-recent.

The first key is always the LRU eviction target.

class PageCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }
  get(key) {
    if (!this.map.has(key)) return undefined;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);
    }
  }
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Ordered store

A JS Map remembers insertion order, which we exploit as recency order.

this.map = new Map();

2. Refresh on read

Deleting then re-setting moves the key to the most-recent (end) position on every get.

this.map.delete(key);
    this.map.set(key, value);

3. Move on write

Writing an existing key first removes it so the re-set lands it at the most-recent end.

if (this.map.has(key)) this.map.delete(key);

4. Find LRU

The first key the iterator yields is the least-recently-used entry.

const oldest = this.map.keys().next().value;

5. Evict LRU

Deleting the oldest key keeps the cache at capacity in O(1).

this.map.delete(oldest);

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.