Design Memory Allocator

MediumDesignsimulation

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Simulate a memory of n consecutive units, indexed 0 to n - 1, all initially free. Implement Allocator(n): - allocate(size, mID) finds the **leftmost** run of size consecutive free units, marks them as owned by mID, and returns the index of the first unit. If no such run exists, it returns -1 and changes nothing. - freeMemory(mID) frees every unit owned by mID and returns how many units were freed (possibly 0). The same mID can own several separate blocks; freeMemory releases all of them at once.

Examples

Input: ["Allocator","allocate","allocate","allocate","freeMemory","allocate","allocate","freeMemory","allocate","freeMemory"] [[8],[3,1],[2,2],[1,1],[2],[3,4],[2,3],[1],[4,5],[9]]
Output: [null,0,3,5,2,-1,3,4,-1,0]
Blocks go to 0-2 (id 1), 3-4 (id 2), 5 (id 1). Freeing id 2 frees 2 units, leaving free runs 3-4 and 6-7, too short for 3. Size 2 fits at 3. Freeing id 1 releases 4 units, but the longest free run (0-2) is 3 long, so size 4 fails. id 9 owns nothing.
Input: ["Allocator","allocate","allocate","freeMemory","allocate","allocate","freeMemory"] [[3],[3,2],[1,2],[2],[1,2],[1,2],[2]]
Output: [null,0,-1,3,0,1,2]
The first block fills the memory, so the next request fails. After freeing 3 units, two single-unit blocks land at 0 and 1, and both are freed together.

Constraints

  • 1 <= n, size, mID <= 1000
  • At most 1000 calls to `allocate` and `freeMemory`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More simulation problems