FastPrepHash Partition Offsets
Problems/Hash Partition Offsets

Hash Partition Offsets

NVIDIA logoNVIDIA● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an NVIDIA phone screen for a full-time role. The report describes C++ GPU hash partitioning with a histogram pass and an offset pass. It leaves out the hash function and the exact offset format. Here we use a nonnegative modulo, a stable order, two offset rows, and a core that runs on a CPU. GPU optimization stays a follow-up for discussion.

Our version is about 75% the same as the reported question.

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 0 is boundaries, of length partitions + 1. Partition b occupies the half-open range [boundaries[b], boundaries[b + 1]) in the partitioned array. The first boundary is 0 and the final boundary is values.length. Empty partitions have equal adjacent boundaries.
  • Row 1 is offsets, of length values.length. offsets[i] is the zero-based destination position of the original element values[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 and O(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

NVIDIA interview experiences

  • NVIDIA DevOps, QA and Infra Intern Interviews: 12 Experiences
  • NVIDIA Ignite Internship OA Experience
  • NVIDIA Software Intern Interview Questions: 9 Experiences
  • NVIDIA Ignite SWE Intern OA Questions: 6 Experiences
All NVIDIA interview questionsSee NVIDIA hiring insights
Saved
class Solution {
    public int[][] hashPartitionOffsets(int[] values, int partitions) {
      // Write your code here.
    }

}
Checking account…