How should I practice First-Fit Memory Allocator?

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

Is First-Fit Memory Allocator associated with Google?

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

First-Fit Memory Allocator

Google● MediumINTERNONSITE INTERVIEW

Problem statement

Write a simple memory allocator. It manages capacity bytes of memory, with addresses from 0 to capacity - 1. At the start, all memory is one free block.

Process the requests in operations one at a time. Each request either allocates memory or frees an earlier allocation.

Allocate memory: [0, size]

Find size free bytes next to each other.

Start at the lowest address. Choose the first free block that is large enough. This is called first fit.
Use the beginning of that block. If any space is left over, keep it as a separate free block.
Return the starting address of the allocated block. If no block is large enough, return -1 and leave memory unchanged.

Free memory: [1, address]

Free the allocated block that starts at address.

If a block is currently allocated at that starting address, free the whole block and return 1.
Combine the freed block with any free block directly before or after it. The neighboring free space should become one block.
If the address is not the start of a currently allocated block, return 0 and leave memory unchanged. This includes an address inside a block, an address that has already been freed, or an address outside the memory region.
An address can be used again after it is freed. If a later allocation starts there, freeing that address frees the new allocation.

Keep track of blocks

Keep the blocks in address order. Each block records its size, whether it is free, and the blocks before and after it. You can use this header or an equivalent structure:

BlockHeader {
    size_t size;
    bool isFree;
    BlockHeader* next;
    BlockHeader* prev;
};

This bookkeeping is stored outside the managed memory, so it does not use any of the capacity bytes. Ignore alignment: do not round up allocation sizes.

Return an array with one result for each request, in the same order. If there are no requests, return an empty array.

Function

simulateAllocator(capacity: int, operations: int[][]) → int[]

Examples

Example 1

capacity = 10operations = [[0,3],[0,4],[1,0],[0,2],[0,4],[1,3],[0,7]]return = [0,3,1,0,-1,1,2]

The first two allocations occupy [0,3) and [3,7). Freeing address 0 creates a gap, and the next allocation takes [0,2). A request for four bytes fails because the free blocks have sizes one and three. Freeing address 3 merges its block with both free neighbors into [2,10), so the last allocation starts at 2.

Example 2

capacity = 8operations = [[0,8],[0,1],[1,1],[1,0],[1,0],[0,8]]return = [0,-1,0,1,0,0]

The first allocation fills memory. A further allocation fails, and address 1 cannot be freed because it is inside that allocation. Freeing address 0 succeeds once; repeating it fails. The final allocation reuses the entire region at address 0.

Example 3

capacity = 5operations = []return = []

No requests are processed, so the result is an empty array.

Constraints

1 <= capacity <= 10^9
0 <= operations.length <= 2000
Every operation has exactly two integers. The first is 0 or 1.
For allocation requests, 1 <= size <= 10^9.
For deallocation requests, 0 <= address <= 10^9.