Why this matters: the core allocator makes several honest compromises — one-sided coalescing, a linear first-fit scan, packing left on the table. Each compromise has a classical remedy with its own price tag, and knowing this neighborhood is what lets you answer follow-ups by reasoning from your own design rather than reciting allocator trivia.

Boundary tags: buying the backward merge

Lesson 02's asymmetry — next neighbor computable, previous neighbor not — has a classical fix: give blocks a footer (a boundary tag), a copy of the size at the block's end. The previous block's footer then sits immediately before your header, at a fixed offset, and backward coalescing becomes the same O(1) move as forward:

[ hdr size | payload ... | ftr size ][ hdr size | payload ... | ftr size ]
                          ^ read this to find the PREVIOUS block's start

The costs, stated fairly: eight more bytes per block of overhead, and a second word to keep consistent on every size change. The refinement worth knowing — and worth saying, because it shows the trade can be sharpened — is that only free blocks need readable footers: an allocated block's neighbor never merges into it, so the footer space can be reclaimed for payload while a block is live, with a bit in the header recording whether the previous block is free. Full two-sided immediate coalescing, near-zero live overhead — at the price of trickier invariants. That price/precision ladder is exactly the shape of answer a senior systems round rewards.

Segregated free lists: buying the scan

First-fit's O(F) scan is the allocator's slowest path. The classical remedy: multiple free lists, one per size class — 32, 64, 128, and so on. Allocation rounds the request to a class and pops the first entry of that class's list; only when the class is empty does it borrow from a larger one and split.

class[32]  -> free blocks 32..63 bytes
class[64]  -> free blocks 64..127
...
alloc: index by size class -> pop head    ~O(1) common case

The prices: bounded internal fragmentation from class rounding (a 65-byte request occupies a 128-class block, and that waste is by design), more lists whose membership invariant must hold, and coalescing that now moves merged blocks between classes. Real allocators judge the trade worth it — near-constant allocation is what production demands — but in a 45-minute round, naming this as the scaling path while shipping first-fit is the right scope call, and saying why (the objective was latency at interview scale, not throughput at datacenter scale) closes the loop.

realloc: the contract with an escape hatch

Growing an allocation in place is possible exactly when the next block is free and large enough — the same neighbor arithmetic free already uses. When it isn't, realloc's contract permits the escape hatch: allocate elsewhere, copy, free the original. The design insight is that realloc is a policy over primitives you already built — try-extend, else move — plus one honesty obligation: the pointer may change, and callers who cached the old one are broken by contract, not by bug. Sketching realloc this way takes four sentences and demonstrates that your allocator's pieces compose, which is much of what the question probes when it comes up.

Measuring fragmentation, not vibing it

"Fragmentation" stays hand-wavy until you pick a number. The one that matters operationally: largest satisfiable request versus total free bytes. A heap with 300 KiB free that cannot serve a 40 KiB request is badly fragmented no matter how healthy the total looks; the ratio of largest-free-block to total-free memory captures it in one figure. Cheap to compute in a debug walk (the buffer is arithmetic-walkable by design), and it turns a fuzzy complaint into a graph you can watch degrade — or prove stable — under a workload. Offering a measurement when fragmentation comes up, rather than an adjective, is a distinguishing move.

Debugging a heap that lies

Allocator bugs corrupt the very metadata you'd use to find them, so hardening is about making lies loud:

• Header sanity on every free: size a multiple of 8, within buffer bounds, flag coherent — a scribbled header fails fast instead of propagating.
• Canary words flanking payloads in debug builds: overruns announce themselves at free time with an address, instead of as a mysterious crash three calls later.
• Poisoning freed payloads (a recognizable byte pattern): use-after-free reads produce obviously-wrong values, and the free-list overlay makes corruption of poisoned bytes visible — if the pattern is disturbed outside the node links, someone wrote to freed memory.
• A debug heap-walk asserting the full invariant list from lesson 02 — contiguity, flag/list agreement, no adjacent free pairs — run after every N operations in tests. The walkable layout makes this a twenty-line function, and it converts "the heap is corrupt somewhere" into "invariant three failed at block 0x1004A0."