FastPrepKeyed Bounded Executor Schedule

Keyed Bounded Executor Schedule

Microsoft logoMicrosoft● HardFULLTIMEONSITE INTERVIEW
Learn

Problem statement

All tasks are submitted at time 0 in input order. Task i has key keys[i] and runs for durations[i] time units.

Build the deterministic schedule produced by these rules:

  • At most maxConcurrent tasks run at once.
  • Tasks with the same key run in submission order and never overlap.
  • Whenever capacity is available, start the smallest-index waiting task whose key is not active.
  • If no task can start, advance time to the next completion. All tasks ending at that time release their keys before new tasks start.

Return [startTime, endTime] for every task in original input order.

Function

scheduleKeyedTasks(keys: String[], durations: int[], maxConcurrent: int) → long[][]

Examples

Example 1

keys = ["a","b","a","c"]durations = [4,3,2,1]maxConcurrent = 2return = [[0,4],[0,3],[4,6],[3,4]]

Tasks 0 and 1 start first. At time 3 task 2 is still blocked by key a, so task 3 uses the free slot.

Example 2

keys = ["x","x","y"]durations = [1,1,5]maxConcurrent = 3return = [[0,1],[1,2],[0,5]]

Extra global capacity cannot make the two x tasks overlap.

Constraints

  • 1 <= keys.length = durations.length <= 100000.
  • 1 <= maxConcurrent <= keys.length.
  • Keys are nonempty printable ASCII strings.
  • 1 <= durations[i] <= 1000000.
  • Every returned time fits a signed 64-bit integer.

More Microsoft problems

See Microsoft hiring insights
public long[][] scheduleKeyedTasks(String[] keys, int[] durations, int maxConcurrent) {
    // Write your code here.
}
keys["a","b","a","c"]
durations[4,3,2,1]
maxConcurrent2
expected[[0,4],[0,3],[4,6],[3,4]]
Checking account…