How should I practice Sparse Vector Dot Product with GPU Follow-Up?

Start by reading the full statement, solve the visible examples, then compare the pattern against related NVIDIA phone screen problems in FastPrep.

Is Sparse Vector Dot Product with GPU Follow-Up associated with NVIDIA?

FastPrep tags this as a NVIDIA phone screen coding practice problem when the problem catalog has that company and stage context.

Sparse Vector Dot Product with GPU Follow-Up

NVIDIA● EasyFULLTIMEPHONE SCREEN

Learn

Problem statement

Two integer vectors of the same length are represented by their nonzero entries. Each row [index, value] of first or second stores one value at a zero-based coordinate. In each operand, indices are unique, strictly increasing and in range. Every omitted coordinate has value 0.

For this exercise, multiplication means the scalar dot product: sum firstValue(i) * secondValue(i) over coordinates 0 through length - 1. Return that sum as a signed 64-bit integer, using 64-bit arithmetic for products and accumulation. An empty support or a zero-length vector gives 0.

Work directly with the stored entries. The dimension may be much larger than either support, so a dense length-sized array is unnecessary.

GPU follow-up discussion

Discuss how to match nonzero indices in parallel, combine the resulting products safely, and decide whether GPU execution is worthwhile for the workload. This is a discussion follow-up; the submitted function returns the scalar dot product.

What the interview report shared

The coding prompt asked for sparse vector multiplication.
The interviewer also asked how the problem would run on a GPU and supplied hints; the report does not disclose those hints.

Function

sparseDotProduct(length: int, first: int[][], second: int[][]) → long

Examples

Example 1

length = 10first = [[0,2],[3,-4],[9,5]]second = [[1,7],[3,6],[9,-2]]return = -34

Only indices 3 and 9 occur in both operands. Their contributions are -4 * 6 = -24 and 5 * -2 = -10, giving -34.

Example 2

length = 1000000000first = [[999999999,1000000]]second = [[999999999,1000000]]return = 1000000000000

The final valid index contributes 10^6 * 10^6 = 10^12. The large dimension does not require allocating a dense vector.

Example 3

length = 0first = []second = []return = 0

There are no coordinates, so the empty sum is 0.

Constraints

0 <= length <= 10^9.
0 <= first.length, second.length <= min(256, length).
Every row has exactly two integers: [index, value].
Indices within each operand are strictly increasing and satisfy 0 <= index < length.
Every stored value is nonzero and lies in [-10^6, 10^6].
Inputs satisfy these rules; duplicate indices and malformed rows are outside the accepted domain.
Use signed 64-bit products and accumulation; at most 256 * 10^12 bounds the magnitude of any partial sum.