Problem
Suppose you have an array of size n that represents computer memory. You have to allocate contiguous blocks of memory. There are two operations that can happen:
i. Allocate(x) - Find a contiguous block of x positions that are all unmarked. Mark this block of positions as used. If a block of this size exists, return the first position in the block. If no such block exists, return -1.
ii. Free(p, x) - Unmark a contiguous block of x positions starting at position p. Initially, there is a single unmarked block of size n. After a series of operations, the array will be chopped up into many blocks, some marked and some unmarked.
Describe how to efficiently implement each of these operations. Analyze the worst-case runtime of each operation. Note that n can potentially be very large.