Dot Product of Two Sparse Vectors

Moderate
0/80
profile
Contributed by
6 upvotes
Asked in companies
FacebookExpedia Group

Problem statement

You are given two sparse vectors ‘vec1’ and ‘vec2’. You have to compute the dot product of these two vectors and print the final answer.

Implement class :

Sparse Vector: Initialize the vector.

dotProduct(vec2): Implement the dot product between vector ‘sparseVector’ and ‘vec2’.
For Example : 
‘N’ = 6, ‘vec1’ = {2, 4, 0, 0, 1, 0}, ‘vec2’ = {0, 0, 3, 0, 5, 0}

Now in this example, the dot product of these two vectors is (2 * 0) + (4 * 0) + (0 * 3) + (0 * 0) + (1 * 5) + (0 * 0) = 5. Hence the final answer is 5.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input format contains ‘T’, denoting the number of test cases. Then each test case follows.

The first line of each test case contains an integer ‘N’, Denoting the number of elements in the array ‘vec1’ and ‘vec2’.

The second line of the test case contains an array of ‘N’ integers denoting the elements of the array ‘vec1’.

The third line of the test case contains an array of ‘N’ integers denoting the elements of array ‘vec2’.
Output Format : 
For each test case, print a single integer “ans” denoting the dot product of the two vectors.

Output for every query will be printed in a separate line.
Note : 
You are not required to print anything explicitly. It has already been taken care of. Just implement the two functions of class ‘sparseVector’.
Constraints : 
1 <= T <= 100
2 <= N <= 10^5
0 <= vec1[i], vec2[i] <= 100

Time Limit: 1 sec
Sample Input 1 :
2
3
1 0 1
0 1 0
2
6 0
6 0
Sample Output 1 :
0
36
Explanation For Sample Output 1 :
In the first test case, the dot product of these two vectors is (1 * 0) + (0 * 1) + (1 * 0) = 0. Hence the final answer is 0.

In the second test case, the dot product of these two vectors is (6 * 6) + (0 * 0) = 36. Hence the final answer is 36.
Sample Input 2 :
2
5
0 1 0 0 1
0 4 1 0 11
5  
1 2 0 0 0
0 44 0 0 0
Sample Output 2 :
15
88
Hint

Map all the elements of both the vectors and compute the answer for each index

Approaches (2)
Hash Map

We will declare a hash map ‘vecToMap’ and hash all the values to the hash map. Now in the constructor function, we will update the hash map and in the dot product function, we will calculate the dot product of all the elements which have the same index.

 

The steps are as follows:

‘SparseVector(vec1)’:

  1. Iterate through the whole ‘vec1’ and check for each element in the ‘vec1’ if the value is zero or not.
  2. If the value is non-zero, then update this value in the hash map.

 

‘dotProduct(sparseVector &vec)’:

  1. Take an integer result for storing the final answer.
  2. Take a iterator for map and iterate through the whole ‘vecToMap’:
    • Check for each position of the current index, if there is any value present in the ‘vecToMap’ of ‘vec’:
      • If true, Update ‘result’ equal to ‘result’ + the value at the current index of vector 1 * value at the current index of vector 2.
  3. Return ‘result’.
Time Complexity

O(N). Where N is the total number of elements in the vector.


Since we are iterating through the vector in a linear manner using one for loop for hashing all the elements.

Hence, the time complexity is O(N).

Space Complexity

O( K ), Where K is the number of elements that are non-zero.


Since we are hashing all the non-zero elements.

Hence the space complexity is O( K ).

Code Solution
(100% EXP penalty)
Dot Product of Two Sparse Vectors
Full screen
Console