FastPrepFirst-Fit Arena Allocator
Problems/First-Fit Arena Allocator

First-Fit Arena Allocator

AMD logoAMD● MediumNEW GRADFULLTIMEPHONE SCREENONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The new-graduate report asks for a memory allocator with alloc/free and coalescing; another C++ loop asks for a custom memory allocator implementation. The finite arena, unit sizes, first-fit policy, tuple API, failure results and bounds are authored practice details. It does not reconstruct an AMD allocator ABI. Approximate source match 75%.

Implement a small allocator over addresses 0..capacity-1. Each address is one unit; initially every unit is free. Process operations in order and return one result per operation.

  • [0,size]: reserve the lowest-address contiguous free block of exactly size units. Return its start, or -1 if no block fits. A failed allocation changes nothing.
  • [1,start]: free the entire active allocation beginning at start. Return 0 on success, or -1 if no active allocation begins there. Interior addresses and already freed addresses are invalid.

Freed neighbors can be used as one contiguous block. Addresses may be reused. This exercise uses a finite logical arena; alignment, metadata bytes, actual process pointers, payload contents and thread safety are outside its contract.

Function

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

Examples

Example 1

capacity = 8operations = [[0,3],[0,2],[1,0],[0,2]]return = [0,3,0,0]

The first two blocks start at 0 and 3. Freeing start 0 releases addresses 0 through 2. The next size-2 block therefore starts at 0.

Example 2

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

After freeing the first and last blocks, four units are free in two separate runs of length 2. No contiguous run can hold 3 units.

Constraints

  • 1 <= capacity <= 256.
  • 0 <= operations.length <= 200.
  • Every operation has exactly two entries.
  • 0 <= operations[i][j] <= 256.
  • Each row is [kind,arg]. Kind is 0 (allocate) or 1 (free). Allocation size arg is at least 1; a free argument is a candidate starting address from 0 through 256.

More AMD problems

  • Insert After a Linked-List NodeONSITE INTERVIEW · Seen Oct 2026
  • LRU CacheONSITE INTERVIEW · Seen Oct 2026
  • Lowest Common Ancestor of a Binary TreePHONE SCREEN · Seen Oct 2026
All AMD interview questionsSee AMD hiring insights
Saved
public int[] runAllocator(int capacity, int[][] operations) {
    // Write your code here.
}
Checking account…