js-03-lru-cache

# LRU cache

Implement an ES module **`solution.js`** exporting a least-recently-used cache class:

```js
export class LRUCache {
  constructor(capacity) { /* ... */ }
  get(key) { /* ... */ }
  put(key, value) { /* ... */ }
}
```

`capacity` is a positive integer — the maximum number of entries the cache holds.

- **`get(key)`** returns the stored value, or `undefined` if the key is not present. A successful
  `get` counts as a use: it marks the key as the **most recently used**.
- **`put(key, value)`** inserts or updates the entry and marks it most recently used. If adding a
  **new** key would exceed `capacity`, evict the **least recently used** entry first. Updating an
  existing key never changes the number of entries (and refreshes its recency).

"Recently used" is updated by **both** `get` and `put`. Keys may be any value usable as a `Map` key.

Example:
```js
const c = new LRUCache(2);
c.put("a", 1);
c.put("b", 2);
c.get("a");       // => 1   (now "a" is most-recently-used, "b" is least)
c.put("c", 3);    // capacity exceeded -> evicts "b"
c.get("b");       // => undefined
c.get("a");       // => 1
c.get("c");       // => 3
```

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

test("stores and retrieves a value", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  assert.equal(c.get("a"), 1);
});

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

test("evicts the least-recently-used entry at capacity", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  c.put("b", 2);
  c.put("c", 3); // exceeds capacity -> "a" (oldest) evicted
  assert.equal(c.get("a"), undefined);
  assert.equal(c.get("b"), 2);
  assert.equal(c.get("c"), 3);
});

test("get refreshes recency so a different key is evicted", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  c.put("b", 2);
  c.get("a"); // "a" now most-recently-used, "b" least
  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("updating an existing key does not grow size and refreshes recency", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  c.put("b", 2);
  c.put("a", 10); // update -> "a" most-recently-used, size stays 2
  c.put("c", 3); // evicts "b", not "a"
  assert.equal(c.get("b"), undefined);
  assert.equal(c.get("a"), 10);
  assert.equal(c.get("c"), 3);
});

test("capacity of 1 keeps only the latest entry", () => {
  const c = new LRUCache(1);
  c.put("a", 1);
  c.put("b", 2);
  assert.equal(c.get("a"), undefined);
  assert.equal(c.get("b"), 2);
});

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.

```js
export class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) {
      return undefined;
    }
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    this.cache.delete(key);
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
  }
}
```

The user wants an implementation of an LRU (Least Recently Used) cache in JavaScript as an ES module.

Requirements:
1. Class name: `LRUCache`.
2. Constructor takes `capacity` (positive integer).
3. `get(key)`: returns value or `undefined`. Updates recency.
4. `put(key, value)`: inserts/updates value. Updates recency. Evicts LRU if capacity exceeded on insert.
5. Keys can be any valid Map key.

Implementation details:
- To achieve O(1) time complexity for both `get` and `put`, a common approach is to use a combination of a `Map` and a Doubly Linked List.
- However, since ES6 `Map` maintains insertion order, we can leverage that.
- If we use a `Map`:
    - `get(key)`: Check if key exists. If yes, delete it and re-insert it to move it to the end (most recently used). Return value.
    - `put(key, value)`: Check if key exists. If yes, delete it and re-insert it. If no, insert it. If size > capacity, delete the first entry (least recently used).
- This approach is O(1) amortized and very concise in modern JavaScript.

Let's verify the constraints.
- "Keys may be any value usable as a Map key." -> `Map` handles this natively.
- "capacity is a positive integer".

Algorithm using `Map`:
1. `constructor(capacity)`:
   - `this.capacity = capacity`
   - `this.cache = new Map()`

2. `get(key)`:
   - If `!this.cache.has(key)`, return `undefined`.
   - Store value: `const val = this.cache.get(key)`
   - Delete key: `this.cache.delete(key)`
   - Re-insert key: `this.cache.set(key, val)`
   - Return `val`

3. `put(key, value)`:
   - If `this.cache.has(key)`:
     - `this.cache.delete(key)` (to update recency)
   - `this.cache.set(key, value)`
   - If `this.cache.size > this.capacity`:
     - Get the first key (least recently used). In ES6 Map, `this.cache.keys().next().value` gives the first inserted key.
     - `this.cache.delete(firstKey)`

Let's double check the `Map` iteration order behavior.
MDN: "A Map object iterates items in insertion order — a for...of loop returns an array of [key, value] for each iteration in insertion order."
When we delete and re-insert, the item moves to the end of the insertion order.
So the first item in the Map is indeed the Least Recently Used (LRU).

Example trace:
`new LRUCache(2)` -> `cache = {}`
`put("a", 1)` -> `cache = {a:1}`
`put("b", 2)` -> `cache = {a:1, b:2}`
`get("a")` -> has "a"? yes. delete "a", set "a":1. `cache = {b:2, a:1}`. Return 1.
`put("c", 3)` -> has "c"? no. set "c":3. `cache = {b:2, a:1, c:3}`. Size 3 > 2. Delete first key ("b"). `cache = {a:1, c:3}`.
`get("b")` -> has "b"? no. Return undefined.
`get("a")` -> has "a"? yes. delete "a", set "a":1. `cache = {c:3, a:1}`. Return 1.
`get("c")` -> has "c"? yes. delete "c", set "c":3. `cache = {a:1, c:3}`. Return 3.

Matches the example logic perfectly.

Code structure:
```js
export class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) {
      return undefined;
    }
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
  }
}
```

Is there any edge case?
- Capacity 0? The prompt says "positive integer", so capacity >= 1.
- Keys being objects? Map handles object references correctly.
- `get` returning `undefined` vs not found? The prompt says "returns the stored value, or `undefined` if the key is not present". If a user stores `undefined` as a value, `get` should return `undefined`. My implementation does this because `this.cache.get(key)` returns the stored value (even if undefined), and we only return early if `!this.cache.has(key)`. Wait, if value is `undefined`, `this.cache.get(key)` is `undefined`. The logic holds.

Wait, check `get` logic again.
If `cache` has key `k` with value `undefined`.
`this.cache.has(k)` is true.
`const value = this.cache.get(k)` -> `undefined`.
`this.cache.delete(k)`
`this.cache.set(k, undefined)`
Return `undefined`.
Correct.

If `cache` does not have key `k`.
`this.cache.has(k)` is false.
Return `undefined`.
Correct.

The solution looks solid.

One small optimization/clean-up:
In `put`, checking `has` then `delete` then `set` is slightly redundant if we just `set` then check size, but we need to handle the "update existing key" case where we don't want to count it as a new entry for capacity purposes, but we do want to move it to the end.
Actually, if we just `set` an existing key in a Map, it updates the value but *does not* change the insertion order (recency) in some implementations?
Let's check MDN for Map.set behavior regarding order.
"If the key already exists in the Map, the value is updated. The key is not moved to the end of the iteration order."
So, to update recency on `put` for an existing key, we *must* delete and re-insert.
So the logic:
```js
if (this.cache.has(key)) {
  this.cache.delete(key);
}
this.cache.set(key, value);
```
is necessary.

Alternatively:
```js
this.cache.delete(key); // If it didn't exist, this is a no-op.
this.cache.set(key, value);
```
This is cleaner. If key exists, it's removed (updating recency later). If not, nothing happens. Then we set it.
Wait, if key exists, we delete it. Size decreases by 1. Then we set it. Size increases by 1. Net change 0.
If key doesn't exist, delete is no-op. Set increases size by 1.
This simplifies the logic.

Revised `put`:
```js
put(key, value) {
  this.cache.delete(key); // Remove if exists to update order later
  this.cache.set(key, value);
  if (this.cache.size > this.capacity) {
    const firstKey = this.cache.keys().next().value;
    this.cache.delete(firstKey);
  }
}
```
This is slightly more efficient/cleaner.

Revised `get`:
```js
get(key) {
  if (!this.cache.has(key)) return undefined;
  const value = this.cache.get(key);
  this.cache.delete(key);
  this.cache.set(key, value);
  return value;
}
```
Can we optimize `get`?
W
…[10433 chars elided]…
bject. It's cheap.
If performance was critical in a tight loop, a custom linked list might be preferred, but for a general coding task, Map is the expected answer for JS.

I will stick with the Map solution.

```js
export class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) {
      return undefined;
    }
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    this.cache.delete(key);
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
  }
}
```
Final check.
Prompt: "Implement an ES module solution.js exporting a least-recently-used cache class"
Code: `export class LRUCache ...`
Matches.

Prompt: "capacity is a positive integer"
Code: stores it.

Prompt: "get(key) returns the stored value, or undefined if the key is not present."
Code: checks has, returns value or undefined.

Prompt: "A successful get counts as a use: it marks the key as the most recently used."
Code: delete + set moves to end (MRU).

Prompt: "put(key, value) inserts or updates the entry and marks it most recently used."
Code: delete + set moves to end (MRU).

Prompt: "If adding a new key would exceed capacity, evict the least recently used entry first."
Code: checks size > capacity, deletes first key (LRU).

Prompt: "Updating an existing key never changes the number of entries (and refreshes its recency)."
Code: delete existing (size -1), set (size +1), net 0. Moves to end.

Prompt: "Keys may be any value usable as a Map key."
Code: uses Map.

All constraints satisfied.

One minor syntax thing: `this.cache.keys().next().value`.
If `this.cache` is empty, `next()` returns `{value: undefined, done: true}`.
But we only call this if `size > capacity` and `capacity >= 1`, so `size >= 2`. Map is not empty.
So `value` is valid.

Ready to generate output.