Last Updated: 12 Oct, 2021
Dot Product of Two Sparse Vectors
Moderate
Asked in companies
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.
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
Approaches
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)’:
- Iterate through the whole ‘vec1’ and check for each element in the ‘vec1’ if the value is zero or not.
- If the value is non-zero, then update this value in the hash map.
‘dotProduct(sparseVector &vec)’:
- Take an integer result for storing the final answer.
- 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.
- Check for each position of the current index, if there is any value present in the ‘vecToMap’ of ‘vec’:
- Return ‘result’.
We will declare a vector of pairs ‘vecToPair’ where each pair will have the first element as an index and the second element as value at that index. Now in the constructor function, we will update the index-value pair vector 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)’:
- Iterate through the whole ‘vec1’ and check for each element in the ‘vec1’ if the value is zero or not.
- If the value is non-zero, then update this value in the index-value pair.
‘dotProduct(sparseVector &vec)’:
- Take three integers i, j, and result denoting the iterator for the first vector, the iterator for the second vector, and the for storing the final answer, respectively.
- Take a while loop till either i or j reaches the last element in their respective index-value pair:
- Check if the current index of the first vector is less than the current index at the second vector:
- Increment ‘i’ by 1.
- Check if the current index of the first vector is greater than the current index at the second vector:
- Increment ‘j’ by 1.
- Check if the current index of the first vector is equal to the current index at the second vector:
- Update ‘result’ equal to ‘result’ + the value at the current index of vector 1 * value at the current index of vector 2.
- Increment ‘i’ by 1.
- Increment ‘j’ by 1.
- Check if the current index of the first vector is less than the current index at the second vector:
- Return ‘result’.