FastPrepCoordinate Odd and Even Workers in Order

Coordinate Odd and Even Workers in Order

The D.E. Shaw Group logoThe D.E. Shaw Group● MediumFULLTIMEONSITE INTERVIEW

Problem statement

Implement two cooperating workers for the integers from 1 through n, inclusive. The odd worker produces only odd values and the even worker produces only even values. Their combined output must be in ascending order: 1, 2, 3, ..., n, regardless of which worker is scheduled first.

Use actual threads in Java, Python and C++, goroutines in Go, or Node worker threads in JavaScript. Both workers must participate when their parity has a value to produce. Coordinate them through synchronization; constructing the whole result in one worker or merging two independently completed lists does not satisfy the task.

For this exercise, assume each worker appends to one shared output sequence instead of writing to the console, and return that sequence after both workers finish.

For this exercise, assume 0 <= n <= 1000, both workers are eventually scheduled, no external interruption occurs, and n = 0 produces an empty sequence.

Function

orderedOddEven(n: int) → int[]

Examples

Example 1

n = 6return = [1,2,3,4,5,6]

The odd worker contributes 1, 3 and 5; the even worker contributes 2, 4 and 6. Synchronization interleaves those contributions as [1,2,3,4,5,6].

Example 2

n = 1return = [1]

Only the odd worker has a value to contribute. Both workers finish, and the result is [1].

Example 3

n = 0return = []

Neither worker has a value to contribute, so the result is an empty array.

Constraints

  • 0 <= n <= 1000.
  • Return an integer array containing the synchronized shared output.
  • Both workers are eventually scheduled and no external interruption occurs.

More The D.E. Shaw Group problems

See The D.E. Shaw Group hiring insights
Saved
public int[] orderedOddEven(int n) {
    // Start and synchronize the odd and even workers.
    return new int[0];
}
Checking account…