关于fb高频题1570: Dot Product of Two Sparse Vectors的问题

这道题评论里基本都说过被面过，很多人也分享了经验说第一个想到的是使用hashmap但是面试官要求用其他方法因为不够efficient但是看解法的话map好像是最有效率的了？因为用tuple的话也是O(l1+l2)而map就是Ol1，看大家讨论从硬件角度讲用个基础的Array最好，但是感觉面试官也不会期待这个答案？

再说follow up就是说把一个sparse vector换成一个很短的不sparse array如何能更有效率的改答案，我看很多人都说binary search，但是我没太明白是在哪条array上search呢？我理解的话感觉map的方法还是最有效率的啊？是我理解出了错误吗？

想看看大家的看法或者有没有当事人现身说法呢？谢谢！

两个 array of array？空间换时间
第一个先行后列 [[r1_a, [c1_a
, v1_a], [c2_a, v2_a],...],...]
r1_a， c1_a 是第一个non zero elem，值是v1_a

第二个先列后行  [[c1_b, [r1_b, v1_b], [r2_b, v2_b],...]]，意义同上。

Dot product 的时候 新矩阵第一个元素位置（r1_a, c1_b) ，值是两个array 一起遍历 ci_a== ri_b 的时候相乘，不然就是0.

complexity虽然也是O(n), 是非零元素数。但是是sequential memory access，即使不算hashing，miss， collision也比unoreder_map的random memory access快百倍。

补充内容 (2022-02-09 12:17 +08:00):
如果需要access elem可以用bisect。如果只是dot prod遍历就可以。

补充内容 (2022-02-09 12:18 +08:00):
求米刷包裹