Design and implement a simplified memory allocator exposing `malloc(size)` and `free(ptr)` over a single fixed-size heap (a contiguous byte array). The allocator must not request more memory from the operating system after initialization — it only manages the bytes it was given. Walk from a straightforward correct implementation to an optimized one, and analyze the trade-offs. ### Constraints & Assumptions - The heap is one contiguous region, e.g. `byte[N]`, with `N` fixed at init. - `malloc(size)` returns a pointer/offset to a block of **at least** `size` usable bytes, or fails (returns null / sentinel) if no block can satisfy the request. - `free(ptr)` marks a previously-allocated block reusable. You may assume `ptr` was returned by a prior `malloc` (but discuss defending against misuse). - Single-threaded for the core problem; concurrency is a follow-up. - Allocations should be aligned to a machine-friendly boundary (e.g. 8 or 16 bytes). ### Clarifying Questions to Ask - What is the heap size `N`, and the expected allocation size distribution (many small vs. few large)? - What alignment guarantee must payloads satisfy? - What is the contract for `malloc(0)`, double-free, and freeing an invalid pointer — defined behavior or undefined? - Are we optimizing for allocation latency, memory utilization, or worst-case fragmentation? - Is the allocator single-threaded, or must it be thread-safe? ### Part 1 — First-fit allocator with splitting Implement `malloc`/`free` using a **first-fit** strategy: linearly scan the blocks (or a free list) and use the first free block large enough. When a chosen free block is larger than requested, **split** it so the remainder stays available. State the time/space complexity of each operation. ```hint Block layout Prefix each block's payload with a small **header** (`size`, `is_free`, and links to physical neighbors). `malloc` returns the *payload* pointer; recover the header on `free` by subtracting `header_size`. Keep blocks in **physical (address) order** so neighbors are reachable. ``` ```hint Splitting threshold Don't split unconditionally. Think about what minimum the leftover must clear to be a usable block of its own — and what goes wrong if you split off something smaller than that. ``` #### What This Part Should Cover - A correct block model: header layout, the payload-vs-header pointer arithmetic, and how alignment is enforced. - A working first-fit scan with a clear, justified `MIN_PAYLOAD` / minimum-split threshold. - Correct per-operation complexity for `malloc`, `free`, and `split`, with reasoning rather than asserted constants. ### Part 2 — Coalescing and fragmentation Show how `free` should handle **adjacent free blocks** (the previous and next physical neighbors), and explain how this reduces **external fragmentation**. Distinguish external from internal fragmentation. ```hint Which neighbors, and why O(1) On `free`, you have two physical neighbors to consider. What property of the block ordering lets you reach both and merge in constant time? And keep the two fragmentation flavors straight: scattered free gaps vs. slack *inside* a block. ``` #### What This Part Should Cover - A precise external-vs-internal fragmentation distinction (scattered gaps between blocks vs. slack inside a block). - Two-sided coalescing with the previous and next physical neighbors, and why address-ordering makes the merge $O(1)$. - An honest account of what coalescing does and does not buy — it limits, but cannot eliminate, external fragmentation. ### Part 3 — Best-fit optimization Propose an optimization that chooses the **smallest** free block that still fits the request, and pick a data structure that makes the lookup efficient. Justify the structure: explain why a plain min-heap keyed by size is *not* a clean fit, and what works instead. ```hint Frame the query precisely Write down the exact query `malloc(size)` must answer over the free blocks. Is it "give me the global minimum," or something else? Once you've named the query shape, ask which structures answer *that* shape efficiently. ``` ```hint Production allocators Real-world allocators don't keep a strict global ordering of every free block. Consider how grouping free blocks could approximate best-fit while staying close to constant time. ``` ```hint Which orderings does each operation need? What ordering does coalescing rely on to reach a block's neighbors, and what ordering does the best-fit query rely on? Ask whether one structure can serve both queries efficiently — and if not, what that implies for every split and coalesce. ``` #### What This Part Should Cover - Names the query shape precisely (smallest free block with usable size $\geq$ request — a lower-bound / successor query, not a global minimum) and uses it to rule out a plain min-heap. - Picks a structure whose operations match that query (ordered map / balanced BST keyed by size, or segregated size-class lists) and reasons about, rather than just names, the candidates. - Recognizes that best-fit needs a **second** size-ordered index alongside the physical list, and states the consequence: every split and coalesce must keep both in sync. ### Part 4 — Complexity & trade-off analysis Compare first-fit and best-fit on **allocation time**, **space/metadata overhead**, and **fragmentation behavior**. State when each is preferable. ```hint Dimensions to contrast Line them up on allocation cost, `free` cost (does the structure need maintenance?), metadata size, and long-run fragmentation. Watch one subtle trap: "less wasted space per allocation" is not the same claim as "less long-run fragmentation." ``` #### What This Part Should Cover - A side-by-side comparison across allocation cost, `free`/coalesce cost, metadata overhead, and long-run fragmentation behavior. - The key insight that minimizing leftover *per allocation* (best-fit) does not automatically minimize *long-run* fragmentation, and can manufacture tiny unusable slivers. - A workload-aware verdict for latency vs. utilization vs. worst-case fragmentation, with no blanket "best-fit is better." ### What a Strong Answer Covers These cut across all four parts — an interviewer tracks them regardless of which part is under discussion: - One consistent set of conventions held throughout: a single `size` semantics (total vs. payload), one alignment rule, one source of pointer arithmetic — so the parts build on each other without contradiction. - Edge cases handled coherently end-to-end: `malloc(0)`, out-of-memory, minimum block size, double-free / invalid-pointer detection, and never returning a pointer that overlaps allocator metadata. - Correct complexity for **every** operation under each strategy, with the cost of maintaining any auxiliary index attributed to the right operation. - Engineering judgment over recipe-following: trade-offs framed against the workload rather than asserting a single "right" answer. ### Follow-up Questions - Make the allocator **thread-safe**. Start from a global lock, then reduce contention — per-thread caches, per-size-class locks, per-CPU arenas. Which operations must be atomic together? - How would you implement **O(1) coalescing** with *boundary tags* (a footer replicating the header) so the previous physical block is reachable without a `prev` pointer? - How do **segregated free lists** trade internal fragmentation for speed, and how do real allocators (e.g. buddy / slab systems) pick their size-class boundaries? - How would you detect and defend against **heap corruption** (canaries, header checksums) without unacceptable overhead?