Dot Product of Two Sparse Vectors

Problem

Design a class for sparse vectors and compute the dot product of two of them efficiently.

Example

a = [1,0,0,2,3], b = [0,3,0,4,0]
Output: 8

Constraints

• n up to 10^5, mostly zeros

Discussion

Store only non-zero (index, value) pairs. Meta follow-up: what if one vector is dense and the other extremely sparse?