Memory Allocator
Updated
Problem statement
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 ofsizeconsecutive free units, give all of them toid, 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 byidfree again and answer with how many units were freed (0 ifidholds 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 <= 1000and1 <= 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