Meta VO 面试真题解析：稀疏向量点积（Sparse Vector Dot Product）

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

这道题的核心是“稀疏向量”的表示与优化。由于 96% 的元素都是 0，最适合用只保存非零项的数据结构来存储向量，例如用哈希表记录索引到数值的映射，或者用“索引 + 值”的压缩列表。计算点积时只需要遍历非零元素更少的一方，并在另一方中快速查找同索引元素，这样可以把原本 O(n) 的逐位相乘，优化到接近 O(k)（k 为非零元素个数）。如果两边都稀疏，通常先让较小的非零集合做外层遍历，再做哈希查找，兼顾时间和空间效率。