MFU Cache — Interview Questions¶

Tiered questions (Junior → Middle → Senior → Professional) followed by the canonical coding challenge: an O(1) MFU Cache in Go, Java, and Python. MFU evicts the most frequently used key (highest access count), breaking ties by least recently used within the top-frequency bucket. It is the mirror image of LFU — same three structures, but a maxFreq pointer instead of minFreq. Cross-references: LFU cache · LRU cache.

Table of Contents¶

1. Junior Questions
2. Middle Questions
3. Senior Questions
4. Professional Questions
5. Trace-Reading Drills
6. Rapid-Fire Round (Mixed)
7. Whiteboard Diagnostic: Spot the Bug
8. Coding Challenge: O(1) MFU Cache
9. Go
10. Java
11. Python
12. Model Answers to the Hardest Questions
13. Complexity & Policy Reference
14. Quick-Reference Cheat Sheet

Junior Questions¶

Middle Questions¶

Senior Questions¶

Professional Questions¶

Trace-Reading Drills¶

Interviewers love asking you to predict the eviction victim. Practice these (capacity in parentheses). Remember: MFU evicts the HIGHEST-frequency key; ties break by LRU within the top bucket.

Drill A (capacity 2): put(1,1) put(2,2) get(1) put(3,3) — who is evicted?

Key 1. After get(1), freqs are {1:2, 2:1}. put(3) overflows; maxFreq=2 holds only key 1. (The opposite of LFU, which would evict key 2.)

Drill B (capacity 2): put(1,1) put(2,2) get(2) get(1) get(2) put(3,3) — who is evicted?

Key 2. Freqs: 1:2, 2:3. maxFreq=3 holds only key 2. (Frequency, not recency, decides — key 2 was touched most recently and most often, and MFU drops it.)

Drill C (capacity 3): put(1,1) put(2,2) put(3,3) get(1) get(2) put(4,4) — who is evicted?

Either 1 or 2. Freqs: 1:2, 2:2, 3:1. maxFreq=2 bucket holds keys 1 and 2 (ordered by recency [2(newest), 1(oldest)]); the back (oldest) is key 1. Recency breaks the tie.

Drill D — the gap (capacity 3): put(1,1) put(2,2) put(3,3) get(1) get(1) get(2) put(4,4) — who is evicted, and what is maxFreq afterward?

Key 1 (freqs 1:3, 2:2, 3:1; maxFreq=3 holds only key 1). After evicting key 1, bucket 3 is empty, so the cache must scan down from 3 → 2 and set maxFreq=2. If you naively did maxFreq-- you'd land on empty bucket... here 2 happens to be occupied, but construct get(1) get(1) get(1) and the drop can be larger.

The pattern: frequency first (highest wins eviction), recency only on ties. The make-or-break detail is the post-eviction downward maxFreq scan — the one thing LFU never needs.

Rapid-Fire Round (Mixed)¶

Whiteboard Diagnostic: Spot the Bug¶

Interviewers often hand you broken MFU code. Train on these:

Coding Challenge: O(1) MFU Cache¶

Problem. Design and implement an MFU cache supporting: - MFUCache(int capacity) — initialize with a non-negative capacity. - get(key) — return the value if present (and increment its use count), else -1. - put(key, value) — insert/update; on overflow, evict the most frequently used key, breaking ties by least recently used.

Both get and put run in O(1) amortized time.

Design. keyMap: key → node, freqMap: freq → doubly linked list (recency-ordered), and a maxFreq integer. Promotion (on every use) moves a node up one frequency bucket and raises maxFreq if needed; eviction removes the back of the maxFreq bucket, then scans maxFreq downward if that bucket emptied.

Test cases¶

MFUCache c = new MFUCache(2)
c.put(1,1)            // cache {1:1}            freqs {1:1}
c.put(2,2)            // cache {1:1, 2:2}       freqs {1:1, 2:1}
c.get(1)   -> 1       // freq: 1->2 ; maxFreq=2 ; cache {1, 2}
c.put(3,3)            // evict key 1 (freq 2, the MAX) ; cache {2, 3}
c.get(1)   -> -1      // not found
c.get(2)   -> 2       // freq: 2->2 ; maxFreq=2
c.put(4,4)            // tie freq=2 between... only key 2 is at maxFreq=2 -> evict 2 ; cache {3, 4}
c.get(2)   -> -1
c.get(3)   -> 3
c.get(4)   -> 4

Go¶

package main

import "fmt"

type node struct {
    key, value, freq int
    prev, next       *node
}

type dll struct {
    head, tail *node
    size       int
}

func newDLL() *dll {
    h, t := &node{}, &node{}
    h.next, t.prev = t, h
    return &dll{head: h, tail: t}
}
func (l *dll) pushFront(n *node) {
    n.prev, n.next = l.head, l.head.next
    l.head.next.prev = n
    l.head.next = n
    l.size++
}
func (l *dll) remove(n *node) {
    n.prev.next = n.next
    n.next.prev = n.prev
    l.size--
}
func (l *dll) popBack() *node { n := l.tail.prev; l.remove(n); return n }

type MFUCache struct {
    capacity, maxFreq int
    keyMap            map[int]*node
    freqMap           map[int]*dll
}

func Constructor(capacity int) MFUCache {
    return MFUCache{
        capacity: capacity,
        keyMap:   make(map[int]*node),
        freqMap:  make(map[int]*dll),
    }
}

func (c *MFUCache) promote(n *node) {
    f := n.freq
    c.freqMap[f].remove(n)
    if c.freqMap[f].size == 0 {
        delete(c.freqMap, f)
    }
    n.freq++
    if c.freqMap[n.freq] == nil {
        c.freqMap[n.freq] = newDLL()
    }
    c.freqMap[n.freq].pushFront(n)
    if n.freq > c.maxFreq { // promotion only ever RAISES the ceiling — O(1)
        c.maxFreq = n.freq
    }
}

func (c *MFUCache) Get(key int) int {
    n, ok := c.keyMap[key]
    if !ok {
        return -1
    }
    c.promote(n)
    return n.value
}

func (c *MFUCache) Put(key, value int) {
    if c.capacity == 0 {
        return
    }
    if n, ok := c.keyMap[key]; ok {
        n.value = value
        c.promote(n)
        return
    }
    if len(c.keyMap) >= c.capacity {
        // Evict the most frequently used: back of the maxFreq bucket.
        victim := c.freqMap[c.maxFreq].popBack()
        delete(c.keyMap, victim.key)
        if c.freqMap[c.maxFreq].size == 0 {
            delete(c.freqMap, c.maxFreq)
            // THE GOTCHA: maxFreq can drop by more than 1 — scan downward.
            for c.maxFreq > 0 && c.freqMap[c.maxFreq] == nil {
                c.maxFreq--
            }
        }
    }
    n := &node{key: key, value: value, freq: 1}
    c.keyMap[key] = n
    if c.freqMap[1] == nil {
        c.freqMap[1] = newDLL()
    }
    c.freqMap[1].pushFront(n)
    if c.maxFreq < 1 {
        c.maxFreq = 1
    }
}

func main() {
    c := Constructor(2)
    c.Put(1, 1)
    c.Put(2, 2)
    fmt.Println(c.Get(1)) // 1   (key 1 freq -> 2, maxFreq = 2)
    c.Put(3, 3)           // evict 1 (the MAX freq)
    fmt.Println(c.Get(1)) // -1
    fmt.Println(c.Get(2)) // 2
    c.Put(4, 4)           // evict 2 (now the MAX freq)
    fmt.Println(c.Get(2)) // -1
    fmt.Println(c.Get(3)) // 3
    fmt.Println(c.Get(4)) // 4
}

Java¶

import java.util.HashMap;
import java.util.Map;

public class Solution {

    static class Node {
        int key, value, freq = 1;
        Node prev, next;
        Node() {}
        Node(int k, int v) { key = k; value = v; }
    }

    static class DLL {
        final Node head = new Node(), tail = new Node();
        int size = 0;
        DLL() { head.next = tail; tail.prev = head; }
        void pushFront(Node n) {
            n.prev = head; n.next = head.next;
            head.next.prev = n; head.next = n; size++;
        }
        void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; size--; }
        Node popBack() { Node n = tail.prev; remove(n); return n; }
    }

    static class MFUCache {
        final int capacity;
        int maxFreq = 0;
        final Map<Integer, Node> keyMap = new HashMap<>();
        final Map<Integer, DLL> freqMap = new HashMap<>();

        MFUCache(int capacity) { this.capacity = capacity; }

        void promote(Node n) {
            int f = n.freq;
            DLL list = freqMap.get(f);
            list.remove(n);
            if (list.size == 0) freqMap.remove(f);
            n.freq++;
            freqMap.computeIfAbsent(n.freq, k -> new DLL()).pushFront(n);
            if (n.freq > maxFreq) maxFreq = n.freq; // only ever raises — O(1)
        }

        int get(int key) {
            Node n = keyMap.get(key);
            if (n == null) return -1;
            promote(n);
            return n.value;
        }

        void put(int key, int value) {
            if (capacity == 0) return;
            Node n = keyMap.get(key);
            if (n != null) { n.value = value; promote(n); return; }
            if (keyMap.size() >= capacity) {
                Node victim = freqMap.get(maxFreq).popBack(); // evict the MAX
                keyMap.remove(victim.key);
                if (freqMap.get(maxFreq).size == 0) {
                    freqMap.remove(maxFreq);
                    // THE GOTCHA: maxFreq may drop by more than 1 — scan down.
                    while (maxFreq > 0 && !freqMap.containsKey(maxFreq)) maxFreq--;
                }
            }
            Node fresh = new Node(key, value);
            keyMap.put(key, fresh);
            freqMap.computeIfAbsent(1, k -> new DLL()).pushFront(fresh);
            if (maxFreq < 1) maxFreq = 1;
        }
    }

    public static void main(String[] args) {
        MFUCache c = new MFUCache(2);
        c.put(1, 1);
        c.put(2, 2);
        System.out.println(c.get(1)); // 1   (key 1 freq -> 2)
        c.put(3, 3);                   // evict 1 (the MAX)
        System.out.println(c.get(1)); // -1
        System.out.println(c.get(2)); // 2
        c.put(4, 4);                   // evict 2 (now the MAX)
        System.out.println(c.get(2)); // -1
        System.out.println(c.get(3)); // 3
        System.out.println(c.get(4)); // 4
    }
}

Python¶

class Node:
    __slots__ = ("key", "value", "freq", "prev", "next")

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.freq = 1
        self.prev = None
        self.next = None


class DLL:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def push_front(self, n):
        n.prev, n.next = self.head, self.head.next
        self.head.next.prev = n
        self.head.next = n
        self.size += 1

    def remove(self, n):
        n.prev.next = n.next
        n.next.prev = n.prev
        self.size -= 1

    def pop_back(self):
        n = self.tail.prev
        self.remove(n)
        return n


class MFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.max_freq = 0
        self.key_map: dict[int, Node] = {}
        self.freq_map: dict[int, DLL] = {}

    def _promote(self, n: Node) -> None:
        f = n.freq
        self.freq_map[f].remove(n)
        if self.freq_map[f].size == 0:
            del self.freq_map[f]
        n.freq += 1
        self.freq_map.setdefault(n.freq, DLL()).push_front(n)
        if n.freq > self.max_freq:  # promotion only raises the ceiling — O(1)
            self.max_freq = n.freq

    def get(self, key: int) -> int:
        n = self.key_map.get(key)
        if n is None:
            return -1
        self._promote(n)
        return n.value

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        n = self.key_map.get(key)
        if n is not None:
            n.value = value
            self._promote(n)
            return
        if len(self.key_map) >= self.capacity:
            # Evict the MOST frequently used: back of the max_freq bucket.
            victim = self.freq_map[self.max_freq].pop_back()
            del self.key_map[victim.key]
            if self.freq_map[self.max_freq].size == 0:
                del self.freq_map[self.max_freq]
                # THE GOTCHA: max_freq may drop by more than 1 — scan downward.
                while self.max_freq > 0 and self.max_freq not in self.freq_map:
                    self.max_freq -= 1
        fresh = Node(key, value)
        self.key_map[key] = fresh
        self.freq_map.setdefault(1, DLL()).push_front(fresh)
        if self.max_freq < 1:
            self.max_freq = 1


if __name__ == "__main__":
    c = MFUCache(2)
    c.put(1, 1)
    c.put(2, 2)
    print(c.get(1))  # 1   (key 1 freq -> 2)
    c.put(3, 3)      # evict 1 (the MAX)
    print(c.get(1))  # -1
    print(c.get(2))  # 2
    c.put(4, 4)      # evict 2 (now the MAX)
    print(c.get(2))  # -1
    print(c.get(3))  # 3
    print(c.get(4))  # 4

The naive O(n) version and why it's slow¶

class NaiveMFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.store = {}   # key -> (value, freq)

    def get(self, key):
        if key not in self.store:
            return -1
        v, f = self.store[key]
        self.store[key] = (v, f + 1)
        return v

    def put(self, key, value):
        if self.capacity == 0:
            return
        if key in self.store:
            _, f = self.store[key]
            self.store[key] = (value, f + 1)
            return
        if len(self.store) >= self.capacity:
            # O(n): scan every entry to find the maximum frequency.
            victim = max(self.store, key=lambda k: self.store[k][1])
            del self.store[victim]
        self.store[key] = (value, 1)

This is correct but put is O(n) on eviction because max(...) scans all entries. It also loses the recency tie-break (it picks an arbitrary max on ties). The bucket design exists precisely to make "find the max-frequency, least-recently-used key" O(1) instead of O(n).

Follow-up questions an interviewer may ask¶

Model Answers to the Hardest Questions¶

These four questions separate strong candidates. Here is how to answer them in full.

"Why is MFU's maxFreq harder to maintain than LFU's minFreq?"¶

"They look symmetric but they are not. In LFU, the minimum is pushed by two forces that both move it in unit steps: an insert creates a freq-1 key, so minFreq snaps to 1; and a promotion that empties the min bucket lands the node in minFreq + 1, so the minimum rises by exactly one. There is always a key sitting at the new minimum — it is never searched. In MFU, promotion likewise raises the ceiling by exactly one, so updating maxFreq upward is trivial. The asymmetry is on eviction: MFU evicts from the top bucket, and when that bucket empties, the next occupied bucket can be an arbitrary number of levels below, because lower buckets emptied independently as their nodes were promoted past them. There is no algebraic relation tying the next-lower occupied frequency to the old maximum, so you must consult actual occupancy — either by scanning down (amortized O(1)) or via an auxiliary ordered bucket index (strictly O(1)). Decrementing maxFreq by one is the classic bug; it lands on an empty bucket."

"Prove MFU is still O(1) despite the downward scan."¶

"Use a potential argument with Φ equal to the current maxFreq. Every promotion does O(1) actual work and raises Φ by at most one, so its amortized cost is O(1). Every eviction whose downward scan walks d empty buckets does O(d) actual work but lowers Φ by d, so its amortized cost is O(d) − d = O(1). Summed over any run, the total downward distance scanned can never exceed the total upward distance climbed by promotions, each of which was paid for. Therefore all operations are O(1) amortized. If you need a strict per-operation bound, thread the non-empty buckets in a frequency-ordered linked list so the next-lower bucket is one pointer hop — that removes the scan entirely."

"When would you actually choose MFU over LRU or LFU?"¶

"Almost never for a general cache, and you should say so plainly — it is the right answer. MFU evicts the most frequently used keys, which under any normal value model are exactly the ones worth keeping; under the Independent Reference Model it converges to caching the least popular keys, the pessimal contents. MFU only wins when the value model is inverted: when high past frequency signals that an item is done and least likely to be needed again. That happens in specific looping or lifecycle patterns — e.g., a cyclic scan slightly larger than the cache, where LRU evicts the next-needed item every time and a most-recently/most-frequently-used eviction keeps the items the loop will actually revisit. In an interview I'd reach for MRU (its recency cousin) for sequential-scan buffers, and treat pure frequency-MFU as a teaching mirror of LFU rather than a production default."

"Design eviction for a workload where 'heavily used' means 'finished.'"¶

"If frequency genuinely anti-correlates with future need, MFU's machinery is exactly right — but I'd harden it three ways. First, decay: halve all counts periodically so 'most frequently used' means recent heavy use, not lifetime totals, and the maxFreq ceiling can drift down naturally instead of ratcheting up forever. Second, replace the post-eviction downward scan with a frequency-ordered bucket linked list so the top-bucket predecessor is one hop — strict O(1) under pressure. Third, measure: replay the real trace against MFU, LRU, LFU, and ARC, because the entire bet rests on the inverted value model, and only the trace can confirm that high frequency really does mean 'safe to drop.' If the hit ratio doesn't beat LRU, the assumption was wrong and MFU is the wrong tool."

Complexity & Policy Reference (for the whiteboard)¶

Memorize this grid — interviewers expect instant recall.

Note: all "O(1)" entries are average/amortized (the hash map's worst case is O(n) on pathological collisions; the linked-list work is always O(1)). MFU's amortized qualifier additionally covers the downward maxFreq scan, removed only by the bucket-list index.

Two-sentence policy pitches (for "compare X vs Y")¶

• MFU vs LFU: Identical three-structure machinery, opposite victim — MFU evicts the max frequency (with a maxFreq pointer), LFU the min (with minFreq). The bookkeeping breaks symmetry: LFU's minFreq moves in strict unit steps, but MFU's maxFreq can drop by an arbitrary gap on eviction, needing a downward scan (amortized O(1)) or a bucket-list index (strict O(1)).
• MFU vs LRU: MFU evicts by how often a key was used (highest count); LRU by how recently (oldest). LRU keeps the recently-hot set; MFU throws it away, which is usually wrong but exactly right for cyclic/scan patterns where the just-finished hot item won't return soon.
• MFU vs MRU: Both target the "just-served, won't-need-again" item, but MRU uses recency (evict the newest) and MFU uses frequency (evict the highest count). MRU is the more common real-world choice (sequential-scan buffers); MFU is its frequency-flavored, niche cousin.

Quick-Reference Cheat Sheet¶