Implement least-recently-used cache

A small class that uses Map iteration order as the recency list. Touching a key reinserts it; eviction removes the first key.

class LruCache<K, V> {
  // The trick: JavaScript's Map preserves insertion order. Re-insert on read
  // (delete + set) and the iteration order *is* the LRU order. The oldest
  // item is always cache.keys().next().value.
  private store = new Map<K, V>();

  constructor(private capacity: number) {
    if (!Number.isInteger(capacity) || capacity < 1) {
      throw new Error('capacity must be a positive integer');
    }
  }

  get(key: K): V | undefined {
    const value= this.store.get(key);
    if (value= undefined) return undefined;
    // Touching a key promotes it to most-recently-used.
    this.store.delete(key);
    this.store.set(key, value);
    return value;
  }

  set(key: K, value: V): void {
    if (this.store.has(key)) this.store.delete(key);
    this.store.set(key, value);
    if (this.store.size > this.capacity) {
      const oldest = this.store.keys().next().value;
      if (oldest !== undefined) this.store.delete(oldest);
    }
  }

  has(key: K): boolean {
    return this.store.has(key);
  }

  delete(key: K): boolean {
    return this.store.delete(key);
  }

  keys(): K[] {
    return Array.from(this.store.keys());
  }

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

function createLruCache<K, V>(capacity: number): LruCache<K, V> {
  return new LruCache<K, V>(capacity);
}

Edit the implementation and run the tests directly in the browser. For system design questions, the playground focuses on the core state/data logic that the UI would call.

class LruCache<K, V> {
  // The trick: JavaScript's Map preserves insertion order. Re-insert on read
  // (delete + set) and the iteration order *is* the LRU order. The oldest
  // item is always cache.keys().next().value.
  private store = new Map<K, V>();

  constructor(private capacity: number) {
    if (!Number.isInteger(capacity) || capacity < 1) {
      throw new Error('capacity must be a positive integer');
    }
  }

  get(key: K): V | undefined {
    const value = this.store.get(key);
    if (value === undefined) return undefined;
    // Touching a key promotes it to most-recently-used.
    this.store.delete(key);
    this.store.set(key, value);
    return value;
  }

  set(key: K, value: V): void {
    if (this.store.has(key)) this.store.delete(key);
    this.store.set(key, value);
    if (this.store.size > this.capacity) {
      const oldest = this.store.keys().next().value;
      if (oldest !== undefined) this.store.delete(oldest);
    }
  }

  has(key: K): boolean {
    return this.store.has(key);
  }

  delete(key: K): boolean {
    return this.store.delete(key);
  }

  keys(): K[] {
    return Array.from(this.store.keys());
  }

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

function createLruCache<K, V>(capacity: number): LruCache<K, V> {
  return new LruCache<K, V>(capacity);
}

Convert the answer into observable behavior. In a mid-senior interview, say which behaviors are covered by unit tests, interaction tests, accessibility checks, and one browser smoke path.

import { describe, it, expect } from 'vitest';

describe('LruCache', () => {
  it('evicts the least recently used key when capacity is exceeded', () => {
    const cache = new LruCache<string, number>(2);
    cache.set('a', 1);
    cache.set('b', 2);
    cache.get('a'); // a is now MRU
    cache.set('c', 3);
    expect(cache.has('b')).toBe(false);
    expect(cache.keys()).toEqual(['a', 'c']);
  });

  it('updates an existing key without evicting', () => {
    const cache = new LruCache<string, number>(2);
    cache.set('a', 1);
    cache.set('b', 2);
    cache.set('a', 99);
    expect(cache.size).toBe(2);
    expect(cache.get('a')).toBe(99);
  });

  it('rejects non-positive capacity', () => {
    expect(() => new LruCache<string, number>(0)).toThrow();
    expect(() => new LruCache<string, number>(-1)).toThrow();
  });

  it('returns undefined for missing keys without changing order', () => {
    const cache = new LruCache<string, number>(2);
    cache.set('a', 1);
    cache.set('b', 2);
    expect(cache.get('missing')).toBeUndefined();
    expect(cache.keys()).toEqual(['a', 'b']);
  });
});

Tests whether you can turn a familiar utility into a precise contract instead of coding only the happy path.

• Define the function signature before coding.
• Do not rely on global mutable state unless it is part of the returned closure.
• Explain time and space cost for the common path.

• Write the smallest public contract first.
• Cover empty input, repeated calls, thrown errors, and cleanup behavior.
• Keep implementation readable enough to narrate under interview pressure.

• A compact implementation is attractive, but explicit state names are easier to debug live.
• Supporting every possible input can distract from the core contract; state the scope before coding.

• No arguments or undefined callbacks.
• Synchronous throw inside the wrapped function.
• Repeated calls before the previous result settles.

• Happy path with representative inputs.
• Boundary input and repeated invocation.
• Cleanup or cancellation if timers or promises are involved.

• How would you expose cancellation?
• How would the API change for React usage?