Quick Overview

Simulate a memory allocator over n units: each allocation takes the leftmost run of consecutive free units for an owner, and each free releases all of that owner's units. Return the result of every operation. It tests interval bookkeeping and logarithmic-time search for free runs at up to 100,000 operations.

Leftmost-Fit Memory Allocator: Allocate Consecutive Units and Free by Owner

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You manage a memory of `n` units, indexed `0` to `n - 1`, all free at the start. Process a list of operations in order, each of which produces one recorded value: - **Allocate** `[1, size, owner]`: find the leftmost block of `size` consecutive free units. If one exists, assign every unit of that block to `owner` and record the index of the block's first unit. If none exists, change nothing and record `-1`. - **Free** `[2, owner]`: free every unit currently assigned to `owner`, and record how many units were freed (`0` if the owner holds nothing). Return the list of recorded values, one per operation, in order. ### Function Signature ```python def run_allocator(n: int, operations: list[list[int]]) -> list[int]: ``` ### Rules - "Leftmost" means the block whose first unit has the smallest index among all runs of `size` consecutive free units. The block may start anywhere inside a longer free run; only its first unit's index matters. - An owner may hold several separate blocks at the same time, from several allocations. A free releases all of them. - Allocating for an owner that already holds units is allowed and does not affect the units it already holds. - After a free, the same owner ID may allocate again. ### Constraints - `1 <= n <= 100000` - `1 <= len(operations) <= 100000` - Each allocate operation is `[1, size, owner]` with `1 <= size <= n` and `1 <= owner <= 100000`. - Each free operation is `[2, owner]` with `1 <= owner <= 100000`. - Each recorded value is `-1` or an integer from `0` to `n`, so all values fit easily in 32-bit integers. - The interviewer expected each operation to take time logarithmic in `n`, amortized over the units freed; an approach that scans the whole memory on every operation is too slow at the upper limits. ### Examples **Example 1** - Input: `n = 8`, `operations = [[1, 3, 1], [1, 2, 2], [1, 2, 3], [2, 2], [1, 3, 4], [1, 2, 5], [2, 1], [1, 4, 6]]` - Output: `[0, 3, 5, 2, -1, 3, 3, -1]` - Explanation: Owner 1 takes units 0 to 2, owner 2 takes 3 to 4, and owner 3 takes 5 to 6. Freeing owner 2 releases 2 units. No run of 3 free units exists (the free runs are units 3 to 4 and unit 7), so owner 4 gets `-1`. Owner 5 takes units 3 to 4. Freeing owner 1 releases 3 units. The free runs are now units 0 to 2 and unit 7, so a block of 4 does not fit. **Example 2** - Input: `n = 5`, `operations = [[1, 2, 7], [1, 1, 9], [1, 2, 7], [2, 7], [1, 5, 1]]` - Output: `[0, 2, 3, 4, -1]` - Explanation: Owner 7 ends up holding two separate blocks, units 0 to 1 and units 3 to 4, and freeing owner 7 releases all 4 units. Unit 2 still belongs to owner 9, so a block of 5 does not fit. **Example 3** - Input: `n = 1`, `operations = [[2, 3], [1, 1, 3], [1, 1, 4], [2, 3], [1, 1, 4]]` - Output: `[0, 0, -1, 1, 0]` - Explanation: Freeing an owner that holds nothing records `0`. After owner 3 frees its unit, owner 4 can take unit 0.

Overview: Simulate a memory allocator over n units: each allocation takes the leftmost run of consecutive free units for an owner, and each free releases all of that owner's units. Return the result of every operation. It tests interval bookkeeping and logarithmic-time search for free runs at up to 100,000 operations.

You are managing a block of memory with `n` units, indexed `0` to `n - 1`. Every unit starts out free. You are given a list of operations to process in order, and each operation produces exactly one recorded value: - **Allocate** `[1, size, owner]`: find the leftmost block of `size` consecutive free units. If such a block exists, assign every unit in it to `owner` and record the index of the block's first unit. If no such block exists, change nothing and record `-1`. - **Free** `[2, owner]`: release every unit currently assigned to `owner` and record how many units were released (`0` if the owner holds nothing). Implement `run_allocator(n, operations)` and return the recorded values, one per operation, in the same order as the operations. ### Rules - "Leftmost" means the block whose first unit has the smallest index among all runs of `size` consecutive free units. The block may start anywhere inside a longer free run; only the index of its first unit matters. This is first fit, not best fit: an earlier free run that is longer than needed wins over a later run of exactly the right length. - An owner may hold several separate blocks at once, from several allocations. A free releases all of them together. - Allocating for an owner that already holds units is allowed and leaves the units it already holds untouched. - After a free, the same owner ID may allocate again. - Every answer is uniquely determined: each allocate records either one specific index or `-1`, and each free records an exact count. ### Example 1 ``` Input: n = 8, operations = [[1, 3, 1], [1, 2, 2], [1, 2, 3], [2, 2], [1, 3, 4], [1, 2, 5], [2, 1], [1, 4, 6]] Output: [0, 3, 5, 2, -1, 3, 3, -1] ``` Owner 1 takes units 0 to 2, owner 2 takes units 3 to 4, and owner 3 takes units 5 to 6. Freeing owner 2 releases 2 units. No run of 3 free units exists (the free runs are units 3 to 4 and unit 7), so owner 4 records `-1`. Owner 5 takes units 3 to 4. Freeing owner 1 releases 3 units. The free runs are now units 0 to 2 and unit 7, so a block of 4 does not fit. ### Example 2 ``` Input: n = 5, operations = [[1, 2, 7], [1, 1, 9], [1, 2, 7], [2, 7], [1, 5, 1]] Output: [0, 2, 3, 4, -1] ``` Owner 7 ends up holding two separate blocks, units 0 to 1 and units 3 to 4, so freeing owner 7 releases all 4 units. Unit 2 still belongs to owner 9, so a block of 5 does not fit. ### Example 3 ``` Input: n = 1, operations = [[2, 3], [1, 1, 3], [1, 1, 4], [2, 3], [1, 1, 4]] Output: [0, 0, -1, 1, 0] ``` Freeing an owner that holds nothing records `0`. After owner 3 frees its unit, owner 4 can take unit 0. ### Constraints - `1 <= n <= 100000` - `1 <= len(operations) <= 100000` - Each allocate operation is `[1, size, owner]` with `1 <= size <= n` and `1 <= owner <= 100000`. - Each free operation is `[2, owner]` with `1 <= owner <= 100000`. - Each recorded value is `-1` or an integer from `0` to `n`, so every value (and every intermediate count) fits in a 32-bit signed integer. - Each operation should take time logarithmic in `n`, amortized over the units freed. An approach that scans the whole memory on every operation is too slow at the upper limits.

Constraints

  • 1 <= n <= 100000
  • 1 <= len(operations) <= 100000
  • Allocate operations are [1, size, owner] with 1 <= size <= n and 1 <= owner <= 100000
  • Free operations are [2, owner] with 1 <= owner <= 100000
  • Each recorded value is -1 or an integer in [0, n], so it fits in a 32-bit signed integer
  • Each operation should run in time logarithmic in n, amortized over the units freed; scanning all of memory per operation is too slow

Examples

Input: (8, [[1, 3, 1], [1, 2, 2], [1, 2, 3], [2, 2], [1, 3, 4], [1, 2, 5], [2, 1], [1, 4, 6]])

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

Input: (5, [[1, 2, 7], [1, 1, 9], [1, 2, 7], [2, 7], [1, 5, 1]])

Expected Output: [0, 2, 3, 4, -1]

Hints

  1. Keeping only the total number of free units is not enough: memory can have plenty of free units and still no run of the requested length. What do you need to know about a range of units to decide whether a run of length size fits inside it?
  2. For any contiguous range, the longest free run inside it is either entirely in its left half, entirely in its right half, or crosses the midpoint. Crossing runs are built from the free suffix of the left half and the free prefix of the right half.
  3. Ownership does not need to live in the tree. Remember, per owner, the (start, size) blocks it was given; a free then turns each of those ranges back to free, and each block is released at most once.

Loading coding console...

Show the approach

Approach

The reference keeps a segment tree over the n units. Each node stores three numbers for its range: the length of the free prefix, the length of the free suffix, and the longest free run anywhere inside. Two children combine as follows: the parent's prefix is the left prefix, extended by the right prefix when the whole left half is free; the suffix is symmetric; and the longest run is the maximum of the two children's longest runs and the crossing run (left suffix + right prefix). Allocating and freeing are range-assign updates (mark a range occupied or free) with lazy propagation, so each costs O(log n).

To allocate size units, first check the root: if its longest run is shorter than size, record -1. Otherwise walk down from the root toward the leftmost fit. If the left child's longest run is at least size, the answer lies in the left child. Otherwise, if the left suffix plus the right prefix reaches size, the answer is the start of that crossing run, mid - leftSuffix + 1. Otherwise it lies in the right child. Checking the left child first, then the crossing run, then the right child gives the smallest starting index, which is exactly the first-fit rule.

Ownership is tracked outside the tree in a map from owner to the list of (start, size) blocks it received. A free pops that list, marks each block free in the tree, and records the sum of the sizes (0 if the owner has no entry). Each allocation creates one block, and each block is freed at most once, so the total work over all frees is bounded by the number of allocations times O(log n).

Time complexity:
O((n + q) log n) overall, where q = len(operations): O(n) to build the tree, O(log n) per allocate, and O(log n) per released block on free (each block is released at most once)
Space complexity:
O(n + q) for the segment tree and the per-owner block lists