Design

3 problems · 4 approaches

Design Hit CounterMedium2 approaches

Problem

Design a counter with hit(timestamp) and getHits(timestamp), which returns the number of hits in the past 300 seconds (timestamps in (t − 300, t]). Timestamps are in seconds and arrive in non-decreasing order.

Example 1

Input:  hit(1), hit(2), hit(3), getHits(4), hit(300), getHits(300), getHits(301)
Output: 3, 4, 3

1. Queue of timestamps

Time O(1) amortisedSpace O(hits in the window)

Push each hit; on getHits drop timestamps older than 300 s from the front.

class HitCounter {
  constructor() { this.q = []; this.head = 0; }
  hit(t) { this.q.push(t); }
  getHits(t) {
    while (this.head < this.q.length && this.q[this.head] <= t - 300) this.head++;
    return this.q.length - this.head;
  }
}

2. Fixed 300-slot ring buffer

Time hit O(1), getHits O(300)Space O(300)

Bounded memory under heavy traffic: slot t % 300 stores [time, count]; reset a slot when its time is stale.

class HitCounter {
  constructor() { this.times = new Array(300).fill(0); this.counts = new Array(300).fill(0); }
  hit(t) {
    const i = t % 300;
    if (this.times[i] !== t) { this.times[i] = t; this.counts[i] = 0; }
    this.counts[i]++;
  }
  getHits(t) {
    let total = 0;
    for (let i = 0; i < 300; i++) if (t - this.times[i] < 300) total += this.counts[i];
    return total;
  }
}

The follow-up "what if hits per second are huge?" is asking for this version.

Insert Delete GetRandom O(1)Medium1 approach

Problem

Design a set with insert(val), remove(val) (each returns whether it changed the set) and getRandom() (returns each current element with equal probability). Every operation must be O(1) on average.

Example 1

Input:  insert(1), remove(2), insert(2), getRandom(), remove(1), insert(2), getRandom()
Output: true, false, true, 1 or 2, true, false, 2

1. Array + value→index map

Time O(1) average for every operationSpace O(n)

The array gives O(1) random access. To delete in O(1), move the last element into the removed slot and update its index.

class RandomizedSet {
  constructor() { this.arr = []; this.idx = new Map(); }
  insert(v) {
    if (this.idx.has(v)) return false;
    this.idx.set(v, this.arr.length);
    this.arr.push(v);
    return true;
  }
  remove(v) {
    if (!this.idx.has(v)) return false;
    const i = this.idx.get(v), last = this.arr[this.arr.length - 1];
    this.arr[i] = last;
    this.idx.set(last, i);
    this.arr.pop();
    this.idx.delete(v);
    return true;
  }
  getRandom() {
    return this.arr[Math.floor(Math.random() * this.arr.length)];
  }
}

LFU CacheHard1 approach

Problem

Design a Least Frequently Used cache with a fixed capacity. get(key) returns the value, or −1 if absent. put(key, value) inserts or updates a key. When the cache is full, evict the key with the lowest use count; break ties by evicting the least recently used of them. Every get or put on a key increases its count. Both operations must be O(1).

Example 1

Input:  capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), get(3), put(4,4), get(1), get(3), get(4)
Output: 1, -1, 3, -1, 3, 4

1. Frequency buckets of insertion-ordered sets

Time O(1) per operationSpace O(capacity)

key → [value, freq]; freq → Set of keys (JS Sets keep insertion order, so the first key is the least recent). Track minFreq; evict the first key of the minFreq bucket. A new key resets minFreq to 1.

class LFUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.vals = new Map();    // key -> [value, freq]
    this.buckets = new Map(); // freq -> Set(keys), oldest first
    this.minFreq = 0;
  }
  #touch(key) {
    const entry = this.vals.get(key), f = entry[1];
    this.buckets.get(f).delete(key);
    if (f === this.minFreq && this.buckets.get(f).size === 0) this.minFreq++;
    entry[1] = f + 1;
    if (!this.buckets.has(f + 1)) this.buckets.set(f + 1, new Set());
    this.buckets.get(f + 1).add(key);
  }
  get(key) {
    if (!this.vals.has(key)) return -1;
    this.#touch(key);
    return this.vals.get(key)[0];
  }
  put(key, value) {
    if (this.cap === 0) return;
    if (this.vals.has(key)) {
      this.vals.get(key)[0] = value;
      this.#touch(key);
      return;
    }
    if (this.vals.size === this.cap) {
      const bucket = this.buckets.get(this.minFreq);
      const evict = bucket.values().next().value;
      bucket.delete(evict);
      this.vals.delete(evict);
    }
    this.vals.set(key, [value, 1]);
    if (!this.buckets.has(1)) this.buckets.set(1, new Set());
    this.buckets.get(1).add(key);
    this.minFreq = 1;
  }
}

In other languages the buckets are doubly linked lists; JS Set insertion order gives the same O(1) behaviour.