2 YOE
Completing my Masters
Phone Round: Fairly straight forward - getting diameter in a tree and a follow up - how I would approach for N-tree
OnSite (4 Coding + 1 Behavior)
Round 1: Given an array of Black and White image sequences [w,w,b,w,w,w], compute number of different white sequence combinations.
In the above example, we have 5 [w], 3[w,w] and 1[w,w,w] etc. So the ans for this example is 5+3+1 = 9.
Initially came up with a O(n*n) time and O(n) space complexity approach but was able to optimize it to O(n) time complexity without any help. For me this looked like an easy problem but i could only explain and code this by the end of round (optimize in the last minute)
Round 2: Deign kind of programming question. We have 3 methods
- increment(key_id)
- get(key_id)
3)getTop3()
We need to implement a data structure the increments the frequency of a given key_id, get the frequency of a given key_id, get the key_id's which has the top 3 frequencies. We needed to do this in O(1)
This round is going to give me a reject. Interviewer told me let's us first solve a easy question and so, I guess he wanted to give me another question after this. Initially, I wasn't able to come up with O(1) as I was trying to use a priority queue. I thought, I will go ahead and implement this first but the interviewer asked to try to optimize to O(1) and not budge on it. In a way he has also given me a hint (you can only use a linear data structure and not a tree kind of datasturcture). Finally, I was able to use this hint to come up with a Map + DLL kind of a structure which is a bit similar to LFU question (but I believe this 1 was a bit more trickier). I was able to explain him how I will be solving it but I couldn't complete the coding part. Also, I seemed to have confused the interviewer a bit for the first 20 mins but slowly gained his confidence.
Round 3: Kind of https://leetcode.com/problems/delete-nodes-and-return-forest but a bit more complicated. Had many input nodes (input was a set of root nodes of forest and so you can consider it as N number of trees). Was given a set of nodes as well as links between nodes that I needed to consider to delete nodes in the forest.
I spend around 15 - 20 mins in discussing the various approaches I could take and communicating my assumptions. I think the question looked complicated on first glance but the final way you approach is same as the 1 in above link. We just need to consider all the cases. Was able to code and solve it optimally.
Round 4: Question related to postfix calculator. ex: (a+b)/(c-d) + (c-d) is given as ab+cd-/cd-. Also, a,b,c,d are numbers and not characters.
This round was for 45 mins and I was given 35 mins for this question. I was able to come up with the optimal solution using stack based approach but had many edge cases to consider. I though I was just able to complete the question in time but the interviewer told me I have missed 1-2 edge cases. Also, didn't have time to discuss on time and space complexity although it is obvious. This might also go as a negative. Also, I wasn't 100 percent confident and was wavering a bit while solving this
Overall, I believe I have given optimal solutions in all the rounds but I think my interview seems to be easy (although I could argue that the constraints are the one's that actually difficult or time consuming). I believe not completing the code in round 2 is the biggest red flag. Also, 1-2 missed cases in round 4.
Do let me know your thoughts on this and all the best for people who are looking to get into google :)