How should I practice Memory Allocator?

Start by reading the full statement, solve the visible examples, then compare the pattern against related OpenAI online assessment problems in FastPrep.

Is Memory Allocator associated with OpenAI?

FastPrep tags this as a OpenAI coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Design

Memory Allocator

Learn this problem

● MediumOpenAIFULLTIMEPHONE SCREEN

Problem statement

You are given a continuous block of n bytes, addressed from 0 to n - 1. Initially, every byte is free.

Implement simulateMemoryAllocator, which processes a list of allocator operations and returns one output string for each operation.

The allocation strategy is fixed for the whole run:

first_fit: choose the lowest-address free block whose length is at least the requested size.
best_fit: choose the smallest free block whose length is at least the requested size. If multiple blocks have the same length, choose the lowest starting address.

The operation list contains only these commands:

malloc k: allocate a contiguous free block of exactly k bytes using the selected strategy. Return the starting address as a string, or "-1" if no eligible block exists.
free p: free the allocated block that starts at address p. Adjacent free blocks must be merged. Return "OK" if a block was freed, or "INVALID" if p is not the start of a currently allocated block.

Allocated blocks cannot be moved or compacted. If an allocation uses only part of a free block, the remaining bytes stay free.

Return an array containing the output for each operation in order.

Follow-up focus

The main allocator behavior is first fit. Best fit uses the same malloc and free operations as a strategy variant. In both cases, the key implementation detail is keeping free intervals consistent and merging neighboring intervals after free.

What the interview report shared

The report described a phone-screen coding task to implement memory allocation over a fixed contiguous memory region, including malloc, free, merging adjacent free intervals, and a best-fit follow-up.

Function

simulateMemoryAllocator(n: int, strategy: String, operations: String[]) → String[]

Examples

Example 1

n = 8strategy = "first_fit"operations = ["malloc 4", "malloc 4", "free 4", "malloc 3", "free 1", "free 0", "malloc 5"]return = ["0", "4", "OK", "4", "INVALID", "OK", "-1"]

After freeing the block at 4, first fit reuses that lowest eligible address for malloc 3. free 1 is invalid because 1 is not the start of an allocated block. The final request fails because no contiguous free block has size 5.

Example 2

n = 12strategy = "best_fit"operations = ["malloc 5", "malloc 3", "malloc 2", "free 0", "free 8", "malloc 4", "free 5", "malloc 6"]return = ["0", "5", "8", "OK", "OK", "8", "OK", "0"]

After freeing starts 0 and 8, the free blocks are [0, 4] and [8, 11]. Best fit chooses the smaller eligible block at 8 for malloc 4.

Constraints

1 <= n <= 10^9
strategy is either "first_fit" or "best_fit".
1 <= operations.length <= 10^4
Each operation is either "malloc k" or "free p".
For malloc operations, 1 <= k <= n.
For free operations, p is an integer address. It may or may not be the start of an allocated block.