Microsoft Visited our campus for Internship selections on IDC and IT profile. There were three rounds for the selection process of IDC profile
First Round :Coding round
3 Questions were asked in different sets . Out of which people who solved 2 and more are shortlisted . People who solved 3 were shortlisted for Personal Interview , while the one’s who solved 2 were shortlisted for Group fly round.
Questions were :
- You will be given buildings of certain height that lie adjacent to each other . Sun starts falling from left side. If there is a building of certain Height, all the buildings right of it having lesser heights cannot see the sun . You need to find the total number of such buildings that receive sunlight .
Find the increasing subsequence (Not strictly ) with 1st building as the starting building.
Solution: neveropen Link - You will be given two arrays of equal size and you need to maximize the first array with the second array elements ( swap the first array elements with second array elements . Once swapped , you cannot use the element anymore )
For ex: A: 3 4 6 8 9 and A : 5 7 3 6 8
B : 6 7 8 8 9 B : 3 4 6 9 10
Op: 9 8 8 8 9 Op : 10 9 6 6 8Solution: neveropen Link
Sort the second array and start swapping if the a[i] < b[i] . else wait for the next a’s element which is less than b[i] and swap ( naive merge procedure ) - You will be given two trees t1 and t2. You need to check if t2 is a subtree of t1. If it is a subtree ,you need to return the size of t2(number of nodes in it).
If either of t1 or t2 are NULL, return -1 .
If t2 is not a subtree of t1 , then also return -1Most Efficient Solution was :Any Tree has 2 unique traversals . ( Either it be (preorder,inoder) ,( in,post) ,(post,pre) ) . So , Traverse them and store any two traversals for both the trees Check first traversal of both trees (String Matching using KMP O(N+M) ) and similarly for the second traversal.If they both come out to be true ( I mean pattern exists in text ). Then you are done . Else return -1This Complexity is O(N+M) and space O(N+M) . If you want to do without space , Try for the recursive approach which in worst case takes O(N*M) complexity
Apparently , I was shortlisted for Personal Interview , so I didn’t attend the Group Fly round.
- Find the median of an Unsorted array . I told him to sort it and find it as per the parity of N( even or odd) . NLogN solution . He asked me to optimize it . Then I told him about the median of an unsorted array in worst case O(N) method … (you can find it in gfg ).He asked me if I can do it using Quick select .. I told him the way to do so and suggested him that the worst case might shoot up to O(N^2) .He told me its fine and asked me to write the code. My code was bit tedious but I was able to get correct code finally .
- Then he asked me regarding hashing (chaining and open addressing – Insertions ,deletions etc ) and c++ maps and their complexities
- You are given an unsorted array where any element can repeat any number of times. Elements ranges are > size . N is too high (10^7) .So , I Gave him O(N)time and O(N)space hashing solution using unordered_map solution . He was satisfied .
- Next the question is to validate a date so that it is in the format expected and should be 20 years less than current date. You need to throw exception if it is invalid. First , I encountered all possible exceptions and after that I wrote an accepting method. He asked me to write code. This time I wrote a clean code covering all possible exceptions . He was satisfied. and told me that the motto of these technical rounds are to check if we can write correct codes and can grasp basics and analyse our strength in them.
3rd Round( HR round)
The manager was very very cool and asked me questions like . Why do you want to join microsoft? Why should we hire you and related stuff about me and he asked me to solve this question. Find the majority Element (element that repeats more than (N/2) times in an array . If it doesn’t exist , return -1. I told him the way to solve it in O(N) time and O(1) space using Moore’s voting algorithm And after these rounds , I was given offer for the Internship for IDC profile.
Though I was selected for GolmanSachs Interview too , I had to take up this offer and I didn’t sit for GS personal Interview.
Thanks to neveropen for helping me revise all the concepts and practice them with the help of practice.geeksforgeeks.org . My Last 15 days before the Intern were completely spent solving problems and revising them in neveropen.
A Big Thanks to the team!!
If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
