Concurrent Collections and Lock-Free Programming Interview Questions

Q1 Why isn't ConcurrentDictionary<TKey,TValue>.GetOrAdd atomic, and what bugs does that cause?#

Short answer: GetOrAdd is thread-safe but not atomic as a whole operation: the valueFactory delegate runs outside the dictionary's internal lock, so under concurrent calls for the same missing key, more than one thread can run the factory, and whichever thread's write reaches the lock first wins — the result is not necessarily the value the caller's own factory produced.

The documented race sequence is precise: thread A calls GetOrAdd, finds no entry, and starts running valueFactory. Thread B calls GetOrAdd for the same key concurrently, its valueFactory also runs, and B reaches the internal lock first, so B's key/value pair is what gets stored. Thread A's factory then finishes, A reaches the lock, sees the key already exists, and returns B's value instead of the one A just built. A's valueFactory ran, produced a value, and that value was silently discarded. This is invisible and harmless if valueFactory is a pure function computing a value from the key with no side effects. It becomes a real bug the moment the factory has a side effect — incrementing a shared counter, opening a connection, registering something with an external system, or capturing mutable state from its closure — because those side effects still happened for the thread whose result got thrown away, so "ran twice" is not just a performance concern — it can leak connections or double-register something.

What interviewers look for: Knowing the exact race sequence, not just "it can run twice," and immediately connecting it to why factory delegates must be side-effect-free — a candidate who has been bitten by this in production usually describes the leaked-resource variant unprompted.

Common mistakes:

• Assuming ConcurrentDictionary<TKey,TValue> guarantees the factory runs exactly once per missing key.
• Putting expensive I/O or a lock acquisition inside valueFactory, multiplying the cost of the race instead of just its side effects.

Q2 What is the atomicity contract of AddOrUpdate, and how do you write a safe update delegate?#

Short answer: AddOrUpdate guarantees the dictionary ends up in a consistent state with one value per key, but it does not guarantee either the add factory or the update factory runs exactly once — both can run multiple times under contention, so both must be pure, side-effect-free, and safe to discard.

counts.AddOrUpdate(
    key,
    addValueFactory: _ => 1,
    updateValueFactory: (_, existing) => existing + 1);

This looks like a correct, thread-safe increment, and it is, as long as updateValueFactory does nothing but compute a new value from existing — running it redundantly and discarding the result must have no observable effect beyond the final stored value. A common bug is writing the update delegate to mutate a field on existing in place and return it, assuming that is equivalent to returning a new value. If two threads race and both mutate the same shared instance before one result is discarded, the discarded thread's mutation already happened and is not rolled back — the "loser" of the race has still corrupted shared state even though its return value was thrown away. Safe update delegates return a new value, or a new immutable version of the existing one, rather than mutating in place. If the update genuinely needs a true single-execution guarantee, such as an audit log entry per call or a metric that must not double count, AddOrUpdate is the wrong tool regardless of how carefully the delegate is written; that logic belongs inside an explicit lock around the whole read-modify-write, not inside the dictionary's convenience method.

What interviewers look for: Recognizing that "runs more than once" applies to both delegates, and the in-place-mutation bug specifically, which is subtler and more common in real codebases than the plain double-execution case.

Follow-up questions:

• How would you implement a truly exactly-once increment on top of ConcurrentDictionary<TKey,TValue>?
• What changes if the value type is itself a mutable class shared elsewhere in the program?

Q3 How are ConcurrentQueue<T> and ConcurrentStack<T> implemented, and why are they faster than a lock-protected Queue<T> under contention?#

Short answer: Both are genuinely lock-free — they use Interlocked compare-and-swap operations to update internal state instead of taking a lock, so a thread never blocks another thread out of the structure the way a lock-protected Queue<T> does, which is why they scale better as contention rises.

A lock-protected Queue<T> serializes every enqueue and dequeue: while one thread holds the lock, every other thread attempting either operation blocks and waits its turn, even if their operations do not logically conflict. Under heavy contention this becomes a bottleneck, since threads spend real time waiting instead of making progress. ConcurrentQueue<T> is internally organized as a linked list of small array segments, and both enqueue and dequeue use compare-and-swap to atomically claim a slot or advance a pointer, retrying if another thread's concurrent change is detected first — no thread ever blocks another out of the structure; a thread that loses a compare-and-swap race simply retries immediately. ConcurrentStack<T> follows the same idea over a singly linked list, using compare-and-swap to update the head pointer for both push and pop. The trade-off is that lock-free retry loops can, in theory, spin under extremely high contention, whereas a fair lock guarantees each waiter eventually gets a turn — in practice, for the segment- and node-based designs these types use, throughput under realistic contention is consistently better than a lock-protected equivalent, which is the reason they exist.

What interviewers look for: Knowing specifically that these two types use compare-and-swap rather than locks — many candidates know they are "thread-safe" without knowing they are lock-free.

Common mistakes: Assuming every type in System.Collections.Concurrent is lock-free — ConcurrentDictionary<TKey,TValue> uses internal, fine-grained locking for writes, unlike the queue and stack.

Q4 How does ConcurrentBag<T> differ from ConcurrentQueue<T>, and when is it the wrong choice?#

Short answer: ConcurrentBag<T> keeps a separate list of items per thread and lets each thread operate on its own list with little synchronization, only falling back to more expensive cross-thread stealing when a thread's own list is empty; it gives no ordering guarantee at all, which makes it a poor fit whenever producers and consumers are different, dedicated threads.

ConcurrentBag<T> is optimized for the specific pattern where the same thread both adds and removes items most of the time, such as an object pool where a thread checks an item out, uses it, and returns it, largely without another thread's involvement. In that pattern, each thread's operations stay on its own local list, which needs little to no synchronization, so throughput is excellent. The moment producers and consumers are cleanly separated — one set of threads always adding, a different set always removing, as in a typical producer-consumer pipeline — ConcurrentBag<T> degrades toward its worst case: consumer threads find their own local lists empty and have to steal from producer threads' lists, which is slower than the same-thread fast path. ConcurrentQueue<T>, or a channel, fits that shape far better and gives ordering as a bonus — "no ordering guarantee" disqualifies ConcurrentBag<T> for anything resembling a work queue where fairness or FIFO order matters.

What interviewers look for: Understanding the thread-local-list design, not just "it's an unordered collection," and correctly steering a producer-consumer scenario away from it.

Follow-up questions:

• What is a realistic scenario where ConcurrentBag<T> is clearly the best choice?
• How would you empirically demonstrate that ConcurrentBag<T> performs worse than ConcurrentQueue<T> for a strict producer-consumer workload?

Q5 What is ImmutableInterlocked, and why would you use it instead of ConcurrentDictionary<TKey,TValue>?#

Short answer: ImmutableInterlocked provides atomic, compare-and-swap-based update helpers — Update, TryAdd, GetOrAdd, AddOrUpdate, and more — for a field holding an immutable collection such as ImmutableDictionary<TKey,TValue> or ImmutableArray<T>, letting you publish an entirely new version of the whole collection atomically instead of mutating a mutable collection in place.

The core use case is a field such as a private ImmutableDictionary<string, Config>, initialized to Empty, that many threads read constantly with no locking needed at all, since the referenced instance is immutable, and occasionally update. ImmutableInterlocked.Update reads the current reference, computes a new immutable collection from it through a transformation delegate, and uses Interlocked.CompareExchange to swap the field to the new reference, retrying the whole computation if another thread updated the field first. Compared to ConcurrentDictionary<TKey,TValue>, the key difference is snapshot semantics: a reader that captures a reference to an ImmutableDictionary<TKey,TValue> sees a perfectly consistent view forever, unaffected by later updates, because updates never mutate that instance — they replace the field with a different one. ConcurrentDictionary<TKey,TValue> gives per-operation thread safety, but a caller enumerating it while another thread writes can observe a mix of old and new state across the enumeration, which is fine for many uses but wrong when a true point-in-time snapshot is required. The trade-off is allocation cost: every update builds a new immutable collection, often sharing structure with the old one so it's cheaper than a full copy but not free. ImmutableInterlocked fits rarely updated, frequently read shared state like configuration or feature flags, not a hot key-value store with constant writes.

What interviewers look for: Understanding the snapshot-consistency argument specifically — that is the actual reason to reach for it over ConcurrentDictionary<TKey,TValue>, not simply "it's for immutable collections."

Q6 Write a lock-free stack push and pop using Interlocked.CompareExchange, and explain each part.#

Short answer: A compare-and-swap loop reads the current head, builds the new node pointing at it, then atomically swaps the head to the new node only if nothing else changed it in the meantime, retrying from the read if the swap fails because another thread got there first.

public sealed class LockFreeStack<T>
{
    private sealed class Node(T value, Node? next)
    {
        public readonly T Value = value;
        public readonly Node? Next = next;
    }

    private Node? _head;

    public void Push(T value)
    {
        var newHead = new Node(value, _head);
        while (Interlocked.CompareExchange(ref _head, newHead, newHead.Next) != newHead.Next)
        {
            newHead = new Node(value, _head); // Head moved; retry with a fresh snapshot.
        }
    }

    public bool TryPop(out T? value)
    {
        var head = _head;
        while (head is not null)
        {
            if (Interlocked.CompareExchange(ref _head, head.Next, head) == head)
            {
                value = head.Value;
                return true;
            }
            head = _head; // Retry with the current head after a failed swap.
        }
        value = default;
        return false;
    }
}

CompareExchange(ref location, newValue, comparand) atomically checks whether location still equals comparand; if so, it sets location to newValue and returns the original value. If another thread changed location between the read and this call, the comparison fails, nothing is written, and the method returns whatever the current value actually is — exactly the signal to retry. The loop is the essential lock-free pattern: read, compute a new value from what you read, attempt to publish it with a single atomic instruction, and retry from the read if publishing failed because the world changed underneath you. No thread ever blocks another; a losing thread simply does slightly more work and tries again. This is also precisely the shape that becomes vulnerable to the ABA problem if node identity, rather than value, matters for correctness.

What interviewers look for: A correct, compiling retry loop with an accurate explanation of what CompareExchange's return value means — many candidates describe CAS in words but get the retry condition backwards when asked to write it.

Q7 What is the ABA problem, and how do lock-free algorithms guard against it?#

Short answer: The ABA problem happens when a compare-and-swap check sees the same value it expects and proceeds, even though the underlying data changed and changed back in between — value A became B and then A again — so the CAS succeeds on a superficial match while the structure it points into is no longer the one the thread actually reasoned about.

Classic example: thread 1 reads the head of a lock-free stack as node A, then gets suspended before its CAS runs. Thread 2 pops A, pops the node after it, then pushes something that ends up as the head again in a way thread 1 cannot distinguish from A. Thread 1 resumes, its CAS compares the head against A, sees a match, and succeeds — but the stack's actual contents underneath have changed in ways thread 1 never observed, potentially corrupting the chain of Next pointers. The classic guard is a tagged pointer or version counter: pair the pointer with a counter that increments on every successful CAS, and compare both together, so "the pointer is A again" no longer matches unless the version also matches. On .NET, the exact address-reuse form of ABA is less of a concern, since the garbage collector generally does not hand a still-referenced object's memory back out mid-operation, but the logical ABA problem — a value legitimately returning to an earlier state through valid operations, not memory reuse — still applies to hand-rolled CAS loops and needs the same versioning defense, which is a large part of why using the BCL type is the right default.

What interviewers look for: A concrete example, not just the name, plus the honest nuance that managed runtimes change the shape of the risk without eliminating the logical version of the problem.

Follow-up questions:

• Why does garbage collection reduce, but not eliminate, exposure to the classic ABA problem in .NET?
• How would you add a version counter to the stack from the previous question?

Q8 What is false sharing, and how do you detect and fix it?#

Short answer: False sharing happens when two unrelated pieces of data that different threads write to independently happen to sit on the same CPU cache line, so every write from one thread invalidates the other thread's cached copy even though the two threads never touch the same logical data, turning independent, parallel work into constant cross-core cache traffic.

Modern CPUs move memory between cores in fixed-size cache lines, commonly 64 bytes. If thread A increments one element of a tightly packed int[] and thread B increments the element right next to it, both elements likely live on the same cache line. Every write by A forces B's core to discard and reload its cached copy of that line, and vice versa, even though A and B never logically share a value — the hardware coherence protocol cannot distinguish "different variables, same line" from "same variable," so it treats every write as a potential conflict. The symptom is a specific kind of scalability failure: code that looks embarrassingly parallel, where each thread owns its own counter or slot in an array, scales far worse than expected as core count increases, without any lock or contention visible in the code itself. It typically shows up in profiling as unexpectedly high time spent on memory access with no obvious synchronization, and hardware performance counters for cache-line invalidation traffic confirm it directly when available. The standard fix is padding: space out per-thread or per-core data so each independent value lands on its own cache line, either with unused filler fields around a hot field or a padded wrapper type sized to at least 64 bytes.

What interviewers look for: A correct mental model of cache-line-granularity coherence, not just "cache stuff got slow," plus a concrete fix and a plausible detection method.

Common mistakes: Confusing false sharing with true contention, where threads actually race on the same variable — the defining feature of false sharing is that the threads' logical data never overlaps at all.

Q9 When does a plain lock outperform or outsimplify a lock-free design?#

Short answer: A plain, uncontended or lightly contended lock around a short critical section is usually fast enough, always simpler, and far less bug-prone than a hand-rolled lock-free structure; reach for lock-free code only after measuring real contention a lock demonstrably cannot handle, not by default on the assumption that lock-free automatically means faster.

Modern lock implementations are highly optimized for the common case: an uncontended lock is extremely cheap, and even under moderate contention, a well-implemented lock with brief spinning before falling back to a true wait often performs comparably to a naive lock-free retry loop, because both are ultimately bounded by the same underlying hardware synchronization primitives. Lock-free code only starts to clearly win once contention is high enough, and critical sections short enough, that avoiding blocking altogether measurably matters, which is a narrower band of real workloads than most engineers assume. The bigger cost of hand-rolled lock-free code is correctness risk, not performance: a lock-protected critical section is trivial to reason about, since exactly one thread executes it at a time, full stop. A compare-and-swap retry loop has to correctly handle every interleaving of reads, retries, and concurrent mutations, is vulnerable to subtle bugs such as the ABA problem, and is genuinely difficult to test, since the bugs are timing-dependent and may not reproduce reliably in CI — a team that cannot safely modify such code months later has effectively made it unmaintainable, regardless of its benchmark numbers on day one. The practical rule: use the BCL's concurrent collections and lock by default, and reach for a targeted lock-free structure only when profiling shows a specific lock as a measured bottleneck.

What interviewers look for: A measurement-driven answer that treats lock-free code as a cost to be justified, not a default "advanced" choice — this question often reveals whether a candidate has actually maintained lock-free code long-term versus only written it once.

Common mistakes: Assuming "lock-free" is a synonym for "faster" without qualification, or that locks are inherently slow regardless of contention level.

Q10 How would you code-review a hand-rolled lock-free data structure submitted by a teammate?#

Short answer: Verify there is a measured reason it needs to be lock-free at all, check every compare-and-swap loop for correct retry semantics and ABA exposure, confirm every field that participates in the protocol is mutated only through Interlocked, and insist on concurrent stress tests, not just single-threaded unit tests, before approving it.

Start with the justification, not the code: ask what contention or latency measurement motivated a lock-free design over a lock, and whether a BCL alternative was considered and ruled out for a specific reason — a lot of hand-rolled lock-free code in review is solving a performance problem nobody has actually measured. Trace every CAS loop by hand: does it correctly retry using the value CompareExchange returns rather than re-reading the field separately, which would reintroduce a race between the read and the retry? Does the algorithm depend on node or pointer identity in a way exposed to the ABA problem, and if so, is there a version counter or equivalent guard? Are all fields the CAS protocol touches accessed exclusively through Interlocked operations everywhere in the class — a single plain read or write outside the protocol anywhere in the codebase is enough to reintroduce a race. Check memory visibility beyond the CAS itself: fields read outside an Interlocked operation may need volatile or an explicit memory barrier to guarantee visibility across threads, which is a frequent gap even in code that gets the CAS logic itself right. Finally, require tests that actually exercise concurrency — many threads hammering push, pop, add, or remove simultaneously for a sustained period, ideally run repeatedly in CI — because lock-free bugs are timing-dependent and a single-threaded unit test suite will pass cleanly on genuinely broken code.

What interviewers look for: A concrete review checklist rather than "I'd be careful" — specifically, checking retry correctness, ABA exposure, memory visibility outside the CAS, and requiring genuine concurrent stress testing before sign-off.