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 map: Map<K, V>;
  private capacity: number;

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

  get(key: K): V | undefined {
    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: K, value: V): void {
    if (this.map.has(key)) {
      this.map.delete(key);
    } else if (this.map.size >= this.capacity) {
      const firstKey = this.map.keys().next().value;
      this.map.delete(firstKey);
    }
    this.map.set(key, value);
  }

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

The user wants a generic LRU cache implementation in TypeScript.

Requirements:
1. Class `LRUCache<K, V>`
2. Constructor takes `capacity: number`
3. Methods: `get(key: K): V | undefined`, `put(key: K, value: V): void`
4. Property: `size: number`
5. Behavior:
   - `get` returns value or undefined, marks key as most recently used
   - `put` inserts/updates, marks as most recently used
   - Evicts least recently used when capacity exceeded on new insert
   - `size` returns current number of entries
   - Throw `RangeError` if capacity < 1
6. Must be fully typed, no `any` in public API, pass `tsc --noEmit` in strict mode

Implementation approach:
- Use a Map for O(1) lookups
- Use a doubly-linked list to track order of usage (most recent at one end, least recent at other)
- Or use Map's insertion order (in modern JS, Map maintains insertion order) and re-insert on access

Actually, using Map's insertion order is simpler and efficient enough:
- On `get`: if key exists, delete and re-insert to move to end (most recent)
- On `put`: if key exists, delete and re-insert; if new and size >= capacity, delete first entry (least recent)
- `size`: map.size

Let me implement this:

```ts
export class LRUCache<K, V> {
  private map: Map<K, V>;
  private capacity: number;

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

  get(key: K): V | undefined {
    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: K, value: V): void {
    if (this.map.has(key)) {
      this.map.delete(key);
    } else if (this.map.size >= this.capacity) {
      const firstKey = this.map.keys().next().value;
      this.map.delete(firstKey);
    }
    this.map.set(key, value);
  }

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

This should work correctly and be fully typed. Let me verify:
- `K` and `V` are generic type parameters
- No `any` used
- `get` returns `V | undefined`
- `put` returns `void`
- `size` returns `number`
- Constructor throws `RangeError` for capacity < 1
- Uses Map's insertion order for LRU tracking

This looks correct. Let me double-check the example:
- `new LRUCache<string, number>(2)` - capacity 2
- `put("a", 1)` - map: {a: 1}
- `put("b", 2)` - map: {a: 1, b: 2}
- `get("a")` - returns 1, map: {b: 2, a: 1} (a moved to end)
- `put("c", 3)` - new key, size >= capacity, evict first (b), map: {a: 1, c: 3}
- `get("b")` - undefined
- `get("a")` - returns 1, map: {c: 3, a: 1}
- `get("c")` - returns 3, map: {a: 1, c: 3}
- `size` - 2

Matches the expected behavior.

One minor thing: I should make sure the code is clean and passes strict TypeScript. The implementation looks good.