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.

To solve this problem, we need to implement an LRU (Least Recently Used) cache in JavaScript. The LRU cache is a data structure that maintains a collection of key-value pairs and evicts the least recently used entry when the cache reaches its capacity. The cache should support two main operations: `get` and `put`.

### Approach
The approach to implement the LRU cache involves using a combination of a Map to store the key-value pairs and an array to keep track of the order of usage. Here's a detailed breakdown of the approach:

1. **Data Structures**:
   - **Map**: To store the key-value pairs for efficient access and updates.
   - **Array**: To maintain the order of usage, where the first element is the least recently used and the last element is the most recently used.

2. **Operations**:
   - **get(key)**: This operation retrieves the value associated with the given key. If the key exists, it updates the key's position to the end of the usage array, marking it as the most recently used. If the key does not exist, it returns `undefined`.
   - **put(key, value)**: This operation inserts a new key-value pair or updates an existing one. If the key already exists, it updates its value and moves it to the end of the usage array. If the key is new and the cache is full, it evicts the least recently used key (the first element in the usage array).

### Solution Code
```javascript
export class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.usageOrder = [];
  }

  get(key) {
    if (this.map.has(key)) {
      const value = this.map.get(key);
      const index = this.usageOrder.indexOf(key);
      if (index !== -1) {
        this.usageOrder.splice(index, 1);
        this.usageOrder.push(key);
      }
      return value;
    }
    return undefined;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.set(key, value);
      const index = this.usageOrder.indexOf(key);
      if (index !== -1) {
        this.usageOrder.splice(index, 1);
        this.usageOrder.push(key);
      }
    } else {
      this.map.set(key, value);
      this.usageOrder.push(key);
      if (this.usageOrder.length > this.capacity) {
        const lruKey = this.usageOrder.shift();
        this.map.delete(lruKey);
      }
    }
  }
}
```

### Explanation
- **Constructor**: Initializes the cache with a given capacity, an empty Map to store key-value pairs, and an empty array to track the order of usage.
- **get(key)**: Checks if the key exists in the Map. If it does, the key is moved to the end of the usage array to mark it as the most recently used. If the key does not exist, it returns `undefined`.
- **put(key, value)**: Updates the value of an existing key or adds a new key-value pair. If the key exists, it updates the value and moves the key to the end of the usage array. If the key is new and the cache is full, the least recently used key (first element in the usage array) is evicted.

This approach ensures that both `get` and `put` operations efficiently manage the cache's usage order and capacity constraints.

Okay, I need to implement an LRU cache in JavaScript as an ES module. The class should have a constructor that takes a capacity, and methods get and put. Let me think about how to approach this.

First, I remember that LRU caches can be implemented using a doubly linked list to keep track of the order of usage. But maybe there's a simpler way using a Map to store the key-value pairs along with their usage order.

Wait, another approach is to maintain a list of keys in the order they were used. Every time a key is accessed (either via get or put), it's moved to the end of the list, making it the most recently used. When the cache is full and a new key is added, the first key in the list is evicted.

So, I'll need a data structure to keep track of the order. Maybe an array where the first element is the least recently used and the last is the most. But arrays in JavaScript are not the most efficient for moving elements around, but for the sake of simplicity, maybe it's manageable.

Let me outline the steps:

1. The constructor takes a capacity. I'll store this as a property, say this.capacity.

2. I'll need a way to store the key-value pairs. A Map seems suitable because it can handle any key type and provides O(1) access time.

3. Additionally, I'll need an ordered list (like an array) to track the order of usage. Each time a key is accessed (get or put), it's moved to the end of the array. If the key is already present, it's moved to the end.

So, the steps for get(key):

- Check if the key exists in the Map.
- If it does, get the value and move the key to the end of the usage array.
- Return the value.
- If not, return undefined.

For put(key, value):

- If the key exists in the Map, update its value and move it to the end of the array.
- If not, add the key to the Map and the end of the array.
- If adding the new key exceeds the capacity, remove the first key in the array from the Map.

Wait, but when a key is updated (put), it's considered as a use, so it's moved to the end. So, the same logic as get applies.

So, the data structures I need are:

- A Map to store key-value pairs.
- An array to track the order of usage.

Let me think about the initial setup:

In the constructor:

- this.capacity = capacity;
- this.map = new Map();
- this.usageOrder = [];

For get(key):

- If the map has the key, get the value.
- Remove the key from usageOrder array and push it to the end.
- Return the value.
- Else, return undefined.

Wait, but how to efficiently remove the key from the usageOrder array? Because if the array is large, searching for the key each time could be O(n), which might not be efficient. Hmm, but for the problem's constraints, maybe it's acceptable.

Alternatively, perhaps using a linked list would be better for O(1) removal, but that's more complex.

Alternatively, maybe I can keep the usageOrder as a list where each element is a key, and when a key is accessed, it's moved to the end. So, for get:

- Check if key is in map.
- If yes, get value.
- Find the index of key in usageOrder, remove it, and push to end.
- Return value.

Same for put.

But for large caches, this could be slow because searching the array is O(n). But given that the problem doesn't specify performance constraints, maybe it's acceptable.

Alternatively, perhaps using a Map to track the order. But that might complicate things.

Wait, another approach: maintain a list where each node contains the key and pointers to previous and next nodes. But that's more complex to implement.

Hmm, perhaps for the sake of simplicity, I'll proceed with the array approach, even though it's O(n) for get and put operations.

So, let's outline the code.

Constructor:

export class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.usageOrder = [];
  }

get(key) {
  if (this.map.has(key)) {
    const value = this.map.get(key);
    // Move to end of usageOrder
    const index = this.usageOrder.indexOf(key);
    if (index !== -1) {
      this.usageOrder.splice(index, 1);
      this.usageOrder.push(key);
    }
    return value;
  }
  return undefined;
}

put(key, value) {
  if (this.map.has(key)) {
    // Update value and move to end
    this.map.set(key, value);
    const index = this.usageOrder.indexOf(key);
    if (index !== -1) {
      this.usageOrder.splice(index, 1);
      this.usageOrder.push(key);
    }
  } else {
    this.map.set(key, value);
    this.usageOrder.push(key);
    // Check if capacity exceeded
    if (this.usageOrder.length > this.capacity) {
      const lruKey = this.usageOrder.shift();
      this.map.delete(lruKey);
    }
  }
}
}

Wait, but in the example given:

c.put("a", 1);
c.put("b", 2);
c.get("a"); // a is moved to end, usageOrder is [b, a]
c.put("c", 3); // capacity is 2, so after adding c, usageOrder is [b, a, c], but then we check if length > capacity (2). So we shift b, and then the usageOrder becomes [a, c].

Wait, no. Let's see:

After putting a and b, usageOrder is [a, b].

Then get a: usageOrder becomes [b, a].

Then put c: since it's a new key, we add to usageOrder, making it [b, a, c]. Then, since capacity is 2, we shift the first element (b), and the usageOrder becomes [a, c].

So, the map now has a and c.

Then, get b returns undefined.

So, the code seems to handle that.

But wait, in the put function, when adding a new key, after pushing to usageOrder, we check if the length exceeds capacity. If so, we shift the first element.

Yes.

But what about when the capacity is zero? Well, the problem says capacity is a positive integer, so we don't need to handle that.

Another test case: when the capacity is 1.

c = new LRUCache(1);
c.put("a", 1);
c.put("b", 2); // a is evicted
c.get("a"); // undefined
c.get("b"); // 2

Yes.

Another test case: when the same key is put multiple times.

c = new LRUCache(2);
c.put("a", 1);
c.put("a", 2); // updates the value, and moves to end. So usageOrder remains [a], but wait, no. Initially, usageOrder is [a]. Then, after put a again, it's in the map, so we update the value and move to end. So usageOrder remains [a].

Wait, no. Because in the put functio
…[1462 chars elided]…
 we update a's value to 2, and move to end. So usageOrder is [a]. Then, the capacity is 1, so no eviction.

Wait, no. Because when putting "b", since it's a new key, the code will add it to the usageOrder, making it [a, b], then check if length exceeds capacity (1). So, it shifts a, and the usageOrder becomes [b]. The map now has b.

Wait, no. Let me re-examine the code.

In the put function:

if (this.map.has(key)) {
  // update value and move to end
} else {
  // add to map and usageOrder
  // then check capacity
}

So, when adding "b" after "a", the code will add "b" to the usageOrder, making it [a, b]. Then, since capacity is 1, the length is 2, which is >1. So, shift the first element (a), and the usageOrder becomes [b].

So, the map now has only "b".

So, the code correctly evicts "a".

Yes.

So, the code seems to handle that.

Another test case: when the key is not present in get.

c = new LRUCache(2);
c.put("a", 1);
c.put("b", 2);
c.get("c"); // returns undefined, and the usageOrder remains [a, b].

Yes.

So, the code seems to handle all these cases.

But wait, in the get function, when the key is not present, we don't modify the usageOrder. That's correct.

Now, what about the performance? For each get or put, the code does an indexOf, which is O(n). For large n, this could be a problem, but perhaps for the problem's constraints, it's acceptable.

Alternatively, to optimize, perhaps we can use a linked list or a more efficient data structure. But that's more complex.

But given the problem statement, perhaps the array approach is sufficient.

So, the code I wrote should work.

Wait, but in the example given:

After c.put("a",1), c.put("b",2), c.get("a"), the usageOrder is [b, a].

Then c.put("c",3) adds c to the end, making [b, a, c], then since capacity is 2, we shift b, so the usageOrder becomes [a, c].

So, the map now has a and c.

Then, c.get("b") returns undefined.

Yes.

So, the code should handle that.

I think this should work. Now, let me write the code as per the required function signatures.