Quick Overview

This question evaluates understanding of memory allocator concepts including malloc/free semantics, contiguous allocation, fragmentation handling, coalescing of adjacent free blocks, pointer validation, and data-structure choices for efficient allocation.

Implement a memory allocator with malloc/free

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are implementing a simplified memory allocator over a contiguous memory region. Initialize the allocator with a fixed total size: - `allocator(totalSize)` creates an allocator that manages bytes indexed from `0` to `totalSize-1`. Implement two operations: - `malloc(size) -> pointer` - Allocates a **contiguous** block of `size` bytes. - Returns a `pointer` representing the allocated block (you may define this as an integer start index, or an opaque handle that can later be passed to `free`). - If no contiguous block of at least `size` bytes is available, return a null/invalid pointer (e.g., `-1` or `null`). - `free(pointer) -> bool` - Frees the block previously returned by `malloc`. - Returns `true` if the pointer was valid and the block was freed, otherwise returns `false` (e.g., double-free or unknown pointer). ### Requirements / Clarifications - The allocator must support many interleaved `malloc` and `free` calls. - Freed space should become available for future allocations. - You must correctly handle merging/coalescing of adjacent free blocks to reduce fragmentation. - Discuss (and aim for) better-than-linear performance per operation if possible (e.g., around \(O(\log n)\) for finding a suitable free block). ### Example (one possible interpretation) - `allocator(10)` - `p1 = malloc(3)` might return `0` (allocates `[0..2]`) - `p2 = malloc(4)` might return `3` (allocates `[3..6]`) - `free(p1)` frees `[0..2]` - `p3 = malloc(2)` might return `0` (reuses part of `[0..2]`) ## What to deliver Explain and implement the data structures and algorithms needed to support `malloc` and `free` efficiently, including coalescing and pointer validation.

Overview: This question evaluates understanding of memory allocator concepts including malloc/free semantics, contiguous allocation, fragmentation handling, coalescing of adjacent free blocks, pointer validation, and data-structure choices for efficient allocation.

You are implementing a simplified memory allocator over a contiguous byte-addressed memory region. The allocator manages bytes indexed from 0 to totalSize-1 and must support many interleaved allocations and deallocations. Operations: - malloc(size) -> pointer - Allocate a contiguous block of `size` bytes. - Return the start index (an integer pointer) of the allocated block. - If no contiguous free block of at least `size` bytes exists, return -1. - free(pointer) -> bool - Free the block previously returned by malloc (identified by its start index). - Return True if the pointer is valid and the block was freed. - Return False if the pointer is invalid (unknown pointer or double-free). Freed blocks must be merged (coalesced) with adjacent free blocks to reduce fragmentation. Implement the allocator to be efficient (aim for ~O(log n) per operation).

Constraints

  • 1 <= totalSize <= 10^9
  • 1 <= len(operations) <= 2 * 10^5
  • For ('malloc', size): 1 <= size <= 10^9
  • Pointers passed to free may be invalid or already freed
  • Memory blocks returned by malloc are always contiguous and non-overlapping

Examples

Input: (10, [('malloc', 3), ('malloc', 4), ('free', 0), ('malloc', 2), ('free', 3), ('malloc', 5)])

Expected Output: [0, 3, True, 0, True, 2]

Explanation: Alloc 3 at 0, alloc 4 at 3, free 0..2, alloc 2 reuses 0..1, free 3..6 which coalesces with remaining free into 2..9, alloc 5 at 2.

Input: (5, [('malloc', 2), ('malloc', 3), ('malloc', 1), ('free', 0), ('free', 0), ('malloc', 1)])

Expected Output: [0, 2, -1, True, False, 0]

Explanation: After allocating 2 and 3 bytes, no space remains. Freeing pointer 0 succeeds once, then fails on double-free. Final malloc(1) uses freed space at 0.

Implement a Memory Allocator with malloc/free

mediumOpenAISoftware Engineer

You are implementing a simplified memory allocator over a contiguous byte-addressed memory region.

The allocator manages bytes indexed from 0 to totalSize-1 and must support many interleaved allocations and deallocations.

Operations:

  • malloc(size) -> pointer

    • Allocate a contiguous block of size bytes.
    • Return the start index (an integer pointer) of the allocated block.
    • If no contiguous free block of at least size bytes exists, return -1.
  • free(pointer) -> bool

    • Free the block previously returned by malloc (identified by its start index).
    • Return True if the pointer is valid and the block was freed.
    • Return False if the pointer is invalid (unknown pointer or double-free).

Freed blocks must be merged (coalesced) with adjacent free blocks to reduce fragmentation.

Implement the allocator to be efficient (aim for ~O(log n) per operation).

View full question (all parts)

Problem

You are implementing a simplified memory allocator over a contiguous memory region.

Initialize the allocator with a fixed total size:

  • allocator(totalSize) creates an allocator that manages bytes indexed from 0 to totalSize-1.

Implement two operations:

  • malloc(size) -> pointer

    • Allocates a contiguous block of size bytes.
    • Returns a pointer representing the allocated block (you may define this as an integer start index, or an opaque handle that can later be passed to free).
    • If no contiguous block of at least size bytes is available, return a null/invalid pointer (e.g., -1 or null).
  • free(pointer) -> bool

    • Frees the block previously returned by malloc.
    • Returns true if the pointer was valid and the block was freed, otherwise returns false (e.g., double-free or unknown pointer).

Requirements / Clarifications

  • The allocator must support many interleaved malloc and free calls.
  • Freed space should become available for future allocations.
  • You must correctly handle merging/coalescing of adjacent free blocks to reduce fragmentation.
  • Discuss (and aim for) better-than-linear performance per operation if possible (e.g., around O(log⁡n)O(\log n) for finding a suitable free block).

Example (one possible interpretation)

  • allocator(10)
  • p1 = malloc(3) might return 0 (allocates [0..2])
  • p2 = malloc(4) might return 3 (allocates [3..6])
  • free(p1) frees [0..2]
  • p3 = malloc(2) might return 0 (reuses part of [0..2])

What to deliver

Explain and implement the data structures and algorithms needed to support malloc and free efficiently, including coalescing and pointer validation.

Examples

Example 1
Input
(10, [('malloc', 3), ('malloc', 4), ('free', 0), ('malloc', 2), ('free', 3), ('malloc', 5)])
Output
[0, 3, True, 0, True, 2]
Notes
Alloc 3 at 0, alloc 4 at 3, free 0..2, alloc 2 reuses 0..1, free 3..6 which coalesces with remaining free into 2..9, alloc 5 at 2.
Example 2
Input
(5, [('malloc', 2), ('malloc', 3), ('malloc', 1), ('free', 0), ('free', 0), ('malloc', 1)])
Output
[0, 2, -1, True, False, 0]
Notes
After allocating 2 and 3 bytes, no space remains. Freeing pointer 0 succeeds once, then fails on double-free. Final malloc(1) uses freed space at 0.

Constraints

  • •1 <= totalSize <= 10^9
  • •1 <= len(operations) <= 2 * 10^5
  • •For ('malloc', size): 1 <= size <= 10^9
  • •Pointers passed to free may be invalid or already freed
  • •Memory blocks returned by malloc are always contiguous and non-overlapping

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def solution(totalSize: int, operations: list[list[str]]) -> str:
Sample call
solution(10, [('malloc', 3), ('malloc', 4), ('free', 0), ('malloc', 2), ('free', 3), ('malloc', 5)])
Language
Case 1
Input
(10, [('malloc', 3), ('malloc', 4), ('free', 0), ('malloc', 2), ('free', 3), ('malloc', 5)])
Expected
[0, 3, True, 0, True, 2]
Case 2
Input
(5, [('malloc', 2), ('malloc', 3), ('malloc', 1), ('free', 0), ('free', 0), ('malloc', 1)])
Expected
[0, 2, -1, True, False, 0]

Browse More Questions

Show the approach

Approach

The allocator models memory as a sorted list of free intervals free_list, each stored as [start, end) (half-open) and kept ordered by start. Initially the whole region is one free interval [0, totalSize). A dict allocated maps each live pointer to its block size.

malloc(size) — uses first-fit: scan free_list left to right for the first interval [s, e) with e - s >= size. Allocate from its front: the returned pointer is s. If the interval is exactly size, remove it; otherwise shrink it in place to [s + size, e). Record allocated[s] = size. If no interval fits, return -1.

free(pointer) — if pointer isn't a key in allocated, it's invalid or a double-free, so return False. Otherwise pop its size and form the freed interval [ns, ne) = [ptr, ptr + size). A binary search (lower_bound_free) finds insertion index i, the first interval whose start is >= ns. Then coalesce with neighbors:

  • merged_left if the interval at i-1 ends exactly at ns;
  • merged_right if the interval at i starts exactly at ne.

If both, the three pieces fuse: extend free_list[i-1]'s end to free_list[i]'s end and delete i. If only left, extend [i-1]'s end to ne. If only right, pull [i]'s start back to ns. If neither, insert [ns, ne) at i. Return True.

Correctness: intervals stay sorted, disjoint, and maximally merged, so adjacency checks against only the two neighbors at i-1/i suffice to keep fragmentation minimal. The allocated dict guarantees only genuinely live pointers can be freed, correctly rejecting invalid and double-frees.

Space complexity:
O(n + a), where n is the number of free intervals held in free_list and a is the number of currently allocated blocks tracked in the allocated dict. The outputs list adds O(m) for m operations.