Hash Partition Offsets
Updated
Problem statement
Given an integer array values and a positive number of partitions partitions, compute the offsets for a stable hash partition of the array.
For this exercise, assign value x to partition ((x % partitions) + partitions) % partitions. Partitions appear in increasing partition-ID order. Elements in the same partition retain their original input order; do not sort their values.
Returned offsets
Return an integer matrix with exactly two rows:
- Row
0isboundaries, of lengthpartitions + 1. Partitionboccupies the half-open range[boundaries[b], boundaries[b + 1])in the partitioned array. The first boundary is0and the final boundary isvalues.length. Empty partitions have equal adjacent boundaries. - Row
1isoffsets, of lengthvalues.length.offsets[i]is the zero-based destination position of the original elementvalues[i]in that layout.
Return the offsets only; you do not need to return the rearranged values. For empty input, return partitions + 1 zero boundaries and an empty second row.
GPU discussion
This function computes a deterministic offset layout in an ordinary function runtime. After solving it, explain how to parallelize histogram construction, scan partition counts, and assign distinct output positions on a GPU. Discuss memory access, synchronization, and skewed partitions. Executing a GPU kernel is outside this function contract.
Function
hashPartitionOffsets(values: int[], partitions: int) → int[][]Examples
Example 1
values = [8,3,7,6,2,5]partitions = 3return = [[0,2,3,6],[3,0,2,1,4,5]]The partition IDs are [2,0,1,0,2,2]. Partition sizes are [2,1,3], so the boundaries are [0,2,3,6]. In the partitioned layout, the original elements occupy positions [3,0,2,1,4,5].
Example 2
values = [-1,-4,0,2]partitions = 3return = [[0,1,1,4],[1,2,0,3]]Normalized modulo places -1, -4 and 2 in partition 2, and 0 in partition 0. Partition 1 is empty; its two boundaries are both 1. Relative order within partition 2 remains -1, -4, 2.
Example 3
values = []partitions = 2return = [[0,0,0],[]]Every partition is empty. There are three zero boundaries and no per-element offsets.
Constraints
0 <= values.length <= 100000.-10^9 <= values[i] <= 10^9.1 <= partitions <= 100000.- Duplicate values are allowed.
- Target
O(values.length + partitions)time andO(partitions)auxiliary space, excluding the returned arrays.
More NVIDIA Phone Screen questions
- Summarize Server Healthcheck LogsPHONE SCREEN · Seen Oct 2026
- Filter Paginated Medical RecordsPHONE SCREEN · Seen Oct 2026
- Least Frequently Used CachePHONE SCREEN · Seen Oct 2026
- Parallel String Counts with a Custom Hash TablePHONE SCREEN · Seen Oct 2026
- Simulate a Reference-Counted Smart PointerPHONE SCREEN · Seen Aug 2026
- Streaming Top-K Frequent ElementsPHONE SCREEN · Seen Aug 2026
- Merge Multiple Sorted StreamsPHONE SCREEN · Seen Aug 2026
- Linked List Palindrome in Constant SpacePHONE SCREEN · Seen Aug 2026
- LRU Key-Value Cache OperationsPHONE SCREEN · Seen Aug 2026
- Transformer KV Cache OperationsPHONE SCREEN · Seen Aug 2026
Similar questions at other companies
- Friend Requests by AgeBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Count Non-Overlapping Pairs of Rectangles That Sum to KWisdomAI · PHONE SCREEN
- Peak Chat Load Across AgentsCresta · PHONE SCREENCresta interview questions
- Trapping Rain WaterGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Apply Operations to Make a String EmptyFlexport · PHONE SCREENFlexport interview questions
- Find Valid SET Card TriplesSnowflake · OA · PHONE SCREENSnowflake interview questions
- Best Improvement Period of at Least K IntervalsAmazon · PHONE SCREEN
- Majority Labels over Audio IntervalsNooks · PHONE SCREEN
- Random Pick with Weight Using Recorded DrawsGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Maximum Sum Desirable SubarrayGroww · PHONE SCREEN