MICROSOFT INTERVIEW EXPERIENCE | SDE | REJECTED | OFF - CAMPUS
Phone Screen: Project Overview and Count number of islands.
Round 1 :
I suggested these 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 a 2 pointer approach where each node has a link to the parent node and it can be used to identify previous/next value. Interviewer pointed out some bugs in the code which I fixed.
Project Overview for 30 mins. Question – For a card based game, verify if given cards form a winning hand. Simple question but the rules of games were complicated. I clarified rules and started implementation. Midway in the implementation interviewer mentioned that the rules of the game are different from what I have understood Clarified and fixed it. Couldn’t find it on Leetcode.
Some project overview. Question - Given some texts and indent level for each text, store it in a data structure. I suggested a map based approach. Interviewer suggested trying a 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 the DFS of the tree will give the 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. https://leetcode.com/problems/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 the initial description of the problem was very vague in every round.