Buddy Allocator Split

Problem

Simulate buddy allocation on a power-of-two heap.

heap_size is the total size and requests is the list of requested sizes; each request is rounded up to a power of two. Allocate the first free block that fits, repeatedly halving it and returning the right half to the free list until it is exactly the requested size. Blocks are always taken from the left half of a split.

Return each allocated start index, or -1 when no block fits.

Hint

Halving a block returns its right half to the free list; the left half stays allocatable.

Test cases

case 1

in: [8,[1,2,3]]

expected: [0,2,4]

case 2

in: [4,[3,1]]

expected: [0,-1]

case 3

in: [8,[8,1]]

expected: [0,-1]

case 4

in: [4,[2,2,2]]

expected: [0,2,-1]

Starter codePython

def buddy_allocate(heap_size, requests):
    # Your code here
    pass

4 test cases · run your code against them in the editor