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.

```ts
export class LRUCache<K, V> {
  private capacity: number;
  private size: number;
  private cache: Map<K, V>;
  private keys: Array<K>;

  constructor(capacity: number) {
    if (capacity < 1) {
      throw new RangeError("Capacity must be at least 1");
    }
    this.capacity = capacity;
    this.size = 0;
    this.cache = new Map<K, V>();
    this.keys = [];
  }

  get(key: K): V | undefined {
    if (!this.cache.has(key)) {
      return undefined;
    }
    const value = this.cache.get(key);
    this.keys[this.keys.indexOf(key)] = this.size;
    this.keys.sort((a, b) => b - a);
    return value;
  }

  put(key: K, value: V): void {
    if (this.cache.has(key)) {
      this.cache.set(key, value);
      this.keys[this.keys.indexOf(key)] = this.size;
      this.keys.sort((a, b) => b - a);
    } else {
      if (this.size === this.capacity) {
        const oldestKey = this.keys.shift();
        this.cache.delete(oldestKey);
      }
      this.cache.set(key, value);
      this.keys.push(this.size);
      this.size = this.size === this.capacity ? this.keys.pop() : this.size;
    }
  }

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

[
  {
    "total": 7,
    "answer": "```ts\nexport class LRUCache<K, V> {\n  private capacity: number;\n  private size: number;\n  private cache: Map<K, V>;\n  private keys: Array<K>;\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.size = 0;\n    this.cache = new Map<K, V>();\n    this.keys = [];\n  }\n\n  get(key: K): V | undefined {\n    if (!this.cache.has(key)) {\n      return undefined;\n    }\n    const value = this.cache.get(key);\n    this.keys[this.keys.indexOf(key)] = this.size;\n    this.keys.sort((a, b) => b - a);\n    return value;\n  }\n\n  put(key: K, value: V): void {\n    if (this.cache.has(key)) {\n      this.cache.set(key, value);\n      this.keys[this.keys.indexOf(key)] = this.size;\n      this.keys.sort((a, b) => b - a);\n    } else {\n      if (this.size === this.capacity) {\n        const oldestKey = this.keys.shift();\n        this.cache.delete(oldestKey);\n      }\n      this.cache.set(key, value);\n      this.keys.push(this.size);\n      this.size = this.size === this.capacity ? this.keys.pop() : this.size;\n    }\n  }\n\n  get size(): number {\n    return this.size;\n  }\n}\n```",
    "passed": 2,
    "test_error": "estContext.<anonymous> (/tmp/llmlab-ts-03-lru-cache-gkl5ftr7/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.09763\n  type: 'test'\n  location: '/tmp/llmlab-ts-03-lru-cache-gkl5ftr7/solution.test.ts:1:841'\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-gkl5ftr7/solution.test.ts:48: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\nnot ok 6 - capacity of 1 keeps only the newest\n  ---\n  duration_ms: 0.09866\n  type: 'test'\n  location: '/tmp/llmlab-ts-03-lru-cache-gkl5ftr7/solution.test.ts:1:1085'\n  failureType: 'testCodeFailure'\n  error: |-\n    Expected values to be strictly equal:\n    \n    'one' !== undefined\n    \n  code: 'ERR_ASSERTION'\n  name: 'AssertionError'\n  actual: 'one'\n  operator: 'strictEqual'\n  stack: |-\n    TestContext.<anonymous> (/tmp/llmlab-ts-03-lru-cache-gkl5ftr7/solution.test.ts:57: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: invalid capacity throws RangeError\nok 7 - invalid capacity throws RangeError\n  ---\n  duration_ms: 0.18748\n  type: 'test'\n  ...\n1..7\n# tests 7\n# suites 0\n# pass 2\n# fail 5\n# cancelled 0\n# skipped 0\n# todo 0\n# duration_ms 78.668327"
  },
  {
    "total": 7,
    "answer": "```ts\nexport class LRUCache<K, V> {\n  private capacity: number;\n  private size: number;\n  private cache: Map<K, V>;\n  private keys: Array<K>;\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.size = 0;\n    this.cache = new Map<K, V>();\n    this.keys = [];\n  }\n\n  get(key: K): V | undefined {\n    if (!this.cache.has(key)) {\n      return undefined;\n    }\n    const value = this.cache.get(key);\n    this.keys[this.keys.indexOf(key)] = this.size;\n    this.keys.sort((a, b) => b - a);\n    return value;\n  }\n\n  put(key: K, value: V): void {\n    if (this.cache.has(key)) {\n      this.cache.set(key, value);\n      this.keys[this.keys.indexOf(key)] = this.size;\n      this.keys.sort((a, b) => b - a);\n    } else {\n      if (this.size === this.capacity) {\n        const oldestKey = this.keys.shift();\n        this.cache.delete(oldestKey);\n      }\n      this.cache.set(key, value);\n      this.keys.push(this.size);\n      this.size = this.size === this.capacity ? this.keys.pop() : this.size;\n    }\n  }\n\n  get size(): number {\n    return this.size;\n  }\n}\n```",
    "passed": 2,
    "test_error": "stContext.<anonymous> (/tmp/llmlab-ts-03-lru-cache-oezfzcms/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.093701\n  type: 'test'\n  location: '/tmp/llmlab-ts-03-lru-cache-oezfzcms/solution.test.ts:1:841'\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-oezfzcms/solution.test.ts:48: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\nnot ok 6 - capacity of 1 keeps only the newest\n  ---\n  duration_ms: 0.10236\n  type: 'test'\n  location: '/tmp/llmlab-ts-03-lru-cache-oezfzcms/solution.test.ts:1:1085'\n  failureType: 'testCodeFailure'\n  error: |-\n    Expected values to be strictly equal:\n    \n    'one' !== undefined\n    \n  code: 'ERR_ASSERTION'\n  name: 'AssertionError'\n  actual: 'one'\n  operator: 'strictEqual'\n  stack: |-\n    TestContext.<anonymous> (/tmp/llmlab-ts-03-lru-cache-oezfzcms/solution.test.ts:57: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: invalid capacity throws RangeError\nok 7 - invalid capacity throws RangeError\n  ---\n  duration_ms: 0.19093\n  type: 'test'\n  ...\n1..7\n# tests 7\n# suites 0\n# pass 2\n# fail 5\n# cancelled 0\n# skipped 0\n# todo 0\n# duration_ms 77.881887"
  },
  {
    "total": 7,
    "answer": "```ts\nexport class LRUCache<K, V> {\n  private capacity: number;\n  private size: number;\n  private cache: Map<K, V>;\n  private keys: Array<K>;\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.size = 0;\n    this.cache = new Map<K, V>();\n    this.keys = [];\n  }\n\n  get(key: K): V | undefined {\n    if (!this.cache.has(key)) {\n      return undefined;\n    }\n    const value = this.cache.get(key);\n    this.keys[this.keys.indexOf(key)] = this.size;\n    this.keys.sort((a, b) => b - a);\n    return value;\n  }\n\n  put(key: K, value: V): void {\n    if (this.cache.has(key)) {\n      this.cache.set(key, value);\n      this.keys[this.keys.indexOf(key)] = this.size;\n      this.keys.sort((a, b) => b - a);\n    } else {\n      if (this.size === this.capacity) {\n        const oldestKey = this.keys.shift();\n        this.cache.delete(oldestKey);\n      }\n      this.cache.set(key, value);\n      this.keys.push(this.size);\n      this.size = this.size === this.capacity ? this.keys.pop() : this.size;\n    }\n  }\n\n  get size(): number {\n    return this.size;\n  }\n}\n```",
    "passed": 2,
    "test_error": ""
  }
]