Question

Microsoft | Interview Experiences | SDE | 2022 | Set-20

Answer 1

MICROSOFT INTERVIEW EXPERIENCE |  SDE | REJECTED | OFF - CAMPUS

Phone Screen: Project Overview and Count number of islands.

Virtual Onsite:

Round 1 : 

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

 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.

Round 2:

  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.

Round 3:

  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.