Malloc · OpenAI coding interview practice

Stage 1 of 2: Reserve and release

Background. A memory pool owns the addresses 0 to capacity - 1 and lends them out as contiguous ranges. A range at start that is n long covers the addresses start to start + n - 1.

Implement MemoryPool in pool.py: the constructor MemoryPool(capacity) and the methods reserve(size) and release(address).

reserve(size) reserves size contiguous free addresses and returns the first of them, or -1 when no free range is long enough. It uses the free range with the lowest address that is long enough (first fit) and takes the low end of it; the rest of that range stays free.
release(address) gives back the range that reserve returned address for, and returns True. Any other address is refused with False: one reserve never returned, one inside a reserved range rather than at its start, and one whose range was already given back. Once reserve returns that address again, it can be released again. A refused release changes nothing.
A released range at start that is n long joins the free range that ends at address start - 1 and the free range that begins at address start + n, when there are such ranges, so it can be reserved again as one range with them.

Example

pool = MemoryPool(10)
pool.reserve(4)    # 0      0-3 reserved
pool.reserve(3)    # 4      4-6 reserved, 7-9 free
pool.reserve(5)    # -1     no 5 free addresses in a row
pool.release(0)    # True   0-3 free
pool.reserve(2)    # 0      0-1 reserved, 2-3 still free
pool.release(4)    # True   4-6 joins 2-3 and 7-9: 2-9 free
pool.reserve(8)    # 2
pool.release(5)    # False  5 is inside the range at 2

Notes

capacity is from 1 to 10^12: too many addresses to keep an entry for each one.
size is a positive integer and may be larger than the pool. address may be any integer.
Several pools can exist at once, each with its own addresses.

Done when Submit goes green.

Constraints

Python 3.12 standard library only
Editable: pool.py
Read-only: all tests/test_*.py files
capacity is from 1 to 10^12, too many addresses to keep one entry per address

What comes after stage 1

The next stage opens once the tests for the one before it pass. Each raises the bar, the way an interviewer does in the room.

Stage 2: The tightest fit, fast. The tightest free range instead of the first, on a pool broken into tens of thousands of free ranges.

The files you get

Yours to edit: pool.py.
Tests you can read and run: tests/test_part1.py. Hidden tests run on Submit.

The round: no AI, an assistant that only answers

OpenAI runs this round without AI. Here the closest format is answer-only: the assistant answers your questions and reviews your code when you ask, the way an interviewer would, and never writes a line of it. The interviewer asks about your decisions as you go, and the report states the format. You can switch to the agent format when you press Begin.

Frequently asked, briefly answered

Is Malloc free?

Stage 1 is free with an account. The last stage needs Nyrion Pro.

Which company asks something like this?

OpenAI. It is modelled on OpenAI's coding round, which runs without AI. Based on candidates' reports of OpenAI interviews. Nyrion wrote this version, so the question you get may differ.

Do I bring my own AI tool?

No. The real round has no AI, so this one opens answer-only: an assistant that answers your questions and can't write code. You can switch to an agent that proposes changes when you press Begin.

What does the interviewer ask?

4 questions along the way about your own code, and one at the end about the whole session. A weak answer gets one follow up. The answers go into the report, which ends with a hire or no hire verdict.

Start the problem

Sign in and the problem opens where you left it. New here? An account takes a minute to create, and the first stage of this problem is free.

Start this problem → Sign in

More like it: every practice problem, OpenAI's interviews, the AI coding interview guide.