Microsoft Interview Experience: SDE windows division, IDC Hyderabad

_________________________________________________________

This is a narrative of my interview experience with Microsoft for a SDE position in windows division for Hyderabad office. One fine afternoon, I got a call by a placement agency for an interview at Microsoft's hyderabad campus ( I guess they picked my resume from LinkedIn or Naukri.com), and I agreed, we fixed the coming saturday as the Interview date. Though generally for anyone with less than 3 years of experience they conduct a written test , but I was fortunate to directly start with personal Interviews.

 We ( about 10-12 folks) were made to sit in a conference room, and the recruiter( the HR guy) sequentially took each one of us to the Interviewer. My first Interview started a little off track , with the Interviewer asking about my role at my present company , which I had joined few months back , I described the work which I had little Idea about. I also mentioned that though 

my present company works on Java , I ha

ve little knowledge of Java and would prefer C for any coding questions. He asked me If I had any experience with C++ , I said I had studied that in college but have not used since , though my concepts of OOPs are clear. He was fine with that and started grilling me on OOPs.

What is a virtual function ? How might the compiler implement virtual fuctions ? I explained him the logic behind virtual function tables a

After waiting for about 15 minutes , the recruiter took me to another Interviewer. This guy was “too the point” guy and without any formalities he directly started with a design question. He wanted me to design a memory manager for him ( the one with free() and malloc() calls ), I explained him the the free list concept and how a small portion of memory allocated can have information about its size which can be used to recombine adjoining free blocks. We discussed about internal and external fragmentation and how this architecture be extended for a software system that has many modules. Then he gave me a programming question , which was like “Given a rectangular grid with some integers in it , now implement a operation which will take the coordinates of a rectangular subsection of the bigger rectangle and return the sum of all the elements in the smaller rectangle, this operation should be a constant time operation”. After taking about 5-7 minutes to analyze the question , I gave him the solution and he was very surprised and happy too . :) . ( the solution involves pre-computation of the sum of elements till every point on the grid , and when a sub-grid is asked , we can take the sum at the corners of the grids and do a couple of additions and subtractions to get the sum inside the grid). This interview too lasted for about 50 minutes and I was sure that the Interviewer was pretty impressed.nd how the compiler might link the right the function in run time. He went a little too deep and wanted me to make an architecture diagram of how this might happen and then after a lot of explaining he was a little bit convinced . Then he started with Synchronization , and asked me what all we use for that , I said mutex and semaphore , and then he wanted the difference between the two. Though I knew the concept behind the different , I got confused about which was which , and after a lot of fumbling told him the concept of ownership applies to mutex and the thread which has locked the mutex is the one which can unlock it, and this is not true for a semaphore. He agreed and we moved a codding question. The question was given a binary tree print it in lavel wise order. I had done this question previously too and I quickly wrote a pseudocode in C and he wanted me to give him a walk through and he was satisfied. This was my first Interview which I guess was Ohkish and it lated for about 50 minutes.

Start out of this Interview the recruited told me that so far I was doing well and I need to keep this up in the next rounds too. I had one more interview , here the interviewer asked me question to search for a simplified regular expression in a string. He was more interested to see how I handled the regular expression , all the boundary cases and a null expression etc, than the algorithm used. I told him a solution and then asked him should I use a build in function to search for a subsrting , he said for now it is ohk . I wrote a pseudocode and he pointed few edge cases and I fixed the code and then he wanted me to write that substring function. I told him about how I might use KMP to do that but it will take some time to code that up , he said I can write the brute force algo also and so I did.

                                    The recruiter told me that so far I was good , and mostly I am selected (yupeee!!!) , but I will have one final interview with the General Manager of Windows division and we will fix a time sometime in the coming week. On monday I got a call from him and we scheduled the interview for wednesday and it was supposed to be a technical interview for about an hour.

                                     This was a big guy , GM of windows , I was pretty nervous , I enterned his cabin and he just sprang up and was off to the white board in no time. He gave me a programming puzzle and aksed me to code it up . The question was something like , if a sorted array is rotated by some unknow value and I had a search for an elemnet in that array, Thankfully I had experienced a similar question previously and was able to write a buggy code ( common ,I was nervous ), he made some changes to the code , took and expample and worked through the code and yeah it was woking. He then asked me a design question. We need to check if an element belongs to a set (hash table aye ? ),what scheme to use if we do not know how many times this operation will be performed , may be once or may be a million times. So a hash table is not good if it was done just once. So we deliberated and I came up with an adaptive algo which will start with a BST and change into a hash table as the operation is performed. He was satisfied ( or so I thought ). 

Then the recruiter had a private word with the GM and after about 15 minutes he came out and told me that I will be sent a offer letter. :) .

My advice for all Microsoft Interview candidates :

1. Brush up your OOP , specially Virtual Functions , Inheritance .
   
   
   
   
2. Operating systems , specifically, Memory Management, Synchronization.
3. Do a lot of hash tables and know about sort and search function, BST and other algo stuffs.
4. Code properly , MS looks for folks who can do clean coding and handles all edge cases , do checks for malloc() , do null checks , do range checks.       

       Best of luck, Lucifer.