ARC and 2Q Adaptive Caches — Interview Preparation¶

Questions are grouped Junior → Middle → Senior → Professional. Each row has a concise model answer. A full from-scratch coding challenge (implement 2Q or ARC) follows in Go, Java, and Python.

Table of Contents¶

1. Junior Questions
2. Middle Questions
3. Senior Questions
4. Professional Questions
5. Rapid-Fire One-Liners
6. Coding Challenge

Junior Questions¶

Middle Questions¶

Senior Questions¶

Professional Questions¶

System Design Discussion Prompts¶

These are open-ended prompts an interviewer expands into a conversation. Each row gives the angle a strong answer takes.

Common Misconceptions to Correct¶

Rapid-Fire One-Liners¶

Coding Challenge¶

Implement a simplified 2Q cache with get(key) and put(key, value). (A from-scratch ARC variant is sketched in the comments at the end of each solution for the stretch version.)

Rules: - A1 (first-time keys) is a FIFO; Am (proven keys) is an LRU. - A key already in A1 that is accessed again is promoted to the front of Am. - On overflow, evict the oldest of A1 (FIFO) or the LRU of Am. - Both operations must be O(1). Use a hash map + doubly linked lists (do not rely on language-ordered maps for the stretch goal).

Test scenario (A1 cap = 2, Am cap = 2):

put(1,"a"); put(2,"b"); get(1) -> "a" (1 promoted to Am)
put(3,"c"); put(4,"d")  -> A1 overflow evicts 2 (FIFO)
get(3) -> "c" (3 promoted to Am)
get(2) -> miss
get(1) -> "a"; get(3) -> "c" (both in Am)

Go¶

package main

import "fmt"

type node struct {
    key, val   int
    prev, next *node
}

// dlist is a doubly linked list with sentinel head/tail.
type dlist struct {
    head, tail *node
    size       int
}

func newList() *dlist {
    h, t := &node{}, &node{}
    h.next, t.prev = t, h
    return &dlist{head: h, tail: t}
}
func (l *dlist) pushFront(n *node) {
    n.prev, n.next = l.head, l.head.next
    l.head.next.prev, l.head.next = n, n
    l.size++
}
func (l *dlist) remove(n *node) {
    n.prev.next, n.next.prev = n.next, n.prev
    l.size--
}
func (l *dlist) back() *node { return l.tail.prev } // LRU / oldest

type TwoQ struct {
    a1Cap, amCap int
    a1, am       *dlist
    a1m, amm     map[int]*node
}

func NewTwoQ(a1Cap, amCap int) *TwoQ {
    return &TwoQ{a1Cap, amCap, newList(), newList(),
        map[int]*node{}, map[int]*node{}}
}

func (c *TwoQ) Get(key int) (int, bool) {
    if n, ok := c.amm[key]; ok { // hit in Am -> LRU touch
        c.am.remove(n)
        c.am.pushFront(n)
        return n.val, true
    }
    if n, ok := c.a1m[key]; ok { // hit in A1 -> PROMOTE to Am
        c.a1.remove(n)
        delete(c.a1m, key)
        c.am.pushFront(n)
        c.amm[key] = n
        c.evictAm()
        return n.val, true
    }
    return 0, false
}

func (c *TwoQ) Put(key, val int) {
    if n, ok := c.amm[key]; ok {
        n.val = val
        c.am.remove(n)
        c.am.pushFront(n)
        return
    }
    if n, ok := c.a1m[key]; ok {
        n.val = val
        c.a1.remove(n)
        delete(c.a1m, key)
        c.am.pushFront(n)
        c.amm[key] = n
        c.evictAm()
        return
    }
    n := &node{key: key, val: val}
    c.a1.pushFront(n)
    c.a1m[key] = n
    if c.a1.size > c.a1Cap { // FIFO evict oldest
        old := c.a1.back()
        c.a1.remove(old)
        delete(c.a1m, old.key)
    }
}

func (c *TwoQ) evictAm() {
    if c.am.size > c.amCap { // LRU evict
        lru := c.am.back()
        c.am.remove(lru)
        delete(c.amm, lru.key)
    }
}

func main() {
    c := NewTwoQ(2, 2)
    c.Put(1, 'a')
    c.Put(2, 'b')
    v, _ := c.Get(1) // promote 1
    fmt.Printf("get(1)=%c\n", v)
    c.Put(3, 'c')
    c.Put(4, 'd') // A1 overflow evicts 2
    c.Get(3)      // promote 3
    if _, ok := c.Get(2); !ok {
        fmt.Println("get(2)=miss")
    }
    v1, _ := c.Get(1)
    v3, _ := c.Get(3)
    fmt.Printf("get(1)=%c get(3)=%c\n", v1, v3)
}

// Stretch (ARC): add b1/b2 ghost lists (key-only) and an int p.
// On a miss whose key is in b1 -> p=min(p+max(1,|b2|/|b1|),cap); load into Am.
// In b2 -> p=max(p-max(1,|b1|/|b2|),0); load into Am. Evict from A1/T1 when its
// size exceeds p, else from Am/T2, demoting the victim's key into the matching ghost.

Java¶

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

public class TwoQCache {
    static class Node { int key, val; Node prev, next; Node(int k,int v){key=k;val=v;} Node(){} }

    static class DList {
        final Node head = new Node(), tail = new Node();
        int size = 0;
        DList(){ 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 back(){ return tail.prev; } // LRU / oldest
    }

    private final int a1Cap, amCap;
    private final DList a1 = new DList(), am = new DList();
    private final Map<Integer,Node> a1m = new HashMap<>(), amm = new HashMap<>();

    public TwoQCache(int a1Cap, int amCap){ this.a1Cap=a1Cap; this.amCap=amCap; }

    public Integer get(int key){
        Node n = amm.get(key);
        if (n != null){ am.remove(n); am.pushFront(n); return n.val; } // LRU touch
        n = a1m.get(key);
        if (n != null){                                                // PROMOTE
            a1.remove(n); a1m.remove(key);
            am.pushFront(n); amm.put(key, n);
            evictAm();
            return n.val;
        }
        return null; // miss
    }

    public void put(int key, int val){
        Node n = amm.get(key);
        if (n != null){ n.val=val; am.remove(n); am.pushFront(n); return; }
        n = a1m.get(key);
        if (n != null){
            n.val=val; a1.remove(n); a1m.remove(key);
            am.pushFront(n); amm.put(key,n); evictAm(); return;
        }
        n = new Node(key, val);
        a1.pushFront(n); a1m.put(key, n);
        if (a1.size > a1Cap){ Node old = a1.back(); a1.remove(old); a1m.remove(old.key); }
    }

    private void evictAm(){
        if (am.size > amCap){ Node lru = am.back(); am.remove(lru); amm.remove(lru.key); }
    }

    public static void main(String[] args){
        TwoQCache c = new TwoQCache(2,2);
        c.put(1,'a'); c.put(2,'b');
        System.out.println("get(1)="+(char)(int)c.get(1)); // promote 1
        c.put(3,'c'); c.put(4,'d');                        // A1 overflow evicts 2
        c.get(3);                                          // promote 3
        System.out.println("get(2)=" + (c.get(2)==null ? "miss" : c.get(2)));
        System.out.println("get(1)="+(char)(int)c.get(1)+" get(3)="+(char)(int)c.get(3));
    }
}

Python¶

class Node:
    __slots__ = ("key", "val", "prev", "next")
    def __init__(self, key=0, val=0):
        self.key, self.val, self.prev, self.next = key, val, None, None


class DList:
    """Doubly linked list with sentinel head/tail."""
    def __init__(self):
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, 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.prev = n.next, n.prev
        self.size -= 1

    def back(self):           # LRU / oldest
        return self.tail.prev


class TwoQCache:
    def __init__(self, a1_cap, am_cap):
        self.a1_cap, self.am_cap = a1_cap, am_cap
        self.a1, self.am = DList(), DList()
        self.a1m, self.amm = {}, {}

    def get(self, key):
        if key in self.amm:                       # hit in Am -> LRU touch
            n = self.amm[key]
            self.am.remove(n); self.am.push_front(n)
            return n.val
        if key in self.a1m:                       # hit in A1 -> PROMOTE
            n = self.a1m.pop(key)
            self.a1.remove(n)
            self.am.push_front(n); self.amm[key] = n
            self._evict_am()
            return n.val
        return None                               # miss

    def put(self, key, val):
        if key in self.amm:
            n = self.amm[key]; n.val = val
            self.am.remove(n); self.am.push_front(n); return
        if key in self.a1m:
            n = self.a1m.pop(key); n.val = val
            self.a1.remove(n)
            self.am.push_front(n); self.amm[key] = n
            self._evict_am(); return
        n = Node(key, val)
        self.a1.push_front(n); self.a1m[key] = n
        if self.a1.size > self.a1_cap:            # FIFO evict oldest
            old = self.a1.back()
            self.a1.remove(old); del self.a1m[old.key]

    def _evict_am(self):
        if self.am.size > self.am_cap:            # LRU evict
            lru = self.am.back()
            self.am.remove(lru); del self.amm[lru.key]


if __name__ == "__main__":
    c = TwoQCache(2, 2)
    c.put(1, "a"); c.put(2, "b")
    print("get(1)=", c.get(1))   # promote 1
    c.put(3, "c"); c.put(4, "d") # A1 overflow evicts 2
    c.get(3)                     # promote 3
    print("get(2)=", c.get(2) or "miss")
    print("get(1)=", c.get(1), "get(3)=", c.get(3))

# Stretch (ARC): add b1/b2 (key-only dicts) and int p. On a miss in b1:
#   p = min(p + max(1, len(b2)//max(1,len(b1))), cap); load into T2.
# In b2: p = max(p - max(1, len(b1)//max(1,len(b2))), 0); load into T2.
# REPLACE evicts from T1 when len(T1) > p (key -> b1), else from T2 (key -> b2).

Complexity of all three: get and put are O(1) (hash lookup + constant pointer surgery). Space is O(a1Cap + amCap) for 2Q, or O(2c) directory for the ARC stretch (data + ghost keys).

Whiteboard Checklist¶

When you implement 2Q or ARC live, walk the interviewer through these decisions explicitly — they are exactly what graders look for:

1. State the two structures. "Hash map for O(1) lookup + doubly linked lists for O(1) reorder/evict; the map stores key → node."
2. Use sentinel head/tail nodes. They kill the empty-list and last-node edge cases. Say so before coding.
3. A1 is FIFO, Am/T2 is LRU. Call this out — mixing them up is the most common bug.
4. Promotion is on the second access. Show the case split: in Am/T2 → touch; in A1/T1 → promote; new → insert into the recency area.
5. Delete on eviction from both the list map and the value store. Forgetting this leaks memory and returns stale nodes.
6. For ARC, ghosts hold keys only. Drop the value when demoting to B1/B2.
7. For ARC, adjust p only on ghost hits, clamp to [0,c], guard the divide with max(1,...).
8. Test the scan. Pre-prove a hot set, run a scan, assert the hot set survives — this is the property the whole topic exists for.

Self-Test Trace (do this before the interview)¶

Run this stream through your 2Q (A1 cap 2, Am cap 2) on paper and confirm the final state:

put(10); put(20); get(10); put(30); put(40); get(30); get(20); get(10); get(30)

Expected reasoning: - put(10),put(20) → A1 = [20,10] - get(10) → promote 10 → Am = [10], A1 = [20] - put(30) → A1 = [30,20] - put(40) → A1 overflows → evict 20 (FIFO) → A1 = [40,30] - get(30) → promote 30 → Am = [30,10], A1 = [40] - get(20) → miss (evicted) - get(10) → hit in Am → Am = [10,30] - get(30) → hit in Am → Am = [30,10]

If your implementation produces a different final Am/A1, the bug is almost always (a) A1 managed as LRU instead of FIFO, or (b) promotion on the wrong access. Fix those first.

What Interviewers Probe After You Finish¶

Pitfall Quick-Reference¶

A condensed list of the bugs that fail candidates on this problem:

Final Talking Points¶

If you have time at the end, leave the interviewer with the three sentences that prove depth:

1. "2Q and ARC fix LRU's scan pollution by making a new key earn promotion on its second access."
2. "ARC goes further with ghost lists that let it measure its own eviction mistakes and retune the recency/frequency split p with no configuration."
3. "It can't beat LRU in the adversarial competitive ratio — nothing can — but on real, scan-prone workloads it gets much closer to optimal, which is why ZFS and storage engines use it."