Design Data Structures: LRU, LFU and Friends

// Template 1: a hash map for O(1) lookup + a doubly linked list for O(1) "move to front" and "evict the oldest".
// head.next is the most recently used entry, tail.prev the least recently used. Sentinels remove edge cases.
class Entry {
  constructor(key, val) {
    this.key = key;
    this.val = val;
    this.prev = null;
    this.next = null;
  }
}

export class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.entries = new Map(); // key -> Entry
    this.head = new Entry(0, 0);
    this.tail = new Entry(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  unlink(e) {
    e.prev.next = e.next;
    e.next.prev = e.prev;
  }

  pushFront(e) {
    e.prev = this.head;
    e.next = this.head.next;
    this.head.next.prev = e;
    this.head.next = e;
  }

  get(key) {
    const e = this.entries.get(key);
    if (!e) return -1;
    this.unlink(e); // a read is a use: move to the front
    this.pushFront(e);
    return e.val;
  }

  put(key, value) {
    const old = this.entries.get(key);
    if (old) {
      old.val = value;
      this.unlink(old);
      this.pushFront(old);
      return;
    }
    if (this.entries.size === this.capacity) {
      const lru = this.tail.prev; // nobody touched it for the longest time
      this.unlink(lru);
      this.entries.delete(lru.key); // the node remembers its key for exactly this
    }
    const e = new Entry(key, value);
    this.entries.set(key, e);
    this.pushFront(e);
  }
}

// The shortcut: a JavaScript Map iterates in insertion order, so delete + set moves a key to the end.
export class LRUCacheMap {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // oldest key first
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value); // now the newest
    return value;
  }

  put(key, value) {
    this.map.delete(key);
    if (this.map.size === this.capacity) this.map.delete(this.map.keys().next().value); // evict the oldest
    this.map.set(key, value);
  }
}

// Template 2: group keys into buckets by use count. A hit moves a key from bucket c to bucket c + 1 only,
// so eviction needs just the lowest non-empty count (minCount) and, inside it, the oldest key.
export class LFUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.values = new Map(); // key -> value
    this.counts = new Map(); // key -> use count
    this.buckets = new Map(); // count -> Set of keys, oldest first (Sets keep insertion order)
    this.minCount = 0;
  }

  touch(key) {
    const c = this.counts.get(key);
    const bucket = this.buckets.get(c);
    bucket.delete(key);
    if (bucket.size === 0) {
      this.buckets.delete(c);
      if (this.minCount === c) this.minCount = c + 1; // the key itself just moved to c + 1
    }
    this.counts.set(key, c + 1);
    if (!this.buckets.has(c + 1)) this.buckets.set(c + 1, new Set());
    this.buckets.get(c + 1).add(key);
  }

  get(key) {
    if (!this.values.has(key)) return -1;
    this.touch(key);
    return this.values.get(key);
  }

  put(key, value) {
    if (this.capacity === 0) return;
    if (this.values.has(key)) {
      this.values.set(key, value);
      this.touch(key);
      return;
    }
    if (this.values.size === this.capacity) {
      const bucket = this.buckets.get(this.minCount);
      const oldest = bucket.values().next().value; // fewest uses, and the oldest among ties
      bucket.delete(oldest);
      if (bucket.size === 0) this.buckets.delete(this.minCount);
      this.values.delete(oldest);
      this.counts.delete(oldest);
    }
    this.values.set(key, value);
    this.counts.set(key, 1);
    if (!this.buckets.has(1)) this.buckets.set(1, new Set());
    this.buckets.get(1).add(key);
    this.minCount = 1; // a new key always has the lowest count
  }
}

// Template 3: keep every key's history in time order (appends keep it sorted), then binary search it.
// lastAtOrBefore returns the index of the newest entry with time <= t, or -1.
export function lastAtOrBefore(history, t) {
  let lo = 0;
  let hi = history.length; // first index whose time is greater than t
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (history[mid][0] <= t) lo = mid + 1;
    else hi = mid;
  }
  return lo - 1;
}

export class TimeMap {
  constructor() {
    this.history = new Map(); // key -> [[time, value], ...] sorted by time
  }

  set(key, value, time) {
    if (!this.history.has(key)) this.history.set(key, []);
    this.history.get(key).push([time, value]);
  }

  get(key, time) {
    const list = this.history.get(key);
    if (!list) return '';
    const i = lastAtOrBefore(list, time);
    return i === -1 ? '' : list[i][1];
  }
}

// Template 4: O(1) insert, remove and random pick. An array makes random picks easy, a map from value to index
// makes removal easy. Remove by copying the LAST element into the hole, then pop.
export class RandomizedSet {
  constructor() {
    this.items = [];
    this.index = new Map(); // value -> position in items
  }

  insert(val) {
    if (this.index.has(val)) return false;
    this.index.set(val, this.items.length);
    this.items.push(val);
    return true;
  }

  remove(val) {
    if (!this.index.has(val)) return false;
    const i = this.index.get(val);
    const last = this.items[this.items.length - 1];
    this.items[i] = last; // fill the hole
    this.index.set(last, i); // tell the map where the moved element lives now
    this.items.pop();
    this.index.delete(val); // after the set above: if val was last, it must end up deleted
    return true;
  }

  getRandom() {
    return this.items[Math.floor(Math.random() * this.items.length)];
  }
}

// Template 5: auxiliary state. Store, with every pushed value, the answer for "everything below me":
// the entry never changes while it lives, so pop needs no repair. O(1) push, pop, top, min and max.
export class MinMaxStack {
  constructor() {
    this.items = []; // [value, min so far, max so far]
  }

  push(val) {
    const top = this.items[this.items.length - 1];
    this.items.push([val, top ? Math.min(val, top[1]) : val, top ? Math.max(val, top[2]) : val]);
  }

  pop() {
    return this.items.pop()[0];
  }

  top() {
    return this.items[this.items.length - 1][0];
  }

  getMin() {
    return this.items[this.items.length - 1][1];
  }

  getMax() {
    return this.items[this.items.length - 1][2];
  }
}