Katkat
Back

Implement sparse vector dot product

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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:

  1. Specify your data representation and explain how it handles vectors with different sparsity patterns.
  2. Analyze the time and space complexity of both constructing the sparse vector and computing the dot product.