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:
1. 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.
2. Free(p, x) - Unmark a contiguous block of x marked positions starting at position p. You may assume that every Free operation will be valid - i.e. p and x are positive integers, p + x - 1 ≤ n, and every position in the set {p, p + 1, . . . , p + x - 1} is marked. 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.