Implement a Simulated Memory Allocator

Implement a simulated memory allocator that supports allocate(size) and free(ptr) operations analogous to malloc and free. Treat memory as a contiguous byte array of capacity N provided at initialization and return identifiers for allocated blocks. Achieve low-latency operations under heavy workloads; justify your choice of data structures (e.g., segregated free lists, interval/balanced trees, buddy system). Handle alignment and external/internal fragmentation, and support coalescing of adjacent free blocks. Provide time and space complexity analysis, discuss trade-offs among first-fit/best-fit/next-fit strategies, and describe tests and benchmarks you would write to validate correctness and performance.