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.

Loading coding console...

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.