How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Implement sparse vector dot product

Quick Overview

Meta's sparse vector dot product question asks you to design a SparseVector class that stores only non-zero entries and computes dot products in time proportional to the number of non-zeros rather than the full vector length. It tests sparse data representation, two-pointer vs. hash-map trade-offs, and time/space complexity analysis.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

##### Question Design a `SparseVector` class for vectors of integers in which most entries are zero, and support an efficient dot product between two such vectors. The length `n` of the vector can be large (e.g., up to `10^5`), but only a small number of positions hold non-zero values. Each vector is initially given as a dense integer array `nums` of length `n`. Implement the class with: 1. A constructor `SparseVector(int[] nums)` that stores the vector in a space-efficient way (it should not require `O(n)` space when the vector is sparse). 2. A method `int dotProduct(SparseVector other)` that returns the dot product of the current vector with another `SparseVector`. The dot product of two vectors `a` and `b` of length `n` is: `a · b = a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1]` The `dotProduct` should be efficient when the vectors are sparse — faster than `O(n)` over all positions. Additionally: 3. Specify your data representation and explain how it handles vectors with different sparsity patterns. 4. Analyze the time and space complexity of both constructing the sparse vector and computing the dot product.

Quick Answer: Meta's sparse vector dot product question asks you to design a SparseVector class that stores only non-zero entries and computes dot products in time proportional to the number of non-zeros rather than the full vector length. It tests sparse data representation, two-pointer vs. hash-map trade-offs, and time/space complexity analysis.

Given two vectors of integers `nums1` and `nums2`, each presented as a dense array of length `n` in which most entries are zero, compute their dot product efficiently. The dot product of two vectors `a` and `b` of length `n` is: `a · b = a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1]` The length `n` may be large (e.g., up to `10^5`), but only a small number of positions hold non-zero values. Store each vector in a space-efficient sparse representation (do not keep `O(n)` storage when the vector is sparse) and make the dot product faster than scanning all `n` positions. Implement `dotProduct(nums1, nums2)` which returns the dot product. A strong solution builds a `SparseVector` representation from each input that stores only the non-zero `(index, value)` pairs, then computes the product in time proportional to the number of non-zeros rather than `n`. Return the integer dot product.

Constraints

1 <= n <= 10^5 (n is the common length of nums1 and nums2)
nums1.length == nums2.length == n
-100 <= nums1[i], nums2[i] <= 100
Most entries are zero (the vectors are sparse)

Examples

Input: ([1,0,0,2,3], [0,3,0,4,0])

Expected Output: 8

Explanation: Overlapping non-zeros only at index 3: 2*4 = 8. Index 0 (1 vs 0) and index 4 (3 vs 0) contribute nothing.

Input: ([0,1,0,0,0], [0,0,0,0,2])

Expected Output: 0

Explanation: The two non-zeros sit at different indices (1 and 4), so there is no overlap and the dot product is 0.

Input: ([0,1,0,0,2,0,0], [1,0,0,0,3,0,4])

Expected Output: 6

Explanation: Only index 4 overlaps: 2*3 = 6. The non-zeros at indices 1, 0, and 6 have no counterpart.

Input: ([], [])

Expected Output: 0

Explanation: Edge case: empty vectors have no entries, so the dot product is 0.

Input: ([0,0,0], [0,0,0])

Expected Output: 0

Explanation: Edge case: all-zero vectors produce empty sparse representations and a dot product of 0.

Input: ([5], [3])

Expected Output: 15

Explanation: Single shared non-zero at index 0: 5*3 = 15.

Input: ([-1,0,2,0,-3], [4,0,-5,0,6])

Expected Output: -32

Explanation: Negatives: index 0 gives -1*4 = -4, index 2 gives 2*-5 = -10, index 4 gives -3*6 = -18; total -32.

Input: ([1,2,3], [4,5,6])

Expected Output: 32

Explanation: Fully dense vectors: 1*4 + 2*5 + 3*6 = 4 + 10 + 18 = 32. The sparse approach still works when nothing is zero.

Hints

Don't store the zeros. Keep only the (index, value) pairs where the value is non-zero, so storage is proportional to the number of non-zeros, not n.
Because the dense array is already in index order, the list of non-zero (index, value) pairs comes out sorted by index for free.
With both pair lists sorted by index, run a two-pointer merge: when both pointers are at the same index, multiply and accumulate; otherwise advance the pointer at the smaller index. This costs O(L + R).
Alternative: store one vector as a hash map {index: value} and iterate over the smaller vector's non-zeros, looking each index up in the larger map for O(min(L, R)) average time — this handles a sparse-vs-dense mix well.

Quick Overview