Dot Product of Two Sparse Vectors

The "Dot Product of Two Sparse Vectors" is a Meta (Facebook) interview problem focusing on efficient computation for sparse data using arrays, hash tables, two pointers, or design patterns.[1][3][5]

Problem Statement

Implement a SparseVector class to represent a sparse vector (mostly zeros) by storing only non-zero index-value pairs, typically in a hash map. The class must support:

• SparseVector(nums): Constructor that initializes from array nums, storing only non-zero elements (e.g., as {index: value} dictionary).
• dotProduct(vec): Computes the dot product with another SparseVector vec by summing products of matching non-zero indices: $$\sum a_i \times b_i$$ where both $$a_i \neq 0$$ and $$b_i \neq 0$$.[3][5]

Example

Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0] v1 = SparseVector(nums1) # {0:1, 3:2, 4:3} v2 = SparseVector(nums2) # {1:3, 3:4} Output: v1.dotProduct(v2) = 8 Explanation: 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8 This matches LeetCode 1570, a locked Meta-favored problem.[2][5]

Constraints

• $$1 \leq n \leq 10^5$$, where $$n =$$ length of nums.
• $$-10^9 \leq$$ nums[i] $$\leq 10^9$$.
• Vectors have equal length.
• Number of non-zero elements is small (sparse), up to $$10^5$$ total.[5][3]