Katkat
Back

Compute the Dot Product of Sparse Vectors

MetaSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

Compute the dot product of two sparse vectors stored as sorted index-value pairs without expanding them. A two-pointer traversal should visit only nonzero entries, multiply matching indices, and accumulate safely in a wide integer type.

Problem

Each sparse vector is represented as a list of [index, value] pairs sorted by strictly increasing index; omitted positions have value zero. Return the dot product of two vectors without expanding either vector to dense form.

Constraints & Assumptions

  • Each vector has at most 200,000 nonzero entries.
  • Indices are nonnegative 32-bit integers and are unique within a vector.
  • Every stored value is an integer in [-100,000, 100,000].
  • Use signed 64-bit products and accumulation in Java and C++; the result magnitude is at most 2,000,000,000,000,000, below 2^53, so Python integers and JavaScript numbers are exact as well.
  • The two logical vectors have the same dimension, which need not be materialized.

Clarifications

  • Pairs are already sorted, so sorting is not part of the task.
  • Only matching indices contribute to the result.
  • The function should also work when one vector is far sparser than the other.

Examples

a = [[0, 1], [3, 2], [10, -4]]
b = [[1, 7], [3, 5], [10, 2]]
output = 2*5 + (-4)*2 = 2

Hints

Hints

Hint 1

Advance by index: Compare the current indices and move past the smaller one when they differ.

Hint 2

Consider asymmetric sparsity: A binary-search variant can be useful, but justify it against a linear two-pointer scan.