ts-03-lru-cache
0.714
Challenge · difficulty 3/5
# 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.
tests/solution.test.ts
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);
});
Proposed solution
```ts
export class LRUCache<K, V> {
private readonly 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<K, V>();
}
get(key: K): V | undefined {
if (!this.map.has(key)) {
return undefined;
}
const val = this.map.get(key)!;
this.map.set(key, val);
return val;
}
put(key: K, value: V): void {
if (this.map.has(key)) {
this.map.set(key, value);
} 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;
}
}
```Test output (stdout)
TAP version 13
# Subtest: stores and retrieves values
ok 1 - stores and retrieves values
---
duration_ms: 0.361359
type: 'test'
...
# Subtest: missing key returns undefined
ok 2 - missing key returns undefined
---
duration_ms: 0.05981
type: 'test'
...
# Subtest: evicts least-recently-used on overflow
ok 3 - evicts least-recently-used on overflow
---
duration_ms: 0.04522
type: 'test'
...
# Subtest: get counts as a use and protects from eviction
not ok 4 - get counts as a use and protects from eviction
---
duration_ms: 0.838038
type: 'test'
location: '/tmp/llmlab-ts-03-lru-cache-ogpg8sxw/solution.test.ts:1:604'
failureType: 'testCodeFailure'
error: |-
Expected values to be strictly equal:
2 !== undefined
code: 'ERR_ASSERTION'
name: 'AssertionError'
actual: 2
operator: 'strictEqual'
stack: |-
TestContext.<anonymous> (/tmp/llmlab-ts-03-lru-cache-ogpg8sxw/solution.test.ts:36:10)
Test.runInAsyncScope (node:async_hooks:227:14)
Test.run (node:internal/test_runner/test:1306:25)
Test.processPendingSubtests (node:internal/test_runner/test:897:18)
Test.postRun (node:internal/test_runner/test:1447:19)
Test.run (node:internal/test_runner/test:1372:12)
async Test.processPendingSubtests (node:internal/test_runner/test:897:7)
...
# Subtest: put updates existing key and marks it used
not ok 5 - put updates existing key and marks it used
---
duration_ms: 0.16155
type: 'test'
location: '/tmp/llmlab-ts-03-lru-cache-ogpg8sxw/solution.test.ts:1:841'
failureType: 'testCodeFailure'
error: |-
Expected values to be strictly equal:
undefined !== 10
code: 'ERR_ASSERTION'
name: 'AssertionError'
expected: 10
operator: 'strictEqual'
stack: |-
TestContext.<anonymous> (/tmp/llmlab-ts-03-lru-cache-ogpg8sxw/solution.test.ts:47:10)
Test.runInAsyncScope (node:async_hooks:227:14)
Test.run (node:internal/test_runner/test:1306:25)
Test.processPendingSubtests (node:internal/test_runner/test:897:18)
Test.postRun (node:internal/test_runner/test:1447:19)
Test.run (node:internal/test_runner/test:1372:12)
async Test.processPendingSubtests (node:internal/test_runner/test:897:7)
...
# Subtest: capacity of 1 keeps only the newest
ok 6 - capacity of 1 keeps only the newest
---
duration_ms: 0.065619
type: 'test'
...
# Subtest: invalid capacity throws RangeError
ok 7 - invalid capacity throws RangeError
---
duration_ms: 0.17707
type: 'test'
...
1..7
# tests 7
# suites 0
# pass 5
# fail 2
# cancelled 0
# skipped 0
# todo 0
# duration_ms 85.976938