FastPrepMemory Allocator
Problems/Memory Allocator

Memory Allocator

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a review of a Microsoft software engineering internship. Malloc was one of two coding questions in the review's second round, with no interface or rules. The task below is our choice of memory-allocator exercise.

Here memory is a row of n units (n up to 1000), all free at the start, and up to 1000 operations come as text, with sizes and ids from 1 to 1000. allocate size id takes the leftmost run of size free units, gives them to id and returns the first index, or -1 if no run fits. free id releases every unit held by id and returns how many were released. The same id may hold several blocks.

Our version is about 50% the same as the reported question.

Implement a simple memory allocator, the core of malloc and free. Memory is a row of n units numbered 0 to n - 1, all free at the start. Process the operations in order:

  • "allocate size id": find the leftmost run of size consecutive free units, give all of them to id, and answer with the index of the first unit of that run. If no such run exists, change nothing and answer -1.
  • "free id": make every unit held by id free again and answer with how many units were freed (0 if id holds none).

The same id may hold several separate blocks; free releases all of them. Return the answers of all operations, in order.

Function

processAllocator(n: int, operations: String[]) → int[]

Examples

Example 1

n = 10operations = ["allocate 3 1","allocate 2 2","allocate 4 3","free 2","allocate 1 4","allocate 3 5","free 1"]return = [0,3,5,2,3,-1,3]

Units 0-2 go to id 1, units 3-4 to id 2, units 5-8 to id 3 (unit 9 is still free). free 2 releases units 3-4 and returns 2. allocate 1 4 takes the leftmost free unit, 3. allocate 3 5 needs three free units in a row; the free units are 4 and 9, so it returns -1. free 1 releases units 0-2 and returns 3.

Example 2

n = 6operations = ["allocate 2 7","allocate 2 8","allocate 2 7","free 7","allocate 4 9"]return = [0,2,4,4,-1]

Id 7 owns two blocks, units 0-1 and 4-5. free 7 releases both and returns 4. Units 0-1 and 4-5 are free but not next to each other, so allocate 4 9 returns -1.

Constraints

  • 1 <= n <= 1000 and 1 <= operations.length <= 1000
  • Each operation is "allocate size id" or "free id", with integers written without leading zeros.
  • 1 <= size, id <= 1000

More Microsoft Onsite Interview questions

  • Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
  • Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
  • Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
  • Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
  • Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
  • Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
  • Coin ChangeONSITE INTERVIEW · Seen Oct 2026
  • Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
  • Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
  • Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026

Similar questions at other companies

  • Customer Bootstrap APIDoorDash · PHONE SCREEN · ONSITE INTERVIEWDoorDash interview questions
  • Path Leaf Character IteratorGoogle · ONSITE INTERVIEWGoogle interview questions
  • Escape Room LeaderboardPinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
  • Implement MallocNVIDIA · ONSITE INTERVIEWNVIDIA interview questions
  • Removal PoolCitadel · ONSITE INTERVIEWCitadel interview questions
  • Circuit Breaker State MachineWise · ONSITE INTERVIEW
  • Durable Data WriterDatabricks · ONSITE INTERVIEWDatabricks interview questions
  • Ring Buffer OperationsAmazon · ONSITE INTERVIEW
  • Apply Overridden Integer TransformsOptimus Information · ONSITE INTERVIEWOptimus Information interview questions
  • Randomized Collection with Duplicate ValuesOkta · ONSITE INTERVIEWOkta interview questions

Interview reports that mention this question

  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int[] processAllocator(int n, String[] operations) {
        // Write your code here.
    }
}
Checking account…