Suppose we have very large sparse vectors, which contains a lot of zeros and double .
- find a data structure to store them
- get the dot product of them
@nullpointerP Welcome to the new Discuss!
Although your description mentions it's dot product, matrix multiplication is just a series of dot products. I think it's very similar problems.
Could you please confirm?
@1337c0d3r hello, I think they are slightly different.
In this case, we first have to store the sparse vector using hash map.
for example [3,0,0,5,6] -> (0,3) (3,5) (4,6) The key is each element's position and the value is the number.
Then we have two hash tables, and we have to iterate through them to calculate the dot product
@nullpointerP I think that your toughts are in the right direction. Can you implement them? Thank you
@nullpointerP Why not store them in just a list of tuples for each vector? And then iterate through both list using two pointers.
@nullpointerP Ohh I see. Updating the data structure will be problematic with a list. Hash table provides O(1) update.
@nullpointerP Are you required to modify the sparse vector frequently? Or just given two sparse vectors, compute their dot product once and return the answer?
@1337c0d3r Yes, in terms of updating frequently, list is not a good idea. But the interviewer didn't mention that. So I think list with tuples is ok.
We represent the vectors as Hash Tables. We sort the them based on the tables sizes (o(nlogn) - where n is the number of tables).
we pick the smallest table, and traverse it. for each of its elements we look for it in all the tables. If it doesn't exist in one of them, we skip and move to the next element. Otherwise we multiply them and sum them up. run time: o(E*N) where E is the number of elements in the smallest table.
@nullpointerP If read/load array is costly, we can do this:
@galster @wangxinbo Hi, I'm confused about dot product of many vectors. From my understanding, we can compute the dot product of two vectors and get a result. The result is a number not a vector. What does dot product of many vectors mean?