Explain how garbage collection decides what to free

This is a mental-model question. The interviewer wants to hear "reachability," not "objects that aren't used anymore." Garbage collectors do not count usage; they compute reachability from roots.

The mental model: a set of roots — global/static variables, stack frames, registers, thread-local storage — references objects. Anything transitively reachable from a root is alive. Everything else is garbage, regardless of how long it has been unreachable. A tracing GC is a graph traversal with the object graph and a roots set.

Walk through the three phases of a tracing collector:

1. Mark. The GC traverses from roots through object fields, marking every object it visits. This is where the algorithm spends most of its time; how it avoids revisiting (mark bits, tri-color marking for concurrent collectors) is the real engineering.
2. Sweep. The heap is scanned linearly and every unmarked object is freed; its memory returns to a free list. Fragmentation is the downside of sweep.
3. Compact (optional). Move survivors to the start of the heap to defragment, at the cost of rewriting all references — which is why compacting collectors need either pinned objects, read barriers, or a stop-the-world pause.

Generational collection exists because of the weak generational hypothesis: most objects die young. The heap is split into generations — typically a small nursery and one or two older generations. Allocations land in the nursery; minor GCs collect only the nursery, promoting survivors (often with an age counter) to the old generation. Old-gen GCs are rare but expensive. Cards or remembered sets track old-gen objects that point into the nursery so a minor GC doesn't have to scan all of the old gen.

Tradeoffs and edge cases worth naming:

• Stop-the-world pauses — the tradeoff curve between pause time and throughput; concurrent (mostly) collectors trade CPU and complexity for shorter pauses.
• Finalizers (Java finalize, .NET Finalize) require a finalization queue and a separate finalizer thread, which means an unreachable object gets at least one extra collection cycle — nondeterministic cleanup that leaks memory if the finalizer is slow.
• Reference counting (Python, Swift's older ARC) is a different family: free at zero count, immediate, deterministic — but pays per-reference overhead and breaks on cycles unless handled.
• WeakReference/WeakRef lets you observe collection: the referent becomes null at a GC boundary.

A strong closing: "deciding what to free is a reachability computation; deciding when to do it is a pause-time vs throughput engineering choice."