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 hard 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 Contiguous Memory Manager | OpenAI Coding Question

Implement a Contiguous Memory Manager

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are asked to implement a contiguous memory manager for an array of `n` memory cells indexed from `0` to `n - 1`, where all cells are initially free. Support the following operations: 1. `allocate(size, id) -> int` - Find the **leftmost** free contiguous segment whose length is at least `size`. - Allocate the first `size` cells of that segment and label them with allocation ID `id`. - Return the starting index of the allocated segment. - If no such segment exists, return `-1`. 2. `release(id) -> int` - Free **all** cells currently allocated with allocation ID `id`. - After freeing memory, merge any adjacent free segments into a single larger segment. - Return the total number of cells released. Additional notes: - Multiple allocations may share the same `id`. - The number of operations is `m`, and `n` may be much larger than `m` (for example, `n` can be up to `10^9`). - A solution that scans the entire memory array for every operation is too slow. Design the data structure and implement both operations efficiently.

Quick Answer: This question evaluates competence in designing efficient data structures and algorithms for interval management, contiguous allocation and deallocation over large sparse arrays, emphasizing complexity analysis and handling of large address spaces.

You manage a contiguous memory space of n cells indexed from 0 to n - 1. Initially, every cell is free. Process a sequence of operations and return the result of each one in order. There are two kinds of operations: 1. ('allocate', size, mID): Find the leftmost free contiguous block with length at least size. Allocate its first size cells to mID and return the starting index. If no such block exists, return -1. 2. ('free', mID): Free every currently allocated block owned by mID, merge adjacent free blocks if needed, and return the total number of cells released. The same mID may be used in multiple successful allocations before it is freed. Because n can be very large, you should not simulate memory cell-by-cell.

Constraints

1 <= n <= 10^9
0 <= len(operations) <= 2 * 10^5
For an allocate operation, 1 <= size <= n and 1 <= mID <= 10^9
For a free operation, 1 <= mID <= 10^9
An O(n) memory array solution is not acceptable for the largest tests

Examples

Input: (10, [('allocate', 3, 1), ('allocate', 2, 2), ('free', 1), ('allocate', 4, 3), ('allocate', 1, 4), ('free', 2), ('allocate', 3, 5)])

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

Explanation: After the first two allocations, freeing mID 1 releases cells [0..2]. The allocation of size 4 must skip that block and use the free block starting at 5. Later, freeing mID 2 merges with the adjacent free block on its left, allowing the final allocation to start at index 1.

Input: (5, [('free', 7), ('allocate', 5, 1), ('allocate', 1, 2), ('free', 1), ('allocate', 2, 3)])

Expected Output: [0, 0, -1, 5, 0]

Explanation: Freeing a non-existent mID releases 0 cells. Allocating size 5 uses the whole memory, so the next allocation fails. Freeing mID 1 restores all 5 cells, and the final allocation starts at 0.

Input: (12, [('allocate', 2, 1), ('allocate', 3, 2), ('allocate', 2, 1), ('free', 1), ('allocate', 4, 3), ('free', 2), ('allocate', 5, 4), ('free', 3), ('free', 4)])

Expected Output: [0, 2, 5, 4, 5, 3, 0, 4, 5]

Explanation: mID 1 owns two separate blocks, so freeing it releases 4 cells total. Later frees trigger merges with neighboring free intervals, eventually rebuilding the entire memory into one free block.

Input: (1, [('allocate', 1, 1), ('free', 1), ('allocate', 1, 2), ('free', 3)])

Expected Output: [0, 1, 0, 0]

Explanation: This checks the single-cell boundary case. The one cell can be allocated and freed correctly, and freeing an ID that is not present returns 0.

Input: (8, [])

Expected Output: []

Explanation: With no operations, there are no results to return.

Hints

Think in terms of intervals instead of individual cells. Allocation splits one free interval, and freeing only needs to check the immediate left and right neighbors for possible merges.
To avoid scanning all free blocks on every allocation, keep free intervals ordered by start position and store the maximum free-block length in each subtree so you can find the leftmost valid interval quickly.

Quick Overview

This question evaluates competence in designing efficient data structures and algorithms for interval management, contiguous allocation and deallocation over large sparse arrays, emphasizing complexity analysis and handling of large address spaces.