Katkat
Back

Dot Product of Two Vectors (Dense, then Sparse)

WhatnotSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests data structure design and algorithmic optimization for sparse vector operations, transitioning from standard array traversal to pointer-based or hash-based solutions that scale with non-zero elements.

Problem Statement

Given two sparse vectors, compute their dot product efficiently.

The dot product of two vectors v1 = [a1, a2, ..., an] and v2 = [b1, b2, ..., bn] is defined as a1 * b1 + a2 * b2 + ... + an * bn.

A vector is considered sparse when most of its elements are zero. An O(n) linear scan over the dense vectors is inefficient when the dimension n is large (e.g., 10^7) but the count of non-zero entries is small.

Implement the SparseVector class:

  • SparseVector(nums: list[int]): Initializes the object with the vector nums.
  • dot_product(vec: 'SparseVector') -> int: Returns the dot product of self and vec.

Your solution should store data efficiently and perform dot product calculations proportional to the number of non-zero elements, rather than the total length of the vector.

Interface

class SparseVector:
    def __init__(self, nums: list[int]):
        pass

    def dot_product(self, vec: 'SparseVector') -> int:
        pass

Examples

Example 1

Input:
nums1 = [1, 0, 0, 2, 3]
nums2 = [0, 3, 0, 4, 0]

v1 = SparseVector(nums1)
v2 = SparseVector(nums2)
result = v1.dot_product(v2)

Output: 8
Explanation: v1.dot_product(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8.

Example 2

Input:
nums1 = [0, 1, 0, 0, 0]
nums2 = [0, 0, 0, 0, 2]

v1 = SparseVector(nums1)
v2 = SparseVector(nums2)
result = v1.dot_product(v2)

Output: 0
Explanation: Neither vector shares a non-zero index, so the dot product is 0.

Constraints

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^7
  • 0 <= nums1[i], nums2[i] <= 10^4
  • The number of non-zero elements in each vector is at most 10^5.

Edge Cases to Consider

  • One or both vectors contain all zeros.
  • Non-zero indices in the two vectors are completely disjoint.
  • One vector has significantly fewer non-zero entries than the other.

Hints

Hint 1

Store only the non-zero values along with their corresponding indices instead of keeping the entire array.

Hint 2

If you store index-value pairs in sorted order by index, you can compute the product in O(k1 + k2) time using two pointers.

Hint 3

If one vector is dramatically sparser than the other (k1 << k2), iterating through the sparser vector and performing binary search or hash-lookups on the denser one may be faster.

Follow-up questions

  • What if one vector has 10 non-zero elements and the other has 100,000 non-zero elements? How can you optimize the dot product computation?
  • What are the memory and cache-locality trade-offs between an array of (index, value) tuples versus a hash map `{index: value}`?
  • How would you adapt your design if vectors are too large to fit in memory on a single machine?