Marauder Bot

Problem

Design a fixed-capacity cache that supports getting a value by key and putting a key-value pair, both in constant time. Every access, whether get or put, counts as using that key. When put would exceed capacity, evict whichever key has gone longest unused before inserting the new one.

Example. With capacity 2: put (1, 1), put (2, 2), then get 1 returns 1 and marks key 1 as most recently used. A subsequent put (3, 3) evicts key 2, since it is now the least recently used, leaving keys 1 and 3 in the cache.

Key idea

Tracking usage order with a plain list and scanning for the oldest entry on every eviction works, but that scan costs time proportional to cache size, defeating the constant-time requirement. The fix combines two structures: a hash map from key to node gives O(1) lookup, and a doubly linked list ordered from most- to least-recently-used gives O(1) reordering.

On every get or put of an existing key, unlink that key's node from wherever it sits and reattach it at the most-recently-used end, an O(1) operation because a doubly linked list holds a pointer to both neighbors. When a put exceeds capacity, the node at the least-recently-used end is evicted from both structures together. A singly linked list cannot support this: unlinking an interior node needs a pointer to the node before it, which only a doubly linked list provides.

Solution

class DListNode {
  key: number;
  val: number;
  prev: DListNode | null = null;
  next: DListNode | null = null;
  constructor(key: number, val: number) {
    this.key = key;
    this.val = val;
  }
}

class LRUCache {
  private capacity: number;
  private map: Map<number, DListNode>; // key to node, for O(1) lookup
  private head: DListNode; // sentinel; head.next is the most-recently-used node
  private tail: DListNode; // sentinel; tail.prev is the least-recently-used node

  constructor(capacity: number) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new DListNode(0, 0);
    this.tail = new DListNode(0, 0);
    this.head.next = this.tail; // link the sentinels so the list is never empty
    this.tail.prev = this.head;
  }

  get(key: number): number {
    const node = this.map.get(key);
    if (node === undefined) {
      return -1;
    }
    this.moveToFront(node);
    return node.val;
  }

  put(key: number, value: number): void {
    const existing = this.map.get(key);
    if (existing !== undefined) {
      existing.val = value;
      this.moveToFront(existing);
      return;
    }

    if (this.map.size === this.capacity) {
      const lru = this.tail.prev as DListNode; // node right before tail is least recently used
      this.unlink(lru);
      this.map.delete(lru.key);
    }

    const node = new DListNode(key, value);
    this.map.set(key, node);
    this.attachToFront(node);
  }

  private unlink(node: DListNode): void {
    const prev = node.prev as DListNode;
    const next = node.next as DListNode;
    prev.next = next;
    next.prev = prev;
  }

  private attachToFront(node: DListNode): void {
    const first = this.head.next as DListNode;
    node.prev = this.head;
    node.next = first;
    this.head.next = node;
    first.prev = node;
  }

  private moveToFront(node: DListNode): void {
    this.unlink(node);
    this.attachToFront(node);
  }
}

Complexity

Time: O(1) per get and put. One hash lookup plus a constant amount of pointer rewiring.
Space: O(capacity). One hash map entry and one list node per cached key.

Watch out for

Sentinel head and tail nodes remove the need to special-case an empty or single-entry cache.
Every insertion and eviction must update the map and the list together, or the two structures fall out of sync.
A get on a missing key must not insert anything or affect recency ordering.

Pattern

The hash map plus doubly linked list combination is the standard design for O(1) lookup with O(1) recency-based eviction, and the same pairing underlies related design problems such as an LFU cache.

LRU Cache