Microsoft | 2021 | Off-CAMPUS | Microsoft engage program
Round1 ( Coding Round on Codility ):
There were two questions to be solved in 120 mins. Questions were medium-hard level.
This question was based on multi-source BFS. A graph was given and an array of hospitals, now for all non – hospital nodes, we need to find the max time an ambulance may take to reach them. ( medium-hard )
This question was based on Graph DFS + DP. Don’t remember the question exactly, but it was to apply the inclusion-exclusion principle on graph nodes using DFS. ( hard )
I was able to solve both the questions and passed all the given test cases within 60 mins. It was mentioned that code would be judged after submission for hidden test cases as well.
Round 2 ( Interview Round 1 on Teams ):
This round lasted for about 45 mins. I was asked 2 coding problems.
Zero Subarray sum, earlier he asked for a bool value, then he asked me to return starting and ending indices of all such subarrays.
When a binary tree is given, the node value can be either 0 or 1. Now moving from root to a leaf forms a decimal number in binary representation. I was asked to find the sum of all such possible decimal numbers. All such possible numbers would be equal to the number of leaf nodes present in the binary tree.
I was able to solve the first one quickly, then the second one with some hints from the interviewer. I was asked to write code in my favorite editor and run the code for some test cases. The interviewer was satisfied at the end and he asked whether I had any questions for him. Within half an hour I received the call for my second round.
Round 3 ( Interview Round 2 on Teams ):
This round lasted for about 50 mins. I was asked 2 coding problems.
Cutting a rod problem was asked, I explained the overlapping subproblems first and optimized them using DP. I was asked to run the code and check for many test cases( including the edge cases ). The interviewer was satisfied with the code, then he said we have time so let’s solve another question.
String question DP + Rabin Karp Hashing. Given a vector of strings, and a target string, find whether a subset of the array of strings could concatenate to the target string, if more than one possible way, return the one with minimum elements in the subset. I explained to him first how hashing would help in comparing then overlapping subproblems while making the target string. Then I was asked to write the code for the same.
The interviewer looked happy after I solved both the questions, So I was pretty sure that I would qualify for the next round.
Round 4 ( Interview Round 3 on Teams ):
This round was conducted after 4 days of the previous two rounds.
The interview began with my introduction, I was asked to brief about my internship and project experience. Then he asked me the potential problems that would occur if my project ( web dev ) was used by millions of users. It took the direction of system design, we discussed how to decrease the latency time in detail.
Then after a 20 min discussion, he asked me a coding problem to code quickly. The problem was based on a string. A string is valid if all the characters have the same frequency or at most two different frequencies. Example – aabb is valid, aabbccdd is valid, aabbccdd is also valid, but aabcddd is not valid. The question was pretty simple, but it took time for me to understand it. I wrote the code and then the interviewer asked me to run it on some test cases.
Result: In the evening on the same day, I got the mail that I have been selected. I was so happy and started celebrating.
Tips for Coding Round –
Practice Graph-based questions and their variations. Try to write print/cout statements along with your code, this helps you to debug faster.
Try commenting on your code as well and with meaningful function names.
Make sure to check for edge cases ( very imp ).
Tips for Interviews –
Listen to the question carefully and clarify the question first, before prompting for your solution.
If you are stuck, discuss what you know and where you are facing issues, this helps the interviewer to provide a direct hint.
After you discuss your approach, don’t forget to explain the time and space complexities.
Be confident in your answers and think out loud.
I hope this helps !!