← 返回 openai 的题目列表Implement malloc and free with First-Fit Allocation and Discuss Best-Fit Optimization
类型：online_judge
Problem: Implement a Simplified malloc/free
You are given a contiguous memory region of N bytes, with addresses from 0 to N - 1. Implement a simplified memory allocator supporting the following operations:
malloc size: allocate a contiguous free block of length size.
Use the first-fit strategy: scan free blocks from low address to high address and choose the first block whose size is at least size.
If allocation succeeds, return the start address of the allocated block.
If no sufficiently large contiguous free block exists, return -1.
free ptr: free the allocated block starting at address ptr.
If ptr is not the start address of a currently allocated block, print INVALID.
Otherwise free the block and print OK.
Adjacent free blocks must be merged after freeing.
Input Format
The first line contains two integers:
N Q
where:
N is the total memory size.
Q is the number of operations.
The next Q lines each contain one operation:
malloc size
free ptr
Output Format
For each operation:
For malloc size, print the allocated start address, or -1 if allocation fails.
For free ptr, print OK if successful, otherwise print INVALID.
Constraints
1 <= N <= 10^9
1 <= Q <= 5000
1 <= size <= N
0 <= ptr < N
Example
Input:
10 5
malloc 3
malloc 4
free 0
malloc 5
malloc 3
Output:
0
3
OK
-1
0
Follow-up
If Q increases to 10^5 or higher, how would you optimize malloc? For example, how would you switch from first-fit to best-fit and use a heap or balanced tree to quickly find the smallest free block that can satisfy the request?
Example
Input
10 5
malloc 3
malloc 4
free 0
malloc 5
malloc 3
Output
0
3
OK
-1
0