Write a function that calculates the dot product of two vectors. 96% of vector components are zero. What is a good data structure for v1, v2 so that you can calculate the dot product fast? You don’t have to worry about setup costs.
v1 = [x1, x2, x3, ..., xN]
v2 = [y1, y2, y3, ..., yN]
v1 · v2 = x1y1 + x2y2 + ... + xNyN
This problem is about representing sparse vectors efficiently. Since 96% of the entries are zero, the best choice is to store only non-zero values, such as a hash map from index to value or a compressed list of index-value pairs. To compute the dot product quickly, iterate over the smaller set of non-zero entries and look up matching indices in the other vector in O(1) average time. This avoids scanning all N positions and makes the computation proportional to the number of non-zero elements rather than the full vector length.
