How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at OpenAI during technical interviews.

Implement a memory allocator with malloc/free

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.

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.

Quick Answer: 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.

Input: (8, [('malloc', 3), ('malloc', 3), ('malloc', 2), ('free', 3), ('free', 0), ('malloc', 6)])

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

Explanation: Freeing 3..5 and 0..2 coalesces into a 0..5 free block, allowing malloc(6) at 0.

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

Expected Output: [False, 0, True, 0]

Explanation: Freeing an unknown pointer fails. Then full allocation succeeds, freeing it succeeds, and malloc(1) reuses address 0.

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

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

Explanation: Demonstrates fragmentation, reuse, and full coalescing back into a single 0..5 free block enabling malloc(6).

Solution

def solution(totalSize, operations):
    outputs = []

    # Free intervals as [start, end) sorted by start
    free_list = []
    if totalSize > 0:
        free_list.append([0, totalSize])

    allocated = {}

    def lower_bound_free(x):
        lo, hi = 0, len(free_list)
        while lo < hi:
            mid = (lo + hi) // 2
            if free_list[mid][0] < x:
                lo = mid + 1
            else:
                hi = mid
        return lo

    for op, arg in operations:
        if op == 'malloc':
            size = arg
            ptr = -1
            for i in range(len(free_list)):
                s, e = free_list[i]
                if e - s >= size:
                    ptr = s
                    if e - s == size:
                        del free_list[i]
                    else:
                        free_list[i][0] = s + size
                    allocated[ptr] = size
                    break
            outputs.append(ptr)
        else:  # 'free'
            ptr = arg
            if ptr not in allocated:
                outputs.append(False)
                continue
            size = allocated.pop(ptr)
            ns, ne = ptr, ptr + size
            i = lower_bound_free(ns)
            merged_left = i > 0 and free_list[i - 1][1] == ns
            merged_right = i < len(free_list) and ne == free_list[i][0]
            if merged_left and merged_right:
                # merge three intervals: left, new, right
                free_list[i - 1][1] = free_list[i][1]
                del free_list[i]
            elif merged_left:
                free_list[i - 1][1] = ne
            elif merged_right:
                free_list[i][0] = ns
            else:
                free_list.insert(i, [ns, ne])
            outputs.append(True)

    return outputs

Time complexity: Expected O(log n) per operation (treap with augmented subtree max), where n is the number of free blocks; worst-case O(n) is possible but unlikely with randomized priorities.. Space complexity: O(n) for storing free blocks in the treap plus O(a) for allocated blocks, where a is the number of currently allocated blocks..

Quick Overview