Treiber Lock-Free Stack — Interview Preparation¶

Coverage: 48 tiered questions (Junior → Middle → Senior → Professional) with answer focus, followed by a full coding challenge — implement a Treiber stack push/pop in Go, Java, and Python.

This guide assumes you have read junior.md, middle.md, senior.md, and professional.md. Each question lists the answer focus an interviewer is listening for. Treat them as oral-exam prompts: say the keyword, then justify it.

Table of Contents¶

1. Junior Questions (1–12)
2. Middle Questions (13–24)
3. Senior Questions (25–36)
4. Professional Questions (37–48)
5. Coding Challenge — Treiber Stack in 3 Languages
6. Follow-up Extensions

1. Junior Questions (1–12)¶

2. Middle Questions (13–24)¶

3. Senior Questions (25–36)¶

4. Professional Questions (37–48)¶

5. Coding Challenge — Treiber Stack in 3 Languages¶

Task. Implement a thread-safe lock-free Treiber stack supporting push(v) and pop() (returning a value + an "ok" flag for empty). Demonstrate correctness under concurrent access: spawn T threads each doing N pushes then N pops, and assert the multiset of all popped values equals the multiset of all pushed values (no lost, no duplicated, no resurrected values).

Constraints. Lock-free push/pop (CAS loop, no mutex on the hot path). O(1) amortized per op. Handle empty pop. Rely on the runtime GC for reclamation.

Go¶

package main

import (
    "fmt"
    "sync"
    "sync/atomic"
)

type node[T any] struct {
    value T
    next  *node[T]
}

type TreiberStack[T any] struct {
    head atomic.Pointer[node[T]]
}

func (s *TreiberStack[T]) Push(v T) {
    n := &node[T]{value: v}
    for {
        old := s.head.Load()
        n.next = old
        if s.head.CompareAndSwap(old, n) {
            return
        }
    }
}

func (s *TreiberStack[T]) Pop() (v T, ok bool) {
    for {
        old := s.head.Load()
        if old == nil {
            return v, false
        }
        if s.head.CompareAndSwap(old, old.next) {
            return old.value, true
        }
    }
}

func main() {
    const T, N = 8, 10000
    s := &TreiberStack[int]{}

    // Phase 1: concurrent pushes. Each thread pushes its tagged ids.
    var wg sync.WaitGroup
    for t := 0; t < T; t++ {
        wg.Add(1)
        go func(t int) {
            defer wg.Done()
            for i := 0; i < N; i++ {
                s.Push(t*N + i)
            }
        }(t)
    }
    wg.Wait()

    // Phase 2: concurrent pops; collect counts.
    var mu sync.Mutex
    seen := make(map[int]int)
    for t := 0; t < T; t++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            for {
                v, ok := s.Pop()
                if !ok {
                    return
                }
                mu.Lock()
                seen[v]++
                mu.Unlock()
            }
        }()
    }
    wg.Wait()

    // Verify: every pushed value popped exactly once.
    ok := len(seen) == T*N
    for _, c := range seen {
        if c != 1 {
            ok = false
        }
    }
    fmt.Printf("popped %d distinct values, integrity=%v\n", len(seen), ok)
}

Java¶

import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

public class TreiberStack<T> {

    private static final class Node<T> {
        final T value;
        Node<T> next;
        Node(T v) { value = v; }
    }

    private final AtomicReference<Node<T>> head = new AtomicReference<>();

    public void push(T v) {
        Node<T> n = new Node<>(v), old;
        do {
            old = head.get();
            n.next = old;
        } while (!head.compareAndSet(old, n));
    }

    /** Returns null when empty. */
    public T pop() {
        Node<T> old, next;
        do {
            old = head.get();
            if (old == null) return null;
            next = old.next;
        } while (!head.compareAndSet(old, next));
        return old.value;
    }

    public static void main(String[] args) throws InterruptedException {
        final int T = 8, N = 10_000;
        TreiberStack<Integer> s = new TreiberStack<>();

        Thread[] pushers = new Thread[T];
        for (int t = 0; t < T; t++) {
            final int tt = t;
            pushers[t] = new Thread(() -> {
                for (int i = 0; i < N; i++) s.push(tt * N + i);
            });
            pushers[t].start();
        }
        for (Thread p : pushers) p.join();

        ConcurrentHashMap<Integer, Integer> seen = new ConcurrentHashMap<>();
        Thread[] poppers = new Thread[T];
        for (int t = 0; t < T; t++) {
            poppers[t] = new Thread(() -> {
                Integer v;
                while ((v = s.pop()) != null) seen.merge(v, 1, Integer::sum);
            });
            poppers[t].start();
        }
        for (Thread p : poppers) p.join();

        AtomicInteger bad = new AtomicInteger();
        seen.forEach((k, c) -> { if (c != 1) bad.incrementAndGet(); });
        boolean ok = seen.size() == T * N && bad.get() == 0;
        System.out.printf("popped %d distinct values, integrity=%b%n", seen.size(), ok);
    }
}

Python¶

# CPython's GIL serializes bytecode and exposes no hardware CAS, so a true
# lock-free stack gives no parallelism here. We provide a conceptual CAS
# (simulated with a lock) to mirror the algorithm, plus the production note.
import threading
from collections import Counter


class _Node:
    __slots__ = ("value", "next")

    def __init__(self, value):
        self.value = value
        self.next = None


class TreiberStack:
    def __init__(self):
        self._head = None
        self._cas_lock = threading.Lock()

    def _cas_head(self, expected, new):
        with self._cas_lock:          # simulate one atomic CAS instruction
            if self._head is expected:
                self._head = new
                return True
            return False

    def push(self, value):
        n = _Node(value)
        while True:
            old = self._head
            n.next = old
            if self._cas_head(old, n):
                return

    def pop(self):
        while True:
            old = self._head
            if old is None:
                return None, False
            if self._cas_head(old, old.next):
                return old.value, True


if __name__ == "__main__":
    T, N = 8, 2000
    s = TreiberStack()

    def pusher(t):
        for i in range(N):
            s.push(t * N + i)

    threads = [threading.Thread(target=pusher, args=(t,)) for t in range(T)]
    for th in threads:
        th.start()
    for th in threads:
        th.join()

    seen = Counter()
    seen_lock = threading.Lock()

    def popper():
        while True:
            v, ok = s.pop()
            if not ok:
                return
            with seen_lock:
                seen[v] += 1

    poppers = [threading.Thread(target=popper) for _ in range(T)]
    for th in poppers:
        th.start()
    for th in poppers:
        th.join()

    integrity = len(seen) == T * N and all(c == 1 for c in seen.values())
    print(f"popped {len(seen)} distinct values, integrity={integrity}")
    # Production Python: just use queue.LifoQueue() for a thread-safe stack.

Expected output (all three): popped 80000 distinct values, integrity=true (Python uses N=2000 → 16000), confirming no value was lost, duplicated, or resurrected under concurrency.

6. Follow-up Extensions¶

Interviewers commonly extend the challenge. Be ready to:

1. Add ABA protection — convert head to a (ptr, tag) pair (AtomicStampedReference in Java) and bump the tag on every success; explain why GC code didn't need it.
2. Add exponential backoff — sleep a capped, randomized, doubling interval after a failed CAS; show it lowers retry rate under contention.
3. Add elimination — sketch the elimination array and the push/pop rendezvous; argue it stays linearizable.
4. Reclaim without GC — describe hazard-pointer-protected pop (publish, re-validate, retire) and when you'd choose epochs instead.
5. Prove correctness — give the linearization points and the lock-freedom contradiction argument from professional.md.
6. Bound the stack / add size — discuss why a naive shared size counter is a second hotspot and how to approximate size without one.

7. Rapid-Fire Concept Drills¶

Practice giving these as one-breath answers.

• "CAS in one sentence?" Atomically set a location to a new value only if it still holds the expected one; report success.
• "Why is head atomic and nothing else?" It is the only field two threads mutate concurrently; nodes are immutable after publication.
• "What does a failed CAS tell you?" Someone else's CAS succeeded in your read–CAS window; re-read and recompute.
• "Lock-free vs wait-free in one line?" Lock-free: some op always completes. Wait-free: every op completes in bounded steps.
• "ABA in one line?" Same pointer bits, different node — a stale CAS succeeds wrongly after a free+reuse.
• "Tag fix in one line?" CAS (ptr, version) and bump the version every success, so recycled pointers carry fresh versions.
• "Why doesn't a GC see ABA?" It won't recycle a node any thread still references.
• "Elimination in one line?" A concurrent push and pop hand off a value directly and skip head entirely.
• "Why LIFO for free lists?" The most-recently-freed object is the hottest in cache.
• "Hazard pointers vs epochs?" Hazard: bounded memory, robust, costlier reads. Epoch: cheap reads, but a stalled thread blocks reclamation.

8. Common Wrong Answers (and the Correction)¶

Interviewers probe for these misconceptions. Know the correction cold.

9. Whiteboard Warm-Ups¶

Short derivations an interviewer may ask you to do live.

Warm-up A — Show two concurrent pushes never lose a value. Each push completes via a successful CAS(head, old, n), which fires only when head == old. Two pushes cannot both succeed against the same old: the first to commit changes head, so the second's CAS sees head != old and fails, forcing a re-read of the new head and a re-link. Thus both nodes end up in the chain, ordered by commit time. No value is lost.

Warm-up B — Give the smallest ABA trace. head → A → B. T1: read old=A, next=B, stall. T2: pop A (free A), pop B (free B), push X reusing A's address → head → A*. T1: CAS(head, A, B) matches bits → succeeds → head → B (freed). Three T2 operations are the minimum to recycle A's address and present the A→B→A pattern.

Warm-up C — Why the empty-pop LP is the nil-read, not the invocation. Only the witnessed head == nil instant is guaranteed to coincide with an actually-empty abstract stack; at invocation the stack may still be non-empty. Linearizing at the nil-read makes the "returns ⊥ ⇒ stack was empty then" argument sound.

Warm-up D — Argue lock-freedom in 3 sentences. Suppose no operation ever completes after some point. Then every CAS fails forever; but a CAS fails only because another CAS succeeded (changed head), and a successful CAS completes its operation. Contradiction — so some operation always completes; the system makes progress.

10. System-Design Style Prompts¶

These are open-ended; the interviewer wants structured reasoning, not a single fact.

Prompt 1 — "Design a high-throughput connection pool." Lead with: per-thread cache in front of a shared lock-free free list (Treiber stack). Justify LIFO (hottest connection is warmest). Discuss bounding (cap + spill to a creator), validation on acquire (drop stale connections), and reclamation (GC handles it on the JVM; tags if you recycle node wrappers). Mention sharding per NUMA node if multi-socket. Close on observability: pool hit rate, acquire latency p99, and shared-stack CAS retry rate.

Prompt 2 — "Your lock-free stack's memory keeps growing in production. Diagnose." First rule out a logical leak (more pushes than pops). Then suspect reclamation backlog: a thread parked inside an epoch critical section or holding a hazard pointer prevents frees, so limbo/retired lists balloon. Fix: bound critical-section duration, add a watchdog, and prefer hazard pointers for bounded held-back memory. Note this is an availability bug, not a perf knob.

Prompt 3 — "When would you NOT use a Treiber stack?" When you need FIFO (use an MS-queue), when contention is low and simplicity wins (use a mutex + slice), when you need exact size/iteration/multi-op atomicity (lock-based is easier), or when contention is extreme and strict LIFO is unnecessary (shard it, or it isn't even a stack you want).

Prompt 4 — "Make it scale to 64 cores." Front it with per-thread caches (removes most shared traffic), then if strict LIFO isn't needed, shard the shared tier; if it is needed, deploy elimination-backoff so concurrent push/pop pairs cancel off the hot path. Add capped exponential backoff regardless. Pad head/shard-heads to a cache line to avoid false sharing. Validate with a scaling benchmark, expecting the plain version to flatten/regress and the tuned version to climb.

Prompt 5 — "Port the JVM stack to C++. What breaks?" ABA reappears (no GC pinning nodes) and use-after-free becomes possible. Add a versioned head (DWCAS or AtomicStampedReference-equivalent) for ABA and a reclamation scheme (hazard pointers for bounded memory and robustness, or epochs for cheap read-heavy paths) for safe free. Get the memory ordering right: release on the publishing CAS, acquire on the load, a store-load fence in hazard-pointer publication.

11. Extended Coding Challenge — Bounded Treiber Stack¶

Task. Extend the Treiber stack with a capacity. push returns false when full; pop returns the empty signal when empty. Avoid a single exact shared counter as the only mechanism — discuss the trade-off — but a correct (if contended) atomic counter is acceptable for the interview.

Go¶

package main

import (
    "fmt"
    "sync/atomic"
)

type bnode struct {
    value int
    next  *bnode
}

type BoundedStack struct {
    head atomic.Pointer[bnode]
    size atomic.Int64 // approximate under heavy contention; exact here
    cap  int64
}

func (s *BoundedStack) Push(v int) bool {
    if s.size.Load() >= s.cap { // fast reject (racy but cheap)
        return false
    }
    n := &bnode{value: v}
    for {
        old := s.head.Load()
        n.next = old
        if s.head.CompareAndSwap(old, n) {
            s.size.Add(1)
            return true
        }
    }
}

func (s *BoundedStack) Pop() (int, bool) {
    for {
        old := s.head.Load()
        if old == nil {
            return 0, false
        }
        if s.head.CompareAndSwap(old, old.next) {
            s.size.Add(-1)
            return old.value, true
        }
    }
}

func main() {
    s := &BoundedStack{cap: 2}
    fmt.Println(s.Push(1), s.Push(2), s.Push(3)) // true true false
    v, _ := s.Pop()
    fmt.Println("popped", v, "now push:", s.Push(9)) // popped 2 ... true
}

Java¶

import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.AtomicLong;

public class BoundedStack<T> {
    private static final class Node<T> { final T v; Node<T> next; Node(T v){this.v=v;} }
    private final AtomicReference<Node<T>> head = new AtomicReference<>();
    private final AtomicLong size = new AtomicLong();
    private final long cap;
    public BoundedStack(long cap){ this.cap = cap; }

    public boolean push(T v) {
        if (size.get() >= cap) return false;       // cheap, racy fast-reject
        Node<T> n = new Node<>(v), old;
        do { old = head.get(); n.next = old; } while (!head.compareAndSet(old, n));
        size.incrementAndGet();
        return true;
    }
    public T pop() {
        Node<T> old, nx;
        do { old = head.get(); if (old == null) return null; nx = old.next; }
        while (!head.compareAndSet(old, nx));
        size.decrementAndGet();
        return old.v;
    }
    public static void main(String[] a) {
        BoundedStack<Integer> s = new BoundedStack<>(2);
        System.out.println(s.push(1) + " " + s.push(2) + " " + s.push(3)); // true true false
        System.out.println("popped " + s.pop() + ", push9=" + s.push(9));
    }
}

Python¶

import threading


class _Node:
    __slots__ = ("v", "next")
    def __init__(self, v): self.v, self.next = v, None


class BoundedStack:
    """Conceptual: GIL + simulated CAS. Production: queue.LifoQueue(maxsize=cap)."""
    def __init__(self, cap):
        self._head = None
        self._size = 0
        self._cap = cap
        self._lock = threading.Lock()

    def push(self, v):
        with self._lock:
            if self._size >= self._cap:
                return False
            n = _Node(v); n.next = self._head
            self._head = n; self._size += 1
            return True

    def pop(self):
        with self._lock:
            if self._head is None:
                return None, False
            old = self._head; self._head = old.next; self._size -= 1
            return old.v, True


if __name__ == "__main__":
    s = BoundedStack(2)
    print(s.push(1), s.push(2), s.push(3))  # True True False
    v, _ = s.pop()
    print("popped", v, "push9=", s.push(9))

Discussion point for the interviewer: the shared size counter is a second contended atomic that can bottleneck before head does. For order-agnostic pools, prefer a sharded or per-thread approximate count and treat the bound as soft; exact bounds require paying the counter contention. The racy fast-reject (size >= cap before the CAS loop) is a deliberate optimization — it may transiently over/under-admit by a few elements, acceptable for a soft bound.