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

  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;
      if (firstKey !== undefined) {
        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.
The class should be named `LRUCache<K, V>` and exported.
It needs methods: `constructor(capacity: number)`, `get(key: K): V | undefined`, `put(key: K, value: V): void`, and a getter `size(): number`.
Constraints:
- `capacity < 1` throws `RangeError`.
- `get` updates recency.
- `put` updates recency if key exists, or inserts new. Evicts LRU if full.
- `size` returns current number of entries.
- Fully typed, strict mode compatible, no `any` in public API.

I'll use a combination of a `Map` for O(1) lookups and a doubly linked list for O(1) recency updates, or just rely on `Map`'s insertion order if I delete and re-insert on access. Actually, JavaScript's `Map` maintains insertion order, and iterating over it yields keys in insertion order. If I delete and re-insert on `get` or `put`, the most recently used will be at the end, and the least recently used will be at the begining. This is a common trick in JS/TS for LRU caches and avoids implementing a doubly linked list manually.
Let's verify: `Map` iteration order is insertion order. When a key is updated, it does *not* change its position in the iteration order. So to make it LRU, I need to delete and re-insert on `get` and `put` (if key exists).
Wait, `Map.prototype.set` updates the value but keeps the key in its original position. So yes, I must delete and then set to move it to the end.
Alternatively, I can implement a proper doubly linked list with a hash map pointing to nodes. That's more robust and standard for interviews, but the Map trick is simpler and perfectly valid in JS/TS. Given the constraints, either is fine. I'll stick to the Map trick for brevity, but I'll make sure it's correct. Actually, implementing a doubly linked list is safer to avoid any edge cases with Map iteration order guarantees (though ES6 guarantees it). I'll just use Map delete+set, it's standard.

Let's draft using Map:
```typescript
export class LRUCache<K, V> {
  private map: Map<K, V>;
  private readonly 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)!;
    // Move to end (most recently used)
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  put(key: K, value: V): void {
    if (this.map.has(key)) {
      // Update existing: move to end
      this.map.delete(key);
    } else if (this.map.size >= this.capacity) {
      // Evict LRU (first key in map)
      const firstKey = this.map.keys().next().value;
      if (firstKey !== undefined) {
        this.map.delete(firstKey);
      }
    }
    this.map.set(key, value);
  }

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

Wait, `this.map.keys().next().value` might be `undefined` if map is empty, but we only call it when `size >= capacity` and `capacity >= 1`, so map won't be empty. It's safe.
But to be strictly typed and avoid `any` or `unknown`, I should handle it carefully. `this.map.keys().next().value` returns `K | undefined`. Since we check `size >= capacity` and `capacity >= 1`, it's guaranteed to be `K`. I can assert or just use `this.map.keys().next().value as K`. Or better, iterate:
```typescript
      const iterator = this.map.keys();
      const firstKey = iterator.next().value;
      this.map.delete(firstKey);
```
TypeScript might complain about `firstKey` being `K | undefined`. I'll add a check or use `!`.
Actually, a simpler way to get the first key: `this.map.keys().next().value` is fine. I'll just cast or use `!`.

Let's reconsider the doubly linked list approach. It's more robust and doesn't rely on Map iteration order quirks (though Map order is guaranteed). But the Map approach is very concise. I'll stick with Map but ensure types are strict.

Wait, `Map` iteration order is guaranteed by ES2015 spec. So it's fine.

Let's check types:
`this.map.keys().next().value` has type `K | undefined`.
I can do:
```typescript
      const firstKey = this.map.keys().next().value;
      if (firstKey !== undefined) {
        this.map.delete(firstKey);
      }
```
This is safe and type-correct.

One minor thing: `get` method signature says `get(key: K): V | undefined;`. My implementation returns `V | undefined`. Correct.
`put(key: K, value: V): void;` Correct.
`size` getter returns `number`. Correct.
Constructor throws `RangeError` if `capacity < 1`. Correct.

Let's test mentally:
`c = new LRUCache(2)`
`c.put("a", 1)` -> map: {"a": 1}
`c.put("b", 2)` -> map: {"a": 1, "b": 2}
`c.get("a")` -> has "a", val=1, delete "a", set "a":1 -> map: {"b": 2, "a": 1}
`c.put("c", 3)` -> has "c"? no. size(2) >= cap(2)? yes. firstKey = "b". delete "b". set "c":3 -> map: {"a": 1, "c": 3}
`c.get("b")` -> undefined
`c.get("a")` -> 1, moves to end -> map: {"c": 3, "a": 1}
`c.get("c")` -> 3, moves to end -> map: {"a": 1, "c": 3}
`c.size` -> 2
Matches example.

What about `put` updating existing key?
`c.put("a", 10)` -> has "a"? yes. delete "a". set "a":10 -> map: {"c": 3, "a": 10}. Correct.

Is there any issue with `Map` iteration order when deleting and re-inserting? No, it's standard.

One detail: `this.map.keys().next().value` might be slightly inefficient if we do it often, but for LRU it's O(1). Actually, getting the first key from Map is O(1) in V8.

Let's ensure strict mode compatibility.
I'll add explicit types where needed.
The class definition:
```typescript
export class LRUCache<K, V> {
  private readonly capacity: number;
  private map: Map<K, V>;

  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.
…[9007 chars elided]…
nt.
I'll output it. 
All good. 
Output matches. 
Proceeds. 
[Final Check]
- Generic class `LRUCache<K, V>`
- `constructor(capacity: number)` throws `RangeError` if `< 1`
- `get(key: K): V | undefined` updates recency
- `put(key: K, value: V): void` updates/inserts, evicts LRU if full
- `get size(): number` returns current size
- Strict mode compatible, no `any`
- Example behavior matches
All correct.
Output generation. 
```typescript
export class LRUCache<K, V> {
  private readonly capacity: number;
  private map: Map<K, V>;

  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;
      if (firstKey !== undefined) {
        this.map.delete(firstKey);
      }
    }
    this.map.set(key, value);
  }

  get size(): number {
    return this.map.size;
  }
}
```
Looks perfect. Output matches. 
Proceeds. 
[Output Generation] -> *Self-Correction/Verification during generation prep*
Wait, `this.map.keys().next().value` might be `undefined` if the map is empty, but we guard with `this.map.size >= this.capacity` and `capacity >= 1`, so map is never empty there. The `if (firstKey !== undefined)` is technically redundant but safe. I'll keep it for strict type safety.
Actually, to be perfectly clean, I can just do:
```typescript
      const iterator = this.map.keys();
      const firstKey = iterator.next().value;
      this.map.delete(firstKey);
```
But TS will complain `firstKey` is `K | undefined`. So the `if` is necessary. I'll keep it.
All good.
Output matches. 
Done. 
[Final Output Generation] (proceeds)