Microsoft Interview Experience for FTE

Coding Round(60-65 mins): 2 QuestionsGiven an array, select the largest subset such that an operation for all elements is non-zero.Given a string and a cost array associated with each index of the string. Remove elements from the string such that no two adjacent characters are the same and find the min-cost for building that string.40 people were shortlisted after the coding round for interviews.All the interview rounds were on Microsoft TeamsInterview Round 1(Medium): The interviewer was helpful. First, he introduced himself and told me about his work at Microsoft, and then I was told to introduce myself.Then he started with a simple ques:Given an array of n integers, all numbers are unique exception one of them.The repeating number repeats n/2 times if n is evenThe repeating number repeats (n-1)/2 or (n+1)/2 times if n is oddThe repeating number is not adjacent to itself in the arrayWrite a program to find the repeating number without using extra spaceI solved the problem in O(n). Then he asked me to solve it in O(1) I did the same and he was happy with the solution.Transport the materialsSome materials need to be transported from place A to place B. For transporting the materials, two trucks have been provided. Assume that each truck has enough capacity to carry all the materials in one go from place A to B. Unfortunately, some materials have restrictions on being stacked with the other materials in the same truck. The materials which cannot go together are provided as pairs.Write a program to find out whether all materials can be sent using the two trucks in one go.Also, if it is feasible to send in one go, list the materials that are being sent in each truck.Please note that there are only 2 trucks.Reading the ques, I just told him that I am feeling graph implementation with materials as nodes and restriction pairs as edges.Then we just need to check if the graph is bipartite or not.He asked me the complexity and I told since we will be using DFS time complexity will be O(n+m), n are nodes and m are edgesThe interviewer was happy because I gave the solution just after 1-2 mins of reading the question.Interview Round 2(Medium): After my introduction, he started with questionsFirst, he asked me about virtual memory and its advantages.I answered it correctly and then he further asked with an example of how we can run a 1.5GB game on a device with 1GB RAM.The answer was “yes” and the reason is virtual memory advantage but lagging might occur because of the page faults.Then he asked me a coding ques.Level order traversal of a binary tree but in inverse form i.e from the last level to first.Eg:
1
2 3
4 5 6 7

Output:
4 5 6 7
2 3
1He wanted me to use a data structure for the same. We can run BFS using Queue and for storing the nodes in the inverse form we can use stackThe last ques for this round was the string interleaving problem (standard DP ques). I was told to write the DP relation and the tabular approach.I explained to him properly and he was happy with the final solution.Interview Round 3(Medium): This round/final round was easy but the interviewer was strict. The interviewer was helpful but he wanted me to write the code efficiently without redundancies and in a proper format. First, he asked me about how was my day and how has the learning remotely going on.Coding Ques:Find the least common ancestor of 2 nodes in a BST.Simple question but there were many conditions we need to clarify with the interviewer.Like what if both nodes are the same? in this case, return the parent of that nodewhat if both nodes are the same but the node is the root? return NULL for this casewhat if one node is the parent of another? return parent of the node who was the parent of otherWith proper discussion, I was able to code it properly.Final Verdict: SelectedTips: Be confident and ask questions to the interviewer when asked.Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course. In case you are prepared, test your skills using TCS, Wipro, Amazon. Google ,  E-Litmus and Microsoft Test Serieses.