Microsoft | SDE | Seattle | Reject

Phone Screen: Project Overview and Count number of islands. Virtual Onsite: Round 1 : Two Sum IV - Input is a BST I suggested thse 2 solutions- Solution 1. using map to track values and checking for complement while traversing tree, O(n) space Solution 2 - Pick a node and search for target-node.val, O(1) space. Interviewer asked to provide some other solution and then gave a hint that smallest and largest elements are known in BST and Node structure can be changed. I implemented 2 pointer approach where each node has a link to parent node and it can be used to identify previous/next value. Interviewer pointed some bugs in code which i fixed.

Round 2: Project Overview for 30 mins. Question – For a card based game, verify if given cards form a winning hand. Simple question but rule of games were complicated. I clarified rules and started implementation. Mid way in implementation interviewer mentioned that rules of game are different than what I have understood Clarified and fixed it. Couldn't find it on .

Round 3: Some project overview. Question - Given some texts and indent level for each text, store it in a data structure. I suggested map based approach. Interviewer suggested to try for tree type approach. I was stuck here as I was not sure what is required here. Interviewer gave more hints to clarify requirements which can be summarized as “Convert it to N-ary tree so that DFS of tree will give correct order of text”. Implemented using stack.

Round 4: Hiring Manager. Project Overview for 30 mins. Question - LCA of a N-ary tree with some additional constraints. Suggested 2 approaches and implemented one. Lowest Common Ancestor of a Binary Tree

Overall interview was fun. All problems were easy to medium level. Challenging part was to clarify requirements, as initial description of problem was very vague in every round.

One important difference I observed between practice and interview is that gives a well defined starting point in terms of input(how many inputs ,what type) and output. In my interview, almost all questions started open ended and I had to identify what input/output should look like and then actually solve the problem. Now when I look back, I was not prepared for first part (identify input/output) because while practicing on we never do that. Ironically, in real project we do that everyday but my mind has compartmentalized information in 2 different boxes – interview/ style and real world, and I was not able to combine them 😊