FastPrep
Problem · Array

Leftmost Memory Block Allocator (for mle also :)

Learn this problem
● MediumByteDance logoByteDanceINTERNNEW GRADOA

Problem statement

You are given an integer array memory containing only 0s and 1s. A value of 0 means that the memory unit is free, while 1 means that it is occupied.

Process the two-element arrays in queries in order. Each query has one of two forms:

  • [0, x] is an allocation query. Find the smallest index that begins a contiguous block of x free units. If a block exists, mark all of its units as occupied, assign the next allocation ID to the block, and return its starting index. Allocation IDs start at 1 and increase only after successful allocations. If no block fits, return -1.
  • [1, id] is an erase query. If an active allocation has ID id, free every unit in that block and return its length. If the ID does not exist or has already been erased, return -1.

Memory units that are occupied initially are not associated with an allocation ID and cannot be freed by an erase query.

Return an integer array containing one result for every query.

A solution with time complexity no worse than O(memory.length^2 * queries.length) will fit within the execution time limit.

Function

processMemoryQueries(memory: int[], queries: int[][]) → int[]

Examples

Example 1

memory = [0,1,0,0,0,1,1,0,0,0,1,0,0]queries = [[0,2],[0,1],[0,1],[1,2],[1,4],[0,4]]return = [2,0,4,1,-1,-1]

The first three allocations start at indices 2, 0, and 4, receiving IDs 1, 2, and 3. Erasing ID 2 frees one unit. ID 4 does not exist, and the final allocation cannot find four consecutive free units.

Example 2

memory = [1,0,0]queries = [[1,1],[0,2],[1,1],[0,2]]return = [-1,1,2,1]

The initially occupied unit has no allocation ID, so the first erase fails. Allocating two units starts at index 1 with ID 1. Erasing that ID frees two units, and the final allocation uses the same leftmost block.

Constraints

  • 1 <= memory.length
  • Every value of memory is 0 or 1.
  • 1 <= queries.length
  • Every query contains exactly two integers.
  • queries[i][0] is 0 or 1.
  • 1 <= queries[i][1]

More ByteDance problems

drafts saved locally
public int[] processMemoryQueries(int[] memory, int[][] queries) {
    // write your code here
}
memory[0,1,0,0,0,1,1,0,0,0,1,0,0]
queries[[0,2],[0,1],[0,1],[1,2],[1,4],[0,4]]
expected[2,0,4,1,-1,-1]
checking account