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.
Given sorted non-zero entries of two sparse vectors, return their dot product using two pointers.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([(0,1),(3,2),(10,5)], [(3,4),(10,2)])
Expected Output: 18
Explanation: Prompt example.
Input: ([], [(1,5)])
Expected Output: 0
Explanation: One empty vector.
Input: ([(1,-2),(4,3)], [(1,5),(3,7),(4,-1)])
Expected Output: -13
Explanation: Negative values.
Hints
- Pick a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.