ts-03-lru-cache

# Generic LRU cache

Implement **`solution.ts`** exporting a generic class:

```ts
export class LRUCache<K, V> {
  constructor(capacity: number);
  get(key: K): V | undefined;
  put(key: K, value: V): void;
  get size(): number;
}
```

A least-recently-used cache holding at most `capacity` entries.

- `get(key)` returns the stored value, or `undefined` if absent. A successful `get`
  counts as a **use** (it makes that key the most-recently used).
- `put(key, value)` inserts or updates a key. Updating an existing key also counts as a
  use. When inserting a **new** key would exceed `capacity`, evict the
  least-recently-used key first.
- `size` is the current number of entries (never exceeds `capacity`).
- Throw a `RangeError` if `capacity < 1`.

Example:

```ts
const c = new LRUCache<string, number>(2);
c.put("a", 1);
c.put("b", 2);
c.get("a");      // 1  -> "a" is now most-recently used
c.put("c", 3);   // evicts "b" (least-recently used)
c.get("b");      // undefined
c.get("a");      // 1
c.get("c");      // 3
c.size;          // 2
```

Keep it fully typed (must pass `tsc --noEmit` in strict mode). Do not use `any` in the
public API.

import { test } from "node:test";
import { strict as assert } from "node:assert";
import { LRUCache } from "./solution.ts";

test("stores and retrieves values", () => {
  const c = new LRUCache<string, number>(2);
  c.put("a", 1);
  c.put("b", 2);
  assert.equal(c.get("a"), 1);
  assert.equal(c.get("b"), 2);
  assert.equal(c.size, 2);
});

test("missing key returns undefined", () => {
  const c = new LRUCache<string, number>(2);
  assert.equal(c.get("nope"), undefined);
});

test("evicts least-recently-used on overflow", () => {
  const c = new LRUCache<string, number>(2);
  c.put("a", 1);
  c.put("b", 2);
  c.put("c", 3); // evicts "a"
  assert.equal(c.get("a"), undefined);
  assert.equal(c.get("b"), 2);
  assert.equal(c.get("c"), 3);
  assert.equal(c.size, 2);
});

test("get counts as a use and protects from eviction", () => {
  const c = new LRUCache<string, number>(2);
  c.put("a", 1);
  c.put("b", 2);
  assert.equal(c.get("a"), 1); // "a" now most-recently used
  c.put("c", 3); // evicts "b"
  assert.equal(c.get("b"), undefined);
  assert.equal(c.get("a"), 1);
  assert.equal(c.get("c"), 3);
});

test("put updates existing key and marks it used", () => {
  const c = new LRUCache<string, number>(2);
  c.put("a", 1);
  c.put("b", 2);
  c.put("a", 10); // update + use "a"
  c.put("c", 3); // evicts "b"
  assert.equal(c.get("a"), 10);
  assert.equal(c.get("b"), undefined);
  assert.equal(c.get("c"), 3);
  assert.equal(c.size, 2);
});

test("capacity of 1 keeps only the newest", () => {
  const c = new LRUCache<number, string>(1);
  c.put(1, "one");
  c.put(2, "two");
  assert.equal(c.get(1), undefined);
  assert.equal(c.get(2), "two");
  assert.equal(c.size, 1);
});

test("invalid capacity throws RangeError", () => {
  assert.throws(() => new LRUCache<string, number>(0), RangeError);
});

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```typescript
export class LRUCache<K, V> {
  private capacity: number;
  private map: Map<K, { value: V; prev: LRUCacheNode<K, V> | null; next: LRUCacheNode<K, V> | null }>;
  private head: LRUCacheNode<K, V> | null;
  private tail: LRUCacheNode<K, V> | null;

  constructor(capacity: number) {
    if (capacity < 1) {
      throw new RangeError("Capacity must be at least 1");
    }
    this.capacity = capacity;
    this.map = new Map();
    this.head = null;
    this.tail = null;
  }

  get(key: K): V | undefined {
    const entry = this.map.get(key);
    if (entry === undefined) {
      return undefined;
    }
    this.moveToHead(entry);
    return entry.value;
  }

  put(key: K, value: V): void {
    const entry = this.map.get(key);
    if (entry !== undefined) {
      entry.value = value;
      this.moveToHead(entry);
      return;
    }

    const newNode: LRUCacheNode<K, V> = {
      key,
      value,
      prev: null,
      next: null,
    };

    this.map.set(key, { value, prev: newNode, next: newNode });
    this.addToHead(newNode);

    if (this.map.size > this.capacity) {
      this.evictTail();
    }
  }

  get size(): number {
    return this.map.size;
  }

  private moveToHead(entry: { value: V; prev: LRUCacheNode<K, V> | null; next: LRUCacheNode<K, V> | null }): void {
    if (this.head === entry.prev) {
      return;
    }

    if (entry.prev !== null) {
      entry.prev.next = entry.next;
    }
    if (entry.next !== null) {
      entry.next.prev = entry.prev;
    }

    if (entry.next === null) {
      this.tail = entry.prev;
    }

    entry.prev = null;
    entry.next = this.head;
    if (this.head !== null) {
      this.head.prev = entry;
    }
    this.head = entry;
  }

  private addToHead(node: LRUCacheNode<K, V>): void {
    node.prev = null;
    node.next = this.head;
    if (this.head !== null) {
      this.head.prev = node;
    }
    this.head = node;
    if (this.tail === null) {
      this.tail = node;
    }
  }

  private evictTail(): void {
    if (this.tail === null) {
      return;
    }

    const tailNode = this.tail;
    this.map.delete(tailNode.key);

    if (tailNode.prev !== null) {
      tailNode.prev.next = null;
      this.tail = tailNode.prev;
    } else {
      this.head = null;
      this.tail = null;
    }
  }
}

interface LRUCacheNode<K, V> {
  key: K;
  value: V;
  prev: LRUCacheNode<K, V> | null;
  next: LRUCacheNode<K, V> | null;
}
```

[
  {
    "total": 7,
    "answer": "```typescript\nexport class LRUCache<K, V> {\n  private capacity: number;\n  private map: Map<K, { value: V; prev: LRUCacheNode<K, V> | null; next: LRUCacheNode<K, V> | null }>;\n  private head: LRUCacheNode<K, V> | null;\n  private tail: LRUCacheNode<K, V> | null;\n\n  constructor(capacity: number) {\n    if (capacity < 1) {\n      throw new RangeError(\"Capacity must be at least 1\");\n    }\n    this.capacity = capacity;\n    this.map = new Map();\n    this.head = null;\n    this.tail = null;\n  }\n\n  get(key: K): V | undefined {\n    const entry = this.map.get(key);\n    if (entry === undefined) {\n      return undefined;\n    }\n    this.moveToHead(entry);\n    return entry.value;\n  }\n\n  put(key: K, value: V): void {\n    const entry = this.map.get(key);\n    if (entry !== undefined) {\n      entry.value = value;\n      this.moveToHead(entry);\n      return;\n    }\n\n    const newNode: LRUCacheNode<K, V> = {\n      key,\n      value,\n      prev: null,\n      next: null,\n    };\n\n    this.map.set(key, { value, prev: newNode, next: newNode });\n    this.addToHead(newNode);\n\n    if (this.map.size > this.capacity) {\n      this.evictTail();\n    }\n  }\n\n  get size(): number {\n    return this.map.size;\n  }\n\n  private moveToHead(entry: { value: V; prev: LRUCacheNode<K, V> | null; next: LRUCacheNode<K, V> | null }): void {\n    if (this.head === entry.prev) {\n      return;\n    }\n\n    if (entry.prev !== null) {\n      entry.prev.next = entry.next;\n    }\n    if (entry.next !== null) {\n      entry.next.prev = entry.prev;\n    }\n\n    if (entry.next === null) {\n      this.tail = entry.prev;\n    }\n\n    entry.prev = null;\n    entry.next = this.head;\n    if (this.head !== null) {\n      this.head.prev = entry;\n    }\n    this.head = entry;\n  }\n\n  private addToHead(node: LRUCacheNode<K, V>): void {\n    node.prev = null;\n    node.next = this.head;\n    if (this.head !== null) {\n      this.head.prev = node;\n    }\n    this.head = node;\n    if (this.tail === null) {\n      this.tail = node;\n    }\n  }\n\n  private evictTail(): void {\n    if (this.tail === null) {\n      return;\n    }\n\n    const tailNode = this.tail;\n    this.map.delete(tailNode.key);\n\n    if (tailNode.prev !== null) {\n      tailNode.prev.next = null;\n      this.tail = tailNode.prev;\n    } else {\n      this.head = null;\n      this.tail = null;\n    }\n  }\n}\n\ninterface LRUCacheNode<K, V> {\n  key: K;\n  value: V;\n  prev: LRUCacheNode<K, V> | null;\n  next: LRUCacheNode<K, V> | null;\n}\n```",
    "passed": 5,
    "test_error": "  type: 'test'\n  ...\n# Subtest: missing key returns undefined\nok 2 - missing key returns undefined\n  ---\n  duration_ms: 0.056511\n  type: 'test'\n  ...\n# Subtest: evicts least-recently-used on overflow\nok 3 - evicts least-recently-used on overflow\n  ---\n  duration_ms: 0.05445\n  type: 'test'\n  ...\n# Subtest: get counts as a use and protects from eviction\nnot ok 4 - get counts as a use and protects from eviction\n  ---\n  duration_ms: 0.809637\n  type: 'test'\n  location: '/tmp/llmlab-ts-03-lru-cache-kfkdhplf/solution.test.ts:1:604'\n  failureType: 'testCodeFailure'\n  error: |-\n    Expected values to be strictly equal:\n    \n    2 !== undefined\n    \n  code: 'ERR_ASSERTION'\n  name: 'AssertionError'\n  actual: 2\n  operator: 'strictEqual'\n  stack: |-\n    TestContext.<anonymous> (/tmp/llmlab-ts-03-lru-cache-kfkdhplf/solution.test.ts:36:10)\n    Test.runInAsyncScope (node:async_hooks:227:14)\n    Test.run (node:internal/test_runner/test:1306:25)\n    Test.processPendingSubtests (node:internal/test_runner/test:897:18)\n    Test.postRun (node:internal/test_runner/test:1447:19)\n    Test.run (node:internal/test_runner/test:1372:12)\n    async Test.processPendingSubtests (node:internal/test_runner/test:897:7)\n  ...\n# Subtest: put updates existing key and marks it used\nnot ok 5 - put updates existing key and marks it used\n  ---\n  duration_ms: 0.161101\n  type: 'test'\n  location: '/tmp/llmlab-ts-03-lru-cache-kfkdhplf/solution.test.ts:1:841'\n  failureType: 'testCodeFailure'\n  error: |-\n    Expected values to be strictly equal:\n    \n    undefined !== 10\n    \n  code: 'ERR_ASSERTION'\n  name: 'AssertionError'\n  expected: 10\n  operator: 'strictEqual'\n  stack: |-\n    TestContext.<anonymous> (/tmp/llmlab-ts-03-lru-cache-kfkdhplf/solution.test.ts:47:10)\n    Test.runInAsyncScope (node:async_hooks:227:14)\n    Test.run (node:internal/test_runner/test:1306:25)\n    Test.processPendingSubtests (node:internal/test_runner/test:897:18)\n    Test.postRun (node:internal/test_runner/test:1447:19)\n    Test.run (node:internal/test_runner/test:1372:12)\n    async Test.processPendingSubtests (node:internal/test_runner/test:897:7)\n  ...\n# Subtest: capacity of 1 keeps only the newest\nok 6 - capacity of 1 keeps only the newest\n  ---\n  duration_ms: 0.060801\n  type: 'test'\n  ...\n# Subtest: invalid capacity throws RangeError\nok 7 - invalid capacity throws RangeError\n  ---\n  duration_ms: 0.171592\n  type: 'test'\n  ...\n1..7\n# tests 7\n# suites 0\n# pass 5\n# fail 2\n# cancelled 0\n# skipped 0\n# todo 0\n# duration_ms 77.950035"
  },
  {
    "total": 7,
    "answer": "```typescript\nexport class LRUCache<K, V> {\n  private capacity: number;\n  private map: Map<K, { value: V; prev: LRUCacheNode<K, V> | null; next: LRUCacheNode<K, V> | null }>;\n  private head: LRUCacheNode<K, V> | null;\n  private tail: LRUCacheNode<K, V> | null;\n\n  constructor(capacity: number) {\n    if (capacity < 1) {\n      throw new RangeError(\"Capacity must be at least 1\");\n    }\n    this.capacity = capacity;\n    this.map = new Map();\n    this.head = null;\n    this.tail = null;\n  }\n\n  get(key: K): V | undefined {\n    const entry = this.map.get(key);\n    if (entry === undefined) {\n      return undefined;\n    }\n    this.moveToHead(entry);\n    return entry.value;\n  }\n\n  put(key: K, value: V): void {\n    const entry = this.map.get(key);\n    if (entry !== undefined) {\n      entry.value = value;\n      this.moveToHead(entry);\n      return;\n    }\n\n    const newNode: LRUCacheNode<K, V> = {\n      key,\n      value,\n      prev: null,\n      next: null,\n    };\n\n    this.map.set(key, { value, prev: newNode, next: newNode });\n    this.addToHead(newNode);\n\n    if (this.map.size > this.capacity) {\n      this.evictTail();\n    }\n  }\n\n  get size(): number {\n    return this.map.size;\n  }\n\n  private moveToHead(entry: { value: V; prev: LRUCacheNode<K, V> | null; next: LRUCacheNode<K, V> | null }): void {\n    if (this.head === entry.prev) {\n      return;\n    }\n\n    if (entry.prev !== null) {\n      entry.prev.next = entry.next;\n    }\n    if (entry.next !== null) {\n      entry.next.prev = entry.prev;\n    }\n\n    if (entry.next === null) {\n      this.tail = entry.prev;\n    }\n\n    entry.prev = null;\n    entry.next = this.head;\n    if (this.head !== null) {\n      this.head.prev = entry;\n    }\n    this.head = entry;\n  }\n\n  private addToHead(node: LRUCacheNode<K, V>): void {\n    node.prev = null;\n    node.next = this.head;\n    if (this.head !== null) {\n      this.head.prev = node;\n    }\n    this.head = node;\n    if (this.tail === null) {\n      this.tail = node;\n    }\n  }\n\n  private evictTail(): void {\n    if (this.tail === null) {\n      return;\n    }\n\n    const tailNode = this.tail;\n    this.map.delete(tailNode.key);\n\n    if (tailNode.prev !== null) {\n      tailNode.prev.next = null;\n      this.tail = tailNode.prev;\n    } else {\n      this.head = null;\n      this.tail = null;\n    }\n  }\n}\n\ninterface LRUCacheNode<K, V> {\n  key: K;\n  value: V;\n  prev: LRUCacheNode<K, V> | null;\n  next: LRUCacheNode<K, V> | null;\n}\n```",
    "passed": 5,
    "test_error": "\n  type: 'test'\n  ...\n# Subtest: missing key returns undefined\nok 2 - missing key returns undefined\n  ---\n  duration_ms: 0.06057\n  type: 'test'\n  ...\n# Subtest: evicts least-recently-used on overflow\nok 3 - evicts least-recently-used on overflow\n  ---\n  duration_ms: 0.055611\n  type: 'test'\n  ...\n# Subtest: get counts as a use and protects from eviction\nnot ok 4 - get counts as a use and protects from eviction\n  ---\n  duration_ms: 0.831528\n  type: 'test'\n  location: '/tmp/llmlab-ts-03-lru-cache-nd_u3evl/solution.test.ts:1:604'\n  failureType: 'testCodeFailure'\n  error: |-\n    Expected values to be strictly equal:\n    \n    2 !== undefined\n    \n  code: 'ERR_ASSERTION'\n  name: 'AssertionError'\n  actual: 2\n  operator: 'strictEqual'\n  stack: |-\n    TestContext.<anonymous> (/tmp/llmlab-ts-03-lru-cache-nd_u3evl/solution.test.ts:36:10)\n    Test.runInAsyncScope (node:async_hooks:227:14)\n    Test.run (node:internal/test_runner/test:1306:25)\n    Test.processPendingSubtests (node:internal/test_runner/test:897:18)\n    Test.postRun (node:internal/test_runner/test:1447:19)\n    Test.run (node:internal/test_runner/test:1372:12)\n    async Test.processPendingSubtests (node:internal/test_runner/test:897:7)\n  ...\n# Subtest: put updates existing key and marks it used\nnot ok 5 - put updates existing key and marks it used\n  ---\n  duration_ms: 0.170922\n  type: 'test'\n  location: '/tmp/llmlab-ts-03-lru-cache-nd_u3evl/solution.test.ts:1:841'\n  failureType: 'testCodeFailure'\n  error: |-\n    Expected values to be strictly equal:\n    \n    undefined !== 10\n    \n  code: 'ERR_ASSERTION'\n  name: 'AssertionError'\n  expected: 10\n  operator: 'strictEqual'\n  stack: |-\n    TestContext.<anonymous> (/tmp/llmlab-ts-03-lru-cache-nd_u3evl/solution.test.ts:47:10)\n    Test.runInAsyncScope (node:async_hooks:227:14)\n    Test.run (node:internal/test_runner/test:1306:25)\n    Test.processPendingSubtests (node:internal/test_runner/test:897:18)\n    Test.postRun (node:internal/test_runner/test:1447:19)\n    Test.run (node:internal/test_runner/test:1372:12)\n    async Test.processPendingSubtests (node:internal/test_runner/test:897:7)\n  ...\n# Subtest: capacity of 1 keeps only the newest\nok 6 - capacity of 1 keeps only the newest\n  ---\n  duration_ms: 0.05889\n  type: 'test'\n  ...\n# Subtest: invalid capacity throws RangeError\nok 7 - invalid capacity throws RangeError\n  ---\n  duration_ms: 0.173631\n  type: 'test'\n  ...\n1..7\n# tests 7\n# suites 0\n# pass 5\n# fail 2\n# cancelled 0\n# skipped 0\n# todo 0\n# duration_ms 74.517951"
  },
  {
    "total": 7,
    "answer": "```typescript\nexport class LRUCache<K, V> {\n  private capacity: number;\n  private map: Map<K, { value: V; prev: LRUCacheNode<K, V> | null; next: LRUCacheNode<K, V> | null }>;\n  private head: LRUCacheNode<K, V> | null;\n  private tail: LRUCacheNode<K, V> | null;\n\n  constructor(capacity: number) {\n    if (capacity < 1) {\n      throw new RangeError(\"Capacity must be at least 1\");\n    }\n    this.capacity = capacity;\n    this.map = new Map();\n    this.head = null;\n    this.tail = null;\n  }\n\n  get(key: K): V | undefined {\n    const entry = this.map.get(key);\n    if (entry === undefined) {\n      return undefined;\n    }\n    this.moveToHead(entry);\n    return entry.value;\n  }\n\n  put(key: K, value: V): void {\n    const entry = this.map.get(key);\n    if (entry !== undefined) {\n      entry.value = value;\n      this.moveToHead(entry);\n      return;\n    }\n\n    const newNode: LRUCacheNode<K, V> = {\n      key,\n      value,\n      prev: null,\n      next: null,\n    };\n\n    this.map.set(key, { value, prev: newNode, next: newNode });\n    this.addToHead(newNode);\n\n    if (this.map.size > this.capacity) {\n      this.evictTail();\n    }\n  }\n\n  get size(): number {\n    return this.map.size;\n  }\n\n  private moveToHead(entry: { value: V; prev: LRUCacheNode<K, V> | null; next: LRUCacheNode<K, V> | null }): void {\n    if (this.head === entry.prev) {\n      return;\n    }\n\n    if (entry.prev !== null) {\n      entry.prev.next = entry.next;\n    }\n    if (entry.next !== null) {\n      entry.next.prev = entry.prev;\n    }\n\n    if (entry.next === null) {\n      this.tail = entry.prev;\n    }\n\n    entry.prev = null;\n    entry.next = this.head;\n    if (this.head !== null) {\n      this.head.prev = entry;\n    }\n    this.head = entry;\n  }\n\n  private addToHead(node: LRUCacheNode<K, V>): void {\n    node.prev = null;\n    node.next = this.head;\n    if (this.head !== null) {\n      this.head.prev = node;\n    }\n    this.head = node;\n    if (this.tail === null) {\n      this.tail = node;\n    }\n  }\n\n  private evictTail(): void {\n    if (this.tail === null) {\n      return;\n    }\n\n    const tailNode = this.tail;\n    this.map.delete(tailNode.key);\n\n    if (tailNode.prev !== null) {\n      tailNode.prev.next = null;\n      this.tail = tailNode.prev;\n    } else {\n      this.head = null;\n      this.tail = null;\n    }\n  }\n}\n\ninterface LRUCacheNode<K, V> {\n  key: K;\n  value: V;\n  prev: LRUCacheNode<K, V> | null;\n  next: LRUCacheNode<K, V> | null;\n}\n```",
    "passed": 5,
    "test_error": ""
  }
]