In-Memory Memory Allocator with malloc/free, First-Fit and Best-Fit

Problem: Implement a Memory Allocator You are given a contiguous memory region of N bytes, with addresses from 0 to N - 1. Initially, all memory is free. Implement a memory manager supporting the following operations: malloc(k): allocate a physically contiguous block of k bytes. If successful, return the starting address of the allocated block. If no large enough contiguous free block exists, return -1. free(ptr): free the allocated block that starts at address ptr. The free operation only gives you the starting address, so you must remember the size of each allocated block. After freeing a block, merge it with adjacent free blocks if possible. If ptr is not the starting address of a currently allocated block, return ERROR; otherwise return OK. There are two hard constraints: A malloc(k) allocation must occupy one contiguous interval. It cannot be split into multiple pieces. Allocated blocks cannot be moved, so compaction is not allowed. You need to support two allocation strategies: First-Fit Choose the first free block, in increasing address order, whose size is at least k. Best-Fit Choose the smallest free block whose size is at least k. If multiple candidate blocks have the same size, choose the one with the smallest starting address. Input Format The first line contains: N Q strategy where: N is the total memory size. Q is the number of operations. strategy is either FIRST or BEST. The next Q lines each contain one operation: malloc k free ptr Output Format Print one line for each operation: For malloc k, print the allocated starting address, or -1 if allocation fails. For free ptr, print OK if the block is freed successfully, otherwise print ERROR. Constraints 1 <= N <= 10^9 1 <= Q <= 2 * 10^5 1 <= k <= N 0 <= ptr < N Let F be the current number of free blocks. You should be able to discuss: The time complexity of malloc/free under First-Fit. How to optimize Best-Fit malloc using a secondary index sorted by block size. How to merge adjacent free blocks during free by checking only neighboring intervals. Example Input: 10 5 FIRST malloc 3 malloc 4 free 0 malloc 2 malloc 4 Output: 0 3 OK 0 -1 Example Input 10 5 FIRST malloc 3 malloc 4 free 0 malloc 2 malloc 4 Output 0 3 OK 0 -1