ts-03-lru-cache

1.000

7/7 tests· data-structures

Proposed solution

```ts
export class LRUCache<K, V> {
  private capacity: number;
  private cache: Map<K, V>;
  private order: K[];

  constructor(capacity: number) {
    if (capacity < 1) {
      throw new RangeError("Capacity must be at least 1");
    }
    this.capacity = capacity;
    this.cache = new Map<K, V>();
    this.order = [];
  }

  get(key: K): V | undefined {
    if (!this.cache.has(key)) {
      return undefined;
    }

    // Move to end (most recently used)
    const index = this.order.indexOf(key);
    this.order.splice(index, 1);
    this.order.push(key);

    return this.cache.get(key)!;
  }

  put(key: K, value: V): void {
    if (this.cache.has(key)) {
      // Update existing key
      const index = this.order.indexOf(key);
      this.order.splice(index, 1);
      this.order.push(key);
      this.cache.set(key, value);
    } else {
      // New key
      if (this.cache.size >= this.capacity) {
        // Remove least recently used
        const lruKey = this.order.shift()!;
        this.cache.delete(lruKey);
      }
      
      this.order.push(key);
      this.cache.set(key, value);
    }
  }

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

Test output (stdout)

TAP version 13
# Subtest: stores and retrieves values
ok 1 - stores and retrieves values
  ---
  duration_ms: 0.393032
  type: 'test'
  ...
# Subtest: missing key returns undefined
ok 2 - missing key returns undefined
  ---
  duration_ms: 0.06867
  type: 'test'
  ...
# Subtest: evicts least-recently-used on overflow
ok 3 - evicts least-recently-used on overflow
  ---
  duration_ms: 0.04839
  type: 'test'
  ...
# Subtest: get counts as a use and protects from eviction
ok 4 - get counts as a use and protects from eviction
  ---
  duration_ms: 0.04151
  type: 'test'
  ...
# Subtest: put updates existing key and marks it used
ok 5 - put updates existing key and marks it used
  ---
  duration_ms: 0.05478
  type: 'test'
  ...
# Subtest: capacity of 1 keeps only the newest
ok 6 - capacity of 1 keeps only the newest
  ---
  duration_ms: 0.397493
  type: 'test'
  ...
# Subtest: invalid capacity throws RangeError
ok 7 - invalid capacity throws RangeError
  ---
  duration_ms: 0.206671
  type: 'test'
  ...
1..7
# tests 7
# suites 0
# pass 7
# fail 0
# cancelled 0
# skipped 0
# todo 0
# duration_ms 77.079973

System prompt

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.