Implement a Memory Allocator with First-Fit and Best-Fit

Implement a Memory Allocator (malloc / free) Implement a simplified memory allocator that manages a fixed contiguous heap. The heap address range is [0, capacity), and the entire heap is initially free. Support the following operations: ALLOC size: allocate a contiguous block of exactly size bytes. Print its starting address, or -1 if no sufficiently large contiguous free block exists. FREE address: free the block previously returned by a successful ALLOC at address. After freeing, immediately coalesce every pair of adjacent free blocks. Part 1: First-Fit First implement first-fit: scan free blocks in increasing address order and choose the first block whose size is at least size. When the chosen block is larger than requested, allocate from its lower-address end and keep the remainder as a free block. Follow-up: Best-Fit Optimization Extend the allocator to support best-fit: among all free blocks of size at least size, choose the smallest one. Break ties by choosing the smaller starting address. Describe the data structures you would use to support all of the following: Finding adjacent free blocks and coalescing them during FREE; Efficiently finding a first-fit or best-fit candidate; Updating indexes correctly after splitting, removing, and merging blocks. Input Format The first line contains two integers: capacity q. Each of the next q lines is one operation: ALLOC size FREE address Output Format For every ALLOC, print the allocated starting address, or -1 on failure. FREE produces no output. Constraints 1 <= capacity <= 10^9 1 <= q <= 2 * 10^5 1 <= size <= capacity Every FREE address refers to a successful allocation that has not yet been freed. Ignore alignment, metadata overhead, and concurrency. Example Input: 20 7 ALLOC 8 ALLOC 5 FREE 0 ALLOC 6 FREE 8 FREE 0 ALLOC 20 Output: 0 8 0 0 Example Input 20 7 ALLOC 8 ALLOC 5 FREE 0 ALLOC 6 FREE 8 FREE 0 ALLOC 20 Output 0 8 0 0