FastPrepLeftmost Memory Block Allocator

Leftmost Memory Block Allocator

Susquehanna International Group (SIG) logoSusquehanna International Group (SIG)● MediumFULLTIMEOA
Learn

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.

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 use starts 2, 0, and 4, receiving IDs 1, 2, and 3. Erasing ID 2 frees one unit. ID 4 does not exist, and no block of four free units remains for the final allocation.

Example 2

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

The first erase fails because no allocation exists. The allocation then creates ID 1 at index 0. Its first erase frees two units, while the repeated erase returns -1.

Example 3

memory = [1,0,0,0,1,0,0]queries = [[0,3],[0,2],[1,1],[0,2]]return = [1,5,3,1]

The first two allocations use starts 1 and 5. Erasing ID 1 frees its three-unit block, so the final allocation returns the newly available leftmost start 1.

Constraints

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

Source note: The source screenshot preserves the query formats, complexity target, and reported example.

More Susquehanna International Group (SIG) problems

See Susquehanna International Group (SIG) hiring insights
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…