Machine coding · Caches and stores

Multi-level cache with pluggable eviction

Reported once
Strategy
Chain of responsibility
Factory
1 source

One candidate write-up. Treat it as a single data point.

The prompt

Build a cache made of several levels, each with its own fixed capacity, holding string keys and values. A read searches from the top level downward and promotes a hit to the top. A write pushes whatever it evicts down to the next level, and a new level is created on demand up to a configured maximum. A delete removes the key from every level. The eviction rule must be pluggable, with least frequently used required.

Restated in our own words, not a quote from PhonePe or any page. The answer below is written for this site.

Try it first.The answer is covered until you pick. Talk it through against a 60 minute clock, or just read it.

Clarify first

Pin the scope down before you name a single class.

Questions to ask: is capacity counted in entries or bytes? Is the number of levels fixed, or do levels appear as needed, and what happens to an entry pushed out of the last level? Does a read that hits the top level need any promotion work? Can each level use a different eviction rule? What should a write to a key that already sits in a lower level do? Is the cache used from one thread or many?

Assumed scope: capacities are entry counts given as a list, the list length is the maximum number of levels, and a level is created only when something is first evicted from the one above it. An entry evicted from the last level is dropped and handed back to the caller. All levels use the same kind of policy but each has its own instance. A write replaces any existing copy, restarts its frequency at one and puts the single new copy at the top. Invalid capacities are rejected up front. Single threaded. Out of scope: expiry, byte sizing, persistence and hit statistics.

Entities and relationships

Who owns what, and who talks to whom.

MultiLevelCache is the facade. It owns the ordered list of levels, the list of capacities and a policy factory, and exposes get, put and delete.
CacheLevel owns one map of entries, a fixed capacity and one policy instance. Its put returns the entry it had to evict, if any.
EvictionPolicy is the interface a level talks to: touch, remove and evict. It sees keys only, never values.
LruPolicy implements it with a Map whose insertion order is the recency order.
LfuPolicy implements it with a doubly linked list of frequency buckets, each bucket holding a Set of keys.

Relationships: the cache has many levels, each level has one policy created by the factory function the cache was given, so a level never names a concrete policy class.

The design

The class map, the main flow and the patterns that earn their place.

Class map of the multi-level cacheThe cache owns the levels, each level asks its policy which key to evict, and a factory builds the policies.

The cache owns an ordered list of levels, created lazily up to the configured maximum.
A full level asks its policy for a victim and hands the evicted entry to the next level.

Open on the whiteboardAll 2 diagrams on one tidy board, with a step-by-step walkthrough.

The key separation is between where entries live and which entry leaves. CacheLevel holds the data and the capacity and asks its policy one question: which key goes. That is the Strategy pattern, and it earns its place because LRU and LFU differ only in the bookkeeping behind three methods: touch(key) on an insert or hit, remove(key) on a delete or promotion, and evict() to return and forget the victim. The cache receives a factory function, so every level gets its own policy instance and a new policy is one new class with no edits elsewhere.

LruPolicy keeps keys in a Map. Touching a key deletes and re-inserts it, so the first key in iteration order is always the least recently used one, and every step is O(1) amortised. LfuPolicy keeps a doubly linked list of buckets ordered by frequency, each bucket holding a Set of keys with that count. A touch moves the key to the bucket for count plus one, creating it next to the old bucket if it does not exist, and unlinks a bucket that became empty. The head bucket always has the lowest frequency, so evict reads the first key of the head. A Set keeps insertion order, so ties go to the key that has sat at that frequency longest. Every operation is O(1) and none scans for the minimum, which a count map with a minimum pointer cannot promise once arbitrary keys can be deleted.

The levels form a simple chain: a read, or an entry that was pushed out, moves down until some level handles it.

get finds the first level that holds the key. A miss returns no value. A hit in the top level only touches the policy, so its frequency is kept.
A hit lower down removes the entry from that level, which frees one slot, then inserts it at the top.
insert puts the entry into level 0. If that level is full its policy picks a victim, and the victim is inserted into level 1, and so on. Level k plus 1 is created only when something is first pushed out of level k. Past the last allowed level the entry is dropped and returned.
put deletes the key everywhere first, so no stale copy remains lower down, then inserts at the top.
delete removes the key from every level and reports whether it was found.

Each operation touches at most L levels, so it costs O(L) with L a small constant. The trade-off is that frequency is kept per level and restarts at one after a promotion. That keeps levels independent but means a hot entry can fall behind newer ones right after it moves. For threads, one lock around the whole cache is the simple answer, because a promotion holds two levels at once. Per-level locks would need a fixed top to bottom order.

The code

Runnable JavaScript, with the checks it passes.

phonepe-multilevel-cache.js

class LruPolicy {
  constructor() {
    this.order = new Map();
  }
  touch(key) {
    this.order.delete(key);
    this.order.set(key, true);
  }
  remove(key) {
    this.order.delete(key);
  }
  evict() {
    const key = this.order.keys().next().value;
    this.order.delete(key);
    return key;
  }
}

class LfuPolicy {
  constructor() {
    this.nodeOf = new Map();
    this.head = null;
  }
  link(count, after) {
    const node = { count, keys: new Set(), prev: after, next: after ? after.next : this.head };
    if (node.next) node.next.prev = node;
    if (after) after.next = node;
    else this.head = node;
    return node;
  }
  unlink(node) {
    if (node.prev) node.prev.next = node.next;
    else this.head = node.next;
    if (node.next) node.next.prev = node.prev;
  }
  touch(key) {
    const node = this.nodeOf.get(key) || null;
    const count = node ? node.count + 1 : 1;
    let target = node ? node.next : this.head;
    if (!target || target.count !== count) target = this.link(count, node);
    target.keys.add(key);
    this.nodeOf.set(key, target);
    if (node) {
      node.keys.delete(key);
      if (node.keys.size === 0) this.unlink(node);
    }
  }
  remove(key) {
    const node = this.nodeOf.get(key);
    if (!node) return;
    node.keys.delete(key);
    if (node.keys.size === 0) this.unlink(node);
    this.nodeOf.delete(key);
  }
  evict() {
    const key = this.head.keys.values().next().value;
    this.remove(key);
    return key;
  }
}

class CacheLevel {
  constructor(capacity, policy) {
    this.capacity = capacity;
    this.policy = policy;
    this.data = new Map();
  }
  put(key, value) {
    let evicted = null;
    if (!this.data.has(key) && this.data.size >= this.capacity) {
      const victim = this.policy.evict();
      evicted = { key: victim, value: this.data.get(victim) };
      this.data.delete(victim);
    }
    this.data.set(key, value);
    this.policy.touch(key);
    return evicted;
  }
  remove(key) {
    if (!this.data.delete(key)) return false;
    this.policy.remove(key);
    return true;
  }
}

class MultiLevelCache {
  constructor(capacities, policyFactory) {
    if (capacities.length === 0 || capacities.some((c) => !Number.isInteger(c) || c < 1)) {
      throw new RangeError("capacities must be positive integers");
    }
    this.capacities = capacities;
    this.policyFactory = policyFactory;
    this.levels = [];
  }
  levelAt(index) {
    while (this.levels.length <= index && this.levels.length < this.capacities.length) {
      const capacity = this.capacities[this.levels.length];
      this.levels.push(new CacheLevel(capacity, this.policyFactory()));
    }
    return this.levels[index];
  }
  insert(index, key, value) {
    let entry = { key, value };
    for (let i = index; entry; i++) {
      const level = this.levelAt(i);
      if (!level) return entry;
      entry = level.put(entry.key, entry.value);
    }
    return null;
  }
  levelOf(key) {
    return this.levels.findIndex((level) => level.data.has(key));
  }
  get(key) {
    const index = this.levelOf(key);
    if (index < 0) return undefined;
    const level = this.levels[index];
    const value = level.data.get(key);
    if (index === 0) {
      level.policy.touch(key);
      return value;
    }
    level.remove(key);
    this.insert(0, key, value);
    return value;
  }
  put(key, value) {
    this.delete(key);
    return this.insert(0, key, value);
  }
  delete(key) {
    let found = false;
    for (const level of this.levels) found = level.remove(key) || found;
    return found;
  }
  dump() {
    return this.levels.map((level) => [...level.data.keys()].sort());
  }
}

Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.

Try your own input

Write JavaScript that calls the code above and prints with console.log. It runs after the solution.

Extend it

The change requests an interviewer throws next.

How would you make the cache safe for many threads without one global lock, given that a promotion touches two levels at once?
How would you add a time to live per entry, and where does the expiry check belong so that an expired entry is never promoted?
Capacity is now measured in bytes and values differ in size: what changes in CacheLevel and in the policy interface when one insert may need to evict several entries?
How would you let the levels use different policies, for example LRU on top and LFU below, and what does the factory become?
Should a hit in a lower level move the entry straight to the top or only one level up, and how does that change which entries get pushed down?

Where candidates slip

The mistakes this problem punishes.

Implementing LFU with a plain count map and scanning for the smallest count on each eviction. That is O(n) per eviction, and the question asks for constant time operations.
Forgetting the tie-break. When counts are equal the victim must still be deterministic, usually the entry that has waited longest at that count.
Promoting without removing the entry from the lower level, which leaves two copies, or forgetting that the demotion triggered by a promotion lands in the slot that was just freed.
Removing and re-inserting on a hit in the top level, which silently resets its frequency to one.
Letting CacheLevel know about LRU or LFU, so adding a policy means editing existing classes.
Stopping a delete at the first level that holds the key, or silently losing the entry that falls out of the last level.

Have a go before you read.

Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.

Always show the answer straight away

Now make it stick

Sketch the class map on the whiteboard Run a mock interview

Where this was reported

Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.

Candidate write-upPhonePe Interview Experience for SDE, 2-5 years (GeeksforGeeks)

Read these chapters first

Caching fundamentals

RazorpayIn-memory database

Now make it stick

Where this was reported

Read these chapters first

More on caches and stores