It is Thursday and for a while it was snowing. We received a couple inches of fresh snow. Will see what the weather brings us this weekend. I believe Sunday is going to be the coldest day of this winter so far. We might hit -20F. That said; it appears that the weather forecast changes multiple times a day.
Today my wife was not at home for lunch. I prepare toasts with avocado. Put a dab of butter on a couple slices of ciabatta bread, place them on a cooking sheet and into the oven (set at 400F) they went for about seven minutes. While that was going on, I took out from the freezer a Butter Chicken with Basmati rice tray from Trader Joe’s. As soon as the toast was done I swapped the tray with the chicken. The instructions called for 25 minutes so I consumed the toast with avocado and went back to my office.
While in my office I heard a strange noise. Keep in mind I was alone at home at the time. I went up and checked if someone was at the front or back doors. No luck. I decided to go back to my office for another few minutes. As soon as the timer in my phone went off, I went and took out the plastic tray holding the chicken. Apparently the sound I heard earlier was the ceramic stone we have in the oven breaking into two pieces. We bought the stone years ago and had been working fine. I was surprised for what happened with it.
Earlier today (I woke up shortly before 05:00 AM) I decided to take a look at LeetCode 1570 Dot Product of Two Sparse Vectors.
Given two sparse vectors, compute their dot product. Implement class SparseVector: o SparseVector(nums) Initializes the object with the vector nums o dotProduct(vec) Compute the dot product between the instance of SparseVector and vec A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector. Constraints: o n == nums1.length == nums2.length o 1 <= n <= 10^5 o 0 <= nums1[i], nums2[i] <= 100 Follow up: What if only one of the vectors is sparse?
We are given two arrays of integers. With them we need to convert them to sparse vectors. We then need to produce the dot product of the two vectors.
The requirements sound reasonable. The trick is to select a data structure that would fit the operation at hand which is to produce the dot product.
I will attempt the solution using the Java programming language on a Windows 10 machine using the VSCode IDE. I prefer to have the code and test scaffolding in one place so I can refer to them and easily make changes and test without having to look for the code on-line. That requires us to build a test scaffolding. The simplest way is to write the code on-line using the IDE provided by LeetCode.
class SparseVector {
SparseVector(int[] nums) {
}
// Return the dotProduct of two sparse vectors
public int dotProduct(SparseVector vec) {
}
}
// Your SparseVector object will be instantiated and called as such:
// SparseVector v1 = new SparseVector(nums1);
// SparseVector v2 = new SparseVector(nums2);
// int ans = v1.dotProduct(v2);
Our solution involves the implementation of the SparseVector class. We will need to declare one or more class members and at least populate the constructor and the dotProduct methods.
1,0,0,2,3
0,3,0,4,0
main <<< nums1: [1, 0, 0, 2, 3]
main <<< nums2: [0, 3, 0, 4, 0]
main <<< v1: {0=1, 3=2, 4=3}
main <<< v2: {1=3, 3=4}
main <<< ans: 8
0,1,0,0,0
0,0,0,0,2
main <<< nums1: [0, 1, 0, 0, 0]
main <<< nums2: [0, 0, 0, 0, 2]
main <<< v1: {1=1}
main <<< v2: {4=2}
main <<< ans: 0
0,1,0,0,2,0,0
1,0,0,0,3,0,4
main <<< nums1: [0, 1, 0, 0, 2, 0, 0]
main <<< nums2: [1, 0, 0, 0, 3, 0, 4]
main <<< v1: {1=1, 4=2}
main <<< v2: {0=1, 4=3, 6=4}
main <<< ans: 6
LeetCode provides three test cases. Our test code reads the two input lines. Each contains a set of numbers to be used to populate two arrays. We will need two vectors to perform the dot product operation.
Our test code seems to create and populate the nums1 and nums2 arrays. The arrays are displayed. All seems well so far.
Our test code seems to display the contents of two vectors. We will shortly find out which data structure we chose to represent a vector.
The last line in each set displays the result of the dot product operation. The results seem to be correct. Just traverse the arrays multiplying the corresponding values per index and add the results.
/**
* Test scaffolding
*/
public class DotProductSparseVectors {
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read and populate nums1[] ****
int[] nums1 = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read and populate nums2[] ****
int[] nums2 = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nums1: " + Arrays.toString(nums1));
System.out.println("main <<< nums2: " + Arrays.toString(nums2));
// **** instantiate two vectors ****
SparseVector v1 = new SparseVector(nums1);
SparseVector v2 = new SparseVector(nums2);
// ???? ????
System.out.println("main <<< v1: " + v1.hm.toString());
System.out.println("main <<< v2: " + v2.hm.toString());
// **** dot product of the two vectors ****
System.out.println("main <<< ans: " + v1.dotProduct(v2));
}
}
The code for our test scaffolding is NOT PART OF THE SOLUTION!
We open a buffered reader, read and populate the nums1[] and nums2[] arrays. We then close the buffered reader. We display the arrays to verify that all is well so far.
We then create and populate two vectors. Each vector uses one of the arrays. The contents of the vectors display only the values that are non-zero (we are using sparse vectors).
Finally we generate and display the dot product of the two vectors.
class SparseVector {
// **** class members ****
HashMap<Integer, Integer> hm;
// :::: :::: ::::
}
We will use a HashMap to represent a sparse vector.
/**
* constructor
*/
public SparseVector(int[] nums) {
// **** ****
this.hm = new HashMap<>();
// **** populate hash map ****
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
this.hm.put(i, nums[i]);
}
}
}
We instantiate a hash map and populate it with the non-zero values.
/**
* return the dotProduct of two sparse vectors
*/
public int dotProduct(SparseVector vec) {
// **** initialization ****
int dp = 0;
// **** compute the dot product of the two vectors ****
for (int key : this.hm.keySet()) {
if (vec.hm.containsKey(key) == true) {
dp += this.hm.get(key) * vec.hm.get(key);
}
}
// **** return dot product ****
return dp;
}
This method generated the dot product. We need to multiply the values associated with the same index and add the results. This is accomplished inside of the loop. We then return the result.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 6,328 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com