Bucket Sort with Parallel Workers
NVIDIA● MediumNEW GRADPHONE SCREENProblem statement
Given an integer array values and a positive integer workers, return a new array containing all the values in nondecreasing numeric order. Retain every duplicate occurrence and leave the supplied array unchanged.
Value buckets
Use workers independent value buckets, numbered from 0 through workers - 1. For a nonempty input, let minimum and maximum be its smallest and largest values, and let span = maximum - minimum + 1.
Assign each value x to bucket floor((x - minimum) * workers / span). Sort each bucket independently, then concatenate the sorted buckets in increasing bucket-number order. This assignment uses contiguous value ranges, so the concatenation is globally sorted.
For an empty input, return []. Compute the bucket formula with sufficient integer precision for the stated bounds.
Parallel follow-up
Explain how the bucket sorting can run on workers processors. Discuss distributing values, keeping each bucket private while it is sorted, waiting for all bucket sorts to finish, and assigning disjoint output ranges. Analyze how a heavily skewed bucket limits the benefit of parallel sorting.
The function evaluates the deterministic combined result of these bucket tasks. The reference solutions schedule them sequentially; the follow-up explains concurrent scheduling of the same independent work.
What the interview report shared
A technical screen included a bucket-sort coding task, followed by a question about parallelizing it over P processors. The report omits the precise first variant, input domain, examples, and processor model. The value ranges, partition formula, and edge behavior above define this practice version.
Function
bucketSortWithWorkers(values: int[], workers: int) → int[]Examples
Example 1
values = [9,0,5,9,-2]workers = 3return = [-2,0,5,9,9]The minimum is -2 and the inclusive span is 12. The three buckets receive [0,-2], [5], and [9,9]. Sorting each and concatenating them gives [-2,0,5,9,9].
Example 2
values = []workers = 4return = []An empty input has no minimum or maximum. Its sorted result is an empty array for every valid worker count.
Example 3
values = [1000000000,-1000000000,0]workers = 16return = [-1000000000,0,1000000000]The inclusive span is 2000000001. The values belong to buckets 15, 0, and 7, respectively. Ordered bucket concatenation returns the three numeric values in ascending order.
Constraints
0 <= values.length <= 2000.-10^9 <= values[i] <= 10^9.1 <= workers <= 16.- Duplicate values are allowed.