Conduct Dot Product of two large sparse Vectors
/**
* http://yuanhsh.iteye.com/blog/2186422
* What is a memory-efficient way to store a vector of integers?
* Follow-up question: using your proposed data structure, find an algorithm with constant memory usage
* to calculate the dot product of two vectors.
* 有两个很大的稀疏向量，问怎么存储和算他们的dot product. 只存储非零元素和他的index，
* 如果压缩后的向量大小为m,n, O(m+n)和O(mlogn)方法都不难想到。他问有没有更好，
* 提示divide and conquer，我就说先取一个向量的中间元素，然后搜索他在另一个向量中对应元素的位置，
* 这样就把两个矩阵都分别分为两半。他问复杂度，我说我要算一下才知道，然后他说他也不知道，不过平均情况应该比前面的好。
*/
/**
* 一开始说连个hashmap，小哥说hashmap会浪费掉多余空间，我说那如果一个特别大的话就扫小一点的那个array，然后在特别大的array中用binary search，
* 他说写代码。写完代码接着说，那如果差不多大，我说那就两个指针按照merge sort那么扫。然后我觉得基本都行了，他最后说那有没有O(Math.min(m, n))的方法。
* 我鼓捣半天，最后说了个那就输入直接是一个tuple，第一个elem是位置（这个位置在两个array中必须都不是0），然后扫一遍就行了。其实我感觉他的意思是再用HashMap。
* 不过他忘了之前和我说太浪费空间了。。。
*/
/**
* 算松散向量的点乘，原题有一道算松散矩阵，完全的不同。最后要求是写一个O(n+m)的和一个O(n * log m)的算法，从自己定数据结构开始，面试官看代码真的超仔细....
* for(int idx1=0, idx2=0; idx1<size1 && idx2<size2;) { if(xxx) idx1++ else idx2++ }，类似这样的代码，还要求优化成
* for(int idx1=1, idx=0; ; ) { if(xxx) { idx1++; if(idx1 > size1) break; } else { idx2++; if( idx2 > size2) break; }
*/
basic dot product, A={a1, a2, a3,...}, B={b1, b2, b3,...} dot_product = a1 * b1 + a2 * b2 + a3 * b3 ＋ ...
Solution 1: Brute Force (n); O(1)
public int dotProduct(int[] a, int[] b) {
int res = 0;
for (int i = 0; i < a.length; i++)
res += a[i] * b[i];
return res;
}
Follow Up:
1.If the array is very sparse, calculate the dot product of two very large arrays with many 0 elements. Be as efficient as possible.
What is a memory-efficient way to store a vector of integers?
A={a1, ...., a300, ...., a5000} B={...., b100, ..., b300, ..., b1000, ...} 例子: A=[[1, a1], [300, a300], [5000, a5000]] B=[[100, b100], [300, b300], [1000, b1000]] 返回 a300 * b300
A,B化简成list of tuples，只存储非零元素和他的index，然后two pointer扫就行，还可以优化成binary search
Two Pointers O(m+n) O(min(m,n)); O(1)
时间复杂度要注意：i和j不是同时动的，所以时间应该是+，而不是min。
最坏情况下，A和B最后一个tuple的index相等，就必须要遍历完两个数组。
public int dotProduct(int[][] A, int[][] B) {
int result = 0;
int i = 0;
int j = 0;
while (i < A.length && j < B.length) {
if (A[i][0] == B[j][0]) { //二元组中第一个元素是index，第二个元素是值。
result += A[i][1] * B[j][1];
i++;
j++;
}
else if (A[i][0] > B[j][0])
i++;
else
j++;
}
return result;
}
最后问用改用map存好不好（我用的list存），我觉得时间复杂度一样啊，然后他就笑了，说了怎么不好，说了一通，我也没听明白。
可以以第一个map为基准 遍历每个key 然后看第二个map里是否有相同的key 这样的话还是linear time
这样就不从最低索引开始算，一开始想偏了，以为只能从最低索引开始算，实际上不一定。思维江化！
2.如果length(B) >>> length(A)，即B非常长，怎么做能减少时间复杂度。
对A里面的每个数，用binary search找B中相对应的值，这样时间复杂度是O(mlogn) (m = len(A), n =len(B))
// 优化：Binary Search on array B O(m log n); O(1)
public int docProduct2(int[][] A, int[][] B) {
int result = 0;
for (int[] pair : A) { //O(m)
int index = pair[0];
int indexB = binarySearch(B, index); //O(log n)
if (indexB != -1)
result += pair[1] * B[indexB][1];
}
return result;
}
public int binarySearch(int[][] B, int index) { //九章模板
int start = 0, end = B.length - 1;
while (start + 1 < end) {
int mid = (start + end) / 2;
if (B[mid][0] >= index) //注意>=；原来写的是1，应该是0，第一个元素是index
end = mid;
else
start = mid;
}
if (B[start][0] == index)
return start;
else if (B[end][0] == index)
return end;
return -1;
}
3.two inputs are sorted by index0, have same size, sometimes dense, sometimes sparse;
又问如果两个数组一样长，且一会sparse一会dense怎么办。他说你可以在two pointer的扫描中内置一个切换二分搜索的机制。看差值我说过，设计个反馈我说过，他说不好。他期待的解答是，two pointers找到下个位置需要m次比较，而直接二分搜需要log(n)次比较。那么在你用two pointers方法移动log(n)次以后，就可以果断切换成二分搜索模式了。
two pointes + binary search
public int sparseVectorMultiplication(ArrayList<ArrayList<Integer>> a, ArrayList<ArrayList<Integer>> b) {
if (a == null || b == null || a.size() == 0 || b.size() == 0) {
return 0;
}
int m = a.size();
int n = b.size();
int res = 0;
int i = 0;
int j = 0;
int countA = 0;
int countB = 0;
while (i < m && j < n) {
ArrayList<Integer> pairA = a.get(i);
ArrayList<Integer> pairB = b.get(j);
if (pairA.get(0) < pairB.get(0)) {
i++;
countA++;
countB = 0;
if (countA > Math.log(m)) {
i = search(a, i, m, pairB.get(0));
countA = 0;
}
} else if (pairA.get(0) > pairB.get(0)) {
j++;
countB++;
countA = 0;
if (countB > Math.log(n)) {
j = search(b, j, n, pairA.get(0));
countB = 0;
}
} else {
res += pairA.get(1) * pairB.get(1);
i++;
j++;
countA = 0;
countB = 0;
}
}
}
private int search(ArrayList<ArrayList<Integer>> array, int start, int end, int target) {
while (start + 1 < end) {
int mid = start + (end - start) / 2;
ArrayList<Integer> pair = array.get(mid);
if (pair.get(0) == target) {
return mid;
} else if (pair.get(0) < target) {
start = mid;
} else {
end = mid;
}
}
if (array.get(end).get(0) == target) {
return end;
}
return start;
}
- 面试官先问每个vector很大，不能在内存中存下怎么办，我说只需存下非零元素和他们的下标就行，然后问面试官是否可用预处理后的这两个vector非零元素的index和value作为输入，面试官同意后写完O(M*N)的代码(输入未排序，只能一个个找)，MN分别是两个vector长度。
- 又问这两个输入如果是根据下标排序好的怎么办，是否可以同时利用两个输入都是排序好这一个特性，最后写出了O(M + N)的双指针方法，每次移动pair里index0较小的指针，如果相等则进行计算，再移动两个指针。
- 又问如果一个向量比另一个长很多怎么办，我说可以遍历长度短的那一个，然后用二分搜索的方法在另一个vector中找index相同的那个元素，相乘加入到结果中，这样的话复杂度就是O(M*logN)。
- 又问如果两个数组一样长，且一会sparse一会dense怎么办。他说你可以在two pointer的扫描中内置一个切换二分搜索的机制。看差值我说过，设计个反馈我说过，他说不好。他期待的解答是，two pointers找到下个位置需要m次比较，而直接二分搜需要log(n)次比较。那么在你用two pointers方法移动log(n)次以后，就可以果断切换成二分搜索模式了。
- Binary search如果找到了一个元素index，那就用这次的index作为下次binary search的开始。可以节约掉之前的东西，不用search了。然后问，如果找不到呢，如何优化。说如果找不到，也返回上次search结束的index，然后下次接着search。就是上一次找到了，就用这个index继续找这次的；如果找不到，也有一个ending index，就用那个index当starting index。比如[1, 89，100]，去找90；如果不存在，那么binary search的ending index应该是89，所以下次就从那个index开始。如果找不到，会返回要插入的位置index + 1，index是要插入的位置，我写的就是返回要插入的index的。但是不管返回89还是100的index都无所谓，反正只差一个，对performance没有明显影响的。
(3) 如果把一维向量扩展到二维的矩阵
(4)如果要存数组的话就可以用公式把坐标换成一维的 r,c，变成 r*列数 + c，变回来的话用i/列数, i%列数