Microsoft | SDE-I (On-Campus)
Online Assessment – There were 2 coding questions.
Q1) There are N cities. Cities are connected by roads .(Basically given a graph). K of the cities has a hospital(Given an array of size K). Time taken to reach a hospital from a city is no of edges to the nearest city which contains a hospital. Find the maximum time taken to reach a hospital from all the N cities.
Ans – (Just do a normal multi-point BFS and store the distance of every city and return the maximum one).
Q2) Given a tree of N nodes(0 as the root). Each node contains either ‘A’ or ‘B’. Return the longest path of the tree such that no consecutive letter of that path is the same.(Either “ABABA..” OR “BABABA”) .
Ans – Pretty standard DFS question . Calculate the answer for each node as a root (sum of 2 best child subtree+1) and return the longest path (longest child subtree+1). Maximize the answer.
Luckily, Microsoft gave weightage to the time in which candidates solved the questions, rather than the gpa unlike some other companies. Around 40 were shortlisted for interviews.
Interview Round 1 –
He introduced himself and asked me for an introduction and 1 of my project(mine was an e-commerce website) and asked some questions about it. (Ex-How would you handle multiple requests at the same time for the e-commerce website. How much load can your website take .)We had a discussion for around 20mins and then he asked me a coding question.
Given a 2D grid, there is a value present in each grid. 1 means this index is vaccinated . 0 means this index is not affected till now but not vaccinated . -1 means this index is affected by the virus. (Virus will spread from -1 to 0, in 4 directions) .Find the last day when virus spreading will stop.
I gave him the solution by multipoint bfs. He was quite satisfied with it and asked me to code it. After that he asked me some questions like count the number of indices which are not going to be affected at all(but not by this approach. I gave him the approach of doing a dfs from each indices having 0 value and if we find a 1 we will just return but if we find a -1 this index is surely going to be affected at some time. He was satisfied with it.)
Then he asked me to write some good test cases for the original question , so that it will cover all the possibilities of the solution. At the end he was satisfied and asked me to wait in the call for next round.
Interview Round 2-
After the introduction, he asked me about my internship experience and what work i have done there, the tech stack I have worked on.
Then he asked me some oops concept (polymorphism, abstract classes).
After some time of discussion, he gave me a coding question.
https://www.geeksforgeeks.org/find-pair-given-sum-bst/
But I had to code for the input as well(the whole bst and how i will take the input) and find all the pairs. He was satisfied with my code and asked me to stay on the call for next round.
Interview Round 3 – It was an HR round.
He asked me different questions about my internship and what challenges I have faced during that. Why I want to join Microsoft and what I have to offer to the company and some other HR questions.
Then he talked about the goal of Microsoft as a company and what is the work culture there etc. This round lasted around 35mins and my interview was done.
Verdict- Next day I got to know that I was selected for the role.
Tips:
For the preparation point of view, my advice would be study all the CS fundamentals(oops, OS, DBMS, CN), practice as much as u can in GFG and Leetcode, know all of your project (like what technologies you have used and why you chose that).
Also, some of my friends were asked System Design questions. So you should be prepared for that as well( e-commerce design, twitter design, lift design, parking lot design etc. ).
Happy Coding!!