# Problem: Sparse vectors of dot product

## 思路

* 如果都是 sparse vector,那思路就是把每个 vector 都表示成 (index, non-zero value) pairs:

  ```
  A =[0,2,0,2,0,0,3,0,0,4] ==> A={(1,2), (3,2), (6,3), (9,4)}
  ```

  ```
  B=[0,0,0,0,5,0,2,0,0,8]  ==> B={(4,5), (6,2), (9,8)}
  ```
* for each index i, a = val of pair (i, v\_in\_A), b= val of pair (i, v\_in\_B).\
  dot\_product(A,B) = sum\_of ( a \* b )
* 复杂度： `O(m + n)`

## Follow Up

> what if the number of nonzero elements of one vector is 10^10 and the other is 10^2, how can you make it faster?

* 这里的区别就是，一个特别长一个特别短。那么我们就先扫短的，然后用二分法再长的里面找对应的 index。复杂度应该是 `O(m * log n)`