How should I practice Implement Malloc?

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

Is Implement Malloc associated with Nvidia?

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

Problem · Design

Implement Malloc

Learn this problem

● Medium

NvidiaFULLTIMEONSITE INTERVIEW

Problem statement

Simulate a heap of heapSize bytes that starts as one free block at offset 0.

Process commands in order. Each command is one of:

ALLOC x: reserve a block of x bytes after rounding x up to the next multiple of 8. Choose a best-fit free block (the smallest free block that can hold the rounded size). Break ties by choosing the lowest start offset. Split any leftover tail back into the free list. Return that start offset, or -1 if no free block is large enough.
FREE offset: release the live allocation that starts at offset. Adjacent free blocks must coalesce into one free block. A FREE of an unknown or already-freed offset is a no-op.

Return the list of ALLOC results in command order. FREE commands do not produce an output value.

Function

processMallocCommands(heapSize: int, commands: String[]) → int[]

Examples

Example 1

heapSize = 32commands = ["ALLOC 8","ALLOC 16","FREE 0","ALLOC 8"]return = [0,8,0]

ALLOC 8 takes offset 0. ALLOC 16 takes offset 8. FREE 0 reopens [0, 8). The next ALLOC 8 fits that hole and returns 0.

Example 2

heapSize = 48commands = ["ALLOC 24","ALLOC 8","FREE 0","ALLOC 8"]return = [0,24,32]

After freeing offset 0, the free holes are [0, 24) and [32, 48). Best-fit for 8 bytes chooses the smaller hole at offset 32.

Constraints

8 <= heapSize <= 10^4.
heapSize is a multiple of 8.
1 <= commands.length <= 200.
Each command is ALLOC x with 1 <= x <= heapSize, or FREE offset with an integer offset.