Compute the Dot Product of Sparse Vectors
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
## Problem
Each sparse vector is represented as a list of `[index, value]` pairs sorted
by strictly increasing index; omitted positions have value zero. Return the dot
product of two vectors without expanding either vector to dense form.
### Constraints & Assumptions
- Each vector has at most 200,000 nonzero entries.
- Indices are nonnegative 32-bit integers and are unique within a vector.
- Every stored value is an integer in `[-100,000, 100,000]`.
- Use signed 64-bit products and accumulation in Java and C++; the result magnitude is at most `2,000,000,000,000,000`, below `2^53`, so Python integers and JavaScript numbers are exact as well.
- The two logical vectors have the same dimension, which need not be materialized.
### Clarifications
- Pairs are already sorted, so sorting is not part of the task.
- Only matching indices contribute to the result.
- The function should also work when one vector is far sparser than the other.
### Examples
```text
a = [[0, 1], [3, 2], [10, -4]]
b = [[1, 7], [3, 5], [10, 2]]
output = 2*5 + (-4)*2 = 2
```
### Hints
```hint Advance by index
Compare the current indices and move past the smaller one when they differ.
```
```hint Consider asymmetric sparsity
A binary-search variant can be useful, but justify it against a linear two-pointer scan.
```
Overview: Compute the dot product of two sparse vectors stored as sorted index-value pairs without expanding them. A two-pointer traversal should visit only nonzero entries, multiply matching indices, and accumulate safely in a wide integer type.
Read the full Meta Software Engineer interview experience this question came from
Each sparse vector is a list of [index, value] pairs sorted by strictly increasing nonnegative index; omitted positions have value zero. Return the exact dot product without expanding either vector into a dense representation. Only equal indices contribute, and the logical vectors have the same dimension even though that dimension is not materialized.
Constraints
- Each vector has at most 200000 stored entries.
- Indices are unique within a vector, strictly increasing, and nonnegative signed 32-bit integers.
- Every stored value is an integer in [-100000, 100000].
- The result magnitude is at most 2000000000000000 and requires signed 64-bit products and accumulation in Java and C++.
- Both logical vectors have the same dimension, which need not be materialized.
Examples
Input: ([[0, 1], [3, 2], [10, -4]], [[1, 7], [3, 5], [10, 2]])
Expected Output: 2
Explanation: This is the source example; only indices 3 and 10 contribute.
Input: ([], [])
Expected Output: 0
Explanation: Two empty sparse vectors have dot product zero.
Hints
- Compare the current indices in both sorted pair lists.
- When indices differ, the smaller current index cannot match anything later on the other side.