TypeScript: A generic LRU cache

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 | undefined and put(key: K, value: V): K | undefined, which returns the key it evicted, if any.
  • Both get (when the key is present) and put make the key the most recently used.
  • put KEY VALUE prints evicted KEY when an entry had to go; get KEY prints the value or miss. At the end print cache: 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(" "));

Lesson: Generic classes and typed collections →