How should I practice Aligned Free-List Memory Allocator?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Hudson River Trading onsite interview problems in FastPrep.

Is Aligned Free-List Memory Allocator associated with Hudson River Trading?

FastPrep tags this as a Hudson River Trading onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Design

Aligned Free-List Memory Allocator

Learn this problem

● Medium

Hudson River TradingINTERNONSITE INTERVIEW

Problem statement

Implement an allocator for one fixed-size memory region. The region contains totalBytes bytes, begins at address 0, and is divided into blocks of alignment bytes.

You are given equal-length arrays operations and values. Process them in order:

allocate requests values[i] bytes. Round the request up to a whole number of alignment blocks, then reserve the first free contiguous range large enough to hold it. Return that range's starting address, or -1 when no free range is large enough.
free releases the live allocation whose starting address is values[i]. Every free operation is guaranteed to reference a currently live allocation.

Return the addresses produced by allocate operations, in encounter order. Maintain free memory as an address-ordered linked list of maximal free ranges. Split a range when allocating and coalesce adjacent ranges when freeing.

Function

runAllocator(totalBytes: int, alignment: int, operations: String[], values: int[]) → int[]

Examples

Example 1

totalBytes = 32alignment = 8operations = ["allocate","allocate","free","allocate"]values = [9,8,0,16]return = [0,16,0]

The 9-byte request rounds up to 16 bytes and starts at 0. The 8-byte request starts at 16. Freeing address 0 makes the first 16 bytes available again, so the last request returns 0.

Example 2

totalBytes = 24alignment = 8operations = ["allocate","allocate","allocate","free","allocate"]values = [8,16,8,0,8]return = [0,8,-1,0]

The first two allocations fill the region. The third request fails. After address 0 is freed, one block is available there and the final request succeeds.

Constraints

1 <= alignment <= 1024, and alignment is a power of two.
alignment <= totalBytes <= 1000000.
totalBytes is divisible by alignment.
0 <= operations.length <= 200000.
operations.length == values.length.
Every operation is allocate or free.
For allocate, 1 <= values[i] <= totalBytes.
For free, values[i] is the starting address of a live allocation.