FastPrep
Problem · Design

Reusable Number Allocator

Learn this problem
● MediumDropbox logoDropboxFULLTIMEONSITE INTERVIEW

Problem statement

Implement a reusable allocator for the integers from 0 through n - 1.

The allocator starts with every number available. Process the parallel arrays operations and values from left to right:

  • assign returns and reserves the smallest currently available number. If no number is available, it returns -1. Its corresponding entry in values is -1.
  • release makes values[i] available again. Every release is guaranteed to name a number that is currently assigned. A release produces no output.

Return the results of all assign operations in operation order.

Function

runNumberAllocator(n: int, operations: String[], values: int[]) → int[]

Examples

Example 1

n = 3operations = ["assign","assign","release","assign","assign"]values = [-1,-1,0,-1,-1]return = [0,1,0,2]

The first two assignments reserve 0 and 1. Releasing 0 makes it the smallest available number again, so the next assignment reuses it before assigning 2.

Example 2

n = 2operations = ["assign","assign","assign","release","assign"]values = [-1,-1,-1,1,-1]return = [0,1,-1,1]

After 0 and 1 are assigned, the allocator is exhausted and returns -1. Releasing 1 lets the final assignment return 1.

Constraints

  • 1 <= n <= 10^6
  • 1 <= operations.length <= 2 * 10^5
  • values.length == operations.length
  • Each operation is exactly assign or release.
  • For assign, the corresponding value is -1.
  • For release, 0 <= values[i] < n and that number is currently assigned.

More Dropbox problems

drafts saved locally
public int[] runNumberAllocator(int n, String[] operations, int[] values) {
    // Write your code here.
}
n3
operations["assign","assign","release","assign","assign"]
values[-1,-1,0,-1,-1]
expected[0,1,0,2]
checking account