DOT PRODUCT OF TWO SPARSE VECTORS - 3 SOLUTIONS EXPLAINED [PYTHON]

In this video we'll be solving Leetcode Problem 1570: Dot Product of Two Sparse Vectors. This is a popular Facebook interview question and there are 3 possible solutions, though only 1 should actually be used in an interview.
We'll walk through the question, go over how to compute a dot product, each of the three solutions, and weigh the pros/cons and ultimately code up our best possible solution.

[@aaron10k]

grinding these for my meta interview they're so good

[@Rhythm31]

did you give it? I have my final rounds in a week

[@annlaosun6260]

@@Rhythm31 did you get it? i have my interview in a couple weeks

[@TheSmashten]

How did it go? What questions were you asked

[@SuperAce780]

this is the best channel ever. helped me ace my meta interviews and get a full time offer! thank you

[@crackfaang]

Very happy to hear that mate! Congratulations on the offer and hopefully you got a big sign on bonus and large RSU grant :)

[@landocodes]

The "rambling" at the end was super helpful. This problem seemed way too easy so I figured I was doing it wrong, and ofc I was. Great explanation as always.

[@rachnaramkumar]

Got this question for my Meta interview today! Thank you so much for your videos! My interviewer ended up accepting my Tuple Solution! Looking forward to more videos :) Keep up the amazing work!

[@crackfaang]

Happy this was able to help you! Hopefully you passed the on-site and will receive an offer

[@sunnygoswami5358]

Congrats on getting the solution accepted! What is the position you're interviewing for? Thanks!

[@3rd_iimpact]

Did you get the follow-up question? If so, how did you explain?

[@roywastaken]

GOAT channel bro, come back!!!

[@janarboke4005]

I really love how you walk through the example in the end, helped me understand the problem itself. Great video!

[@3rd_iimpact]

Good stuff. Could you please explain more into detail why 'j' is moved up instead of 'i' when i_idx > j_idx (line 20)? Also, could you please go more in detail about the follow up question and using the binary search?

[@pahul79]

hey man i just discovered your channel. I have to say, im very surprised you havent blown up. even though the view count is low, no disrespect intended, i have to so your videos are top notch. Thank you very much for putting so much effort into these videos to help the public as myself.

[@davidmwangi4312]

Super helpful as I prepare for my upcoming Meta Interview

[@segue97]

love the honesty to know he was handwaving. this guy is either dissing himself, leetcode or subscribers 😂

[@boyun7532]

Thank you so much for the video! can you elaborate a bit more on what a bad hash map function may look like? just looking for reasoning behind using tuple over hash in case getting asked

[@crackfaang]

Thanks the kind words! I suppose this is more of a theoretical question as all languages are going to have optimized hash functions but one that is suboptimal would be one which has a lot of collisions when trying to hash values

[@l.k3072]

One of the best explanation channel

[@crackfaang]

Thanks for the kind words! Make sure to subscribe to not miss future videos

[@adityadn95]

Do we really need binary search approach for the follow up? Can we not iterate over the sparse vector and directly access the corresponding indices in the dense vector?

[@solar679]

God bless you !!!!!!!!!!!!!!

[@crackfaang]

Make sure to subscribe for more content and let me know if there’s any videos you’d like me to make!

[@solar679]

​@@crackfaang thanks for the response. I was a little bit confused on why the first implementation was inefficient. Can you please explain again?

[@rishab9293]

@Cracking FAANG Thank you! I was wondering if we could mention in the follow-up that I will perform a binary search on non-sparse vectors to find the non-zero index from the sparse vector. This will translate our dotProduct function's time complexity to 𝑂 ( min ⁡ ( 𝑚 , 𝑛 ) ⋅ log ⁡ ( max ⁡ ( 𝑚 , 𝑛 ) ) ) O(min(m,n)⋅log(max(m,n))) and space complexity to 𝑂 ( 1 ) O(1). Do you think we are expected to implement the follow-up question or just verbal conversations?

[@ayoubalem865]

Keep Going ! By time you will gain more followers you are doing a great work !

[@Rppiano]

3 solutions: 1. Brute force 2. HashMap 3. Two pointers + HashMap

[@dARKf3n1Xx]

It's amazing how at 2x every coding video still makes sense XD

[@awa8766]

Thanks for that, however, I have a quick question regarding the syntax. I don't understand how at lines 16-18, initializing with self.nums and vec.nums is creating a difference. I thought both cases would be vec.nums since the dotproduct function is receiving an input that is passed to the __init__, preprocessed, then the operations from lines 16 onwards proceed. Initially, I thought of writing it as follows: while i < len(self.nums) and j < len(self.nums): i_idx, i_num = self.nums[i] j_idx, j_num = self.nums[j] but obviously, I'm getting duplicate numbers so it doesn't work. I'm not too sure how the way you wrote it is generating different results. Thanks in advance!

[@crackfaang]

The “nums” part is an attribute on the SparseVector class. Basically the question passes you another SparseVector class to do the dot product with. So self.nums refers to the current SparseVector and it’s numbers and the vec.nums refers to the other sparse vector class. If you look at the function signature for the dot product function you’ll see that you get passed in the other vector

[@dnm9931]

Thanks a lot man

[@mohammadkareem1187]

Thanks for the great video, however the index pair solution might be acceptable in the interview, but in case one parse vetoer is extremely large, this is not going to be efficient, instead, one need to find the matching index in the long vector via binary search, which will be the best solution in terms of time complexity. You can find some solution examples in the discussion part of question in Leetcode :)

[@crackfaang]

It’s not that simple. Who said time complexity is all we want to optimize for? What if we don’t care about time and space is the most important factor? This is one of those annoying questions where there is no “best” answer it it depends on what the interviewer is looking for. At the end of the day, interviewers aren’t really interested so much in the solution you choose for this problem, it’s more how to evaluate the pros/cons of each one within the constraints of the problem that you establish with the interviewer.

[@mohammadkareem1187]

@@crackfaang I agree in general that the solution should be based on the constraints of the problem, however in this particular problem where you have SPARSE vectors, the whole idea is how to efficiently do the computation without going through redundant process of multiplying zeros (0 x 0), so the point is how to quickly find those common index non-zero elements. The target here is definitely time complexity and not space complexity, otherwise the naive dot production of two vectors is of O(1) in space complexity.

[@crackfaang]

@@mohammadkareem1187 You're completely missing the point of this question. At the end of the day, the interviewers don't truly care about the minutia of your solution. This question is more about the discussion of the pros/cons to each different approach at the end of which the interviewer will usually say "okay code X solution". Whether they want binary search, tuple, dictionary approach, it doesn't matter: they want to see if you are able to clearly and concisely enumerate the benefits and drawbacks of the proposed solutions, much like you would in a real life scenario. I'm sure you're smart enough to know that and are simply arguing for the sake of being a smart ass on the internet. At the end of the day, solve it how you see fit. The purpose of the video was to establish 3 potential solutions and discuss their pros/cons and things the interviewer may poke holes in each approach. I'm sure there's some ultra optimal way using some crazy math to do this problem as well. Doesn't matter. Best of luck with the interview prep my G

[@mohammadkareem1187]

@@crackfaang Bro we are at the same page and I fully agree with every single word you are saying. All I am saying is to be prepared in case the interviewer challenged your proposed solution and be aware of other solutions with less time / space complexity. All the best.

[@segue97]

@@mohammadkareem1187 In a case where you're give a sparse matrix with over 1x1e10 zeroes with limited memory, optimising for space complexity will be more relevant.

[@cheesehead6982]

EDIT: nvm - I see that we don't always advance N and M by one each iteration, N may get ahead of M, etc... How is this O(N+M) time for dot product? The loop simply iterates once through N items, sure we access nth and mth item at the same time, but array access is constant, no? It seems like this would just be O(N) O(N+M) would entail iterating through all N items, then a second loop that iterates through all M items...

[@hemanthpalle259]

I think N and M are the number of non-zero elements.

[@pat777b]

wow, my solution was kind of similar to your enumerate solution. Is there a downside to me using only lists instead of enumerate? Also, did you like the extra stuff I did in my while loop? I think it makes it faster overall. I do realize it costs O(1) time (within the O(n+m) loop) to do the extra checks but it also saves time if we exit the while loop earlier. class SparseVector: def __init__(self, nums: List[int]): self.storage = [] n = len(nums) for i in range(n): if nums[i] == 0: continue else: self.storage.append([i,nums[i]]) # Return the dotProduct of two sparse vectors def dotProduct(self, vec: 'SparseVector') -> int: ans = 0 s = self.storage slength = len(s) v = vec.storage vlength = len(v) i = 0 j = 0 while i < slength and j < vlength: if s[slength - 1][0] < v[j][0]: return ans elif v[vlength - 1][0] < s[i][0]: return ans elif s[i][0] == v[j][0]: ans += s[i][1]*v[j][1] i += 1 j += 1 elif s[i][0] > v[j][0]: j += 1 else: i += 1 return ans

[@aaron10k]

isn't the space complexity for the dotProduct function constant?

[@sudharshanchakravarthy7199]

Amazing!

[@jobhunter-j7d]

int dotProduct(vector &v1, vector &v2){ vector m1; vector m2; for(int i = 0; i < v1.size(); i++){ if(v1[i]) m1.push_back({i, v1[i]}); if(v2[i]) m2.push_back({i, v2[i]}); } int l = 0, r = 0, ans = 0; while(l < m1.size() && r < m2.size()){ if(m1[l].first == m2[r].first){ ans += m1[l].second * m2[r].second; l++; r++; } else if(m1[l].first < m2[r].first){ l++; } else{ r++; } } return ans; } v1 and v2 are passed as the arrays