Compute dot product of sparse vectors
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
You need to compute the dot product of two sparse vectors of the same dimension.
Each vector is provided as a list of non-zero entries sorted by index:
- `A = [(i1, v1), (i2, v2), ...]`
- `B = [(j1, w1), (j2, w2), ...]`
Compute:
\[
\sum_{k=0}^{n-1} A[k] \cdot B[k]
\]
### Requirements
- You **may not** use a hash map / dictionary.
- Aim for time proportional to the number of non-zero entries.
### Input/Output
- Input: two arrays/lists of pairs `(index, value)` (indices strictly increasing)
- Output: the integer/long dot product
### Example
- `A = [(0, 1), (3, 2), (10, 5)]`
- `B = [(3, 4), (10, 2)]`
- Dot product = `2*4 + 5*2 = 18`
### Constraints
- Vector dimension `n` can be large (up to 10^9 conceptually)
- Number of non-zeros in each vector up to 2*10^5
Quick Answer: This question evaluates proficiency with sparse data representations and algorithmic efficiency by requiring the dot product to be computed from lists of non-zero entries; it falls under the Coding & Algorithms domain and touches on data structures and numerical operations.