# Design First-Fit and Best-Fit Memory Allocation Design a simplified allocator over one contiguous arena of N bytes. It supports: - allocate(size, strategy) -> AllocationHandle or None - free(handle) -> bool ### Practice API Scope The captured report specifies a malloc-style exercise that starts with first-fit and then changes to best-fit, but it does not provide the original API or say whether deallocation is required. The explicit `free` operation, interval coalescing, handle representation, and invalid-free behavior in this version are practice extensions that make a complete allocator design testable. If the interview scope is allocation-only, implement the `allocate` subset and treat deallocation topics as follow-ups. An allocation occupies a half-open interval [start, start + size). Strategy is FIRST_FIT or BEST_FIT. Start with a correct first-fit design, then explain and sketch the changes needed for best-fit. Freed adjacent intervals must be coalesced. You may ignore alignment and thread safety unless discussing them as extensions. ### Practice Handle Assumption A handle is opaque to callers and contains an allocator-generated allocation_id plus descriptive start and size fields. allocation_id is monotonically generated and never reused during the allocator's lifetime. Even if a freed byte range is later allocated with the same start and size, the new allocation receives a different identity. The allocator's live-allocation table is authoritative; callers may not create or edit handles. free returns True exactly once for a currently live handle from this allocator. An unknown, forged, stale, or already-freed handle returns False and changes no state. The exercise assumes allocation_id does not wrap. This generation-unique identity is a practice choice that prevents a stale-handle ABA bug while preserving the reported malloc-style allocation problem. ### Constraints & Assumptions - N > 0 and every requested size is a positive integer. - allocate returns None when no free interval is large enough. - Allocation may split a free interval; freeing may merge with the left neighbor, right neighbor, or both. - Do not move live allocations to compact the arena. - start and size carried by a handle are informational; free validates identity against internal live metadata rather than trusting caller-provided offsets. ### Clarifying Questions to Ask - Is the primary objective simple code, allocation latency, or fragmentation? - What operation mix and arena size should the design optimize for? - Must offsets be aligned, and will calls be concurrent? - Should invalid frees return False, raise, or terminate in a lower-level environment? - Is handle identity a correctness token, a security capability, or both? ### Hints - Define invariants for free intervals and live allocations before choosing a data structure. - Test exact fits, splits, coalescing orders, double free, and stale-handle reuse. - Distinguish total free memory from the largest free interval. ### What a Strong Answer Covers - Correct allocation, splitting, freeing, and coalescing. - Generation-unique live handles that prevent stale reuse from freeing a newer allocation. - A defensible first-fit data structure and comparison with best-fit. - Time and space complexity for both strategies. - External fragmentation, invalid frees, and invariant-preserving tests. - Extensions such as alignment, metadata hardening, concurrency, and size classes. ### Follow-up Questions 1. Can best-fit produce worse long-term fragmentation than first-fit? 2. How would segregated free lists change complexity? 3. How can an allocator detect metadata corruption, a double free, or a forged handle? 4. What synchronization granularity would you choose for concurrent allocation?