Tiktok SDE VO - Two Code Questions

The interview process at TikTok is quite similar to this, so I’ll share two coding problems I recently faced in a TikTok interview.

First question: How to calculate the dot product of two sparse vectors. The interviewer directly provided the English description of the problem and first asked me to explain my approach: The key lies in two steps: how to store sparse vectors and how to calculate the dot product of these two sparse vectors.

Step one: Use a Hashmap<int, int> to store the mapping of non-zero element indices to their corresponding values.

Step two: For two sparse vectors, a and b, iterate over the vector with fewer non-zero elements. When reaching index i, check if the other sparse vector contains this element in its map. If it does, multiply the values and add the result to the final sum.

The interviewer asked me to demonstrate how to multiply the two sparse vectors. I used the example provided by the interviewer and walked through the calculations step by step. Finally, I analyzed the complexity. Initially, the interviewer didn’t provide enough parameters and only gave n1 and n2, representing the lengths of a and b. Clearly, the complexity is O(n1 + n2). The interviewer then further asked, "What if m1 and m2 represent the number of distinct elements in a and b?" I correctly analyzed the time complexity as O(min(m1, m2)) and space complexity as O(n1 + n2).

Second question: Given a string consisting of 'g' and 'b', where all 'g' characters appear before any 'b', find the first 'b'. First, the interviewer asked me to explain my approach. Our approach was to use binary search. Then, the interviewer asked why we can use binary search. I explained: This is because the key condition is "all 'g' characters appear before any 'b'." We can define three pointers: left, mid, and right. If mid is a 'g', then the first 'b' must be within the range (mid, right]. If mid is the first 'b', then the 'b' must be within [left, mid].

Then, I wrote the code and it passed the test case, giving the correct result. My binary search algorithm was written in a robust and well-structured way, which the interviewer acknowledged. Finally, I analyzed the time complexity, which was straightforward: O(logN).