MICROSOFT - IDC INTERVIEW EXPERIENCE
SUYOG MAPARA
Interview 1
1) He asked me to explain any of my projects. I explained him about the game ‘Battle City’ I coded. He then asked in detail about the data structures, algorithms used and AI of the game. He also asked about how I can extend those data structures for game of larger-sized games such as ‘Age of Empires’ and how running time of my algorithms will be affected by such an extension.
2) Given a very large string, give an algorithm to find repeated patterns in that string. For example; in string ”aaaabbaabba….” ; “abba” and “aabb” are two patterns.
3) Write a program to reverse a string. Optimize for space and optimize for time (separately).
Interview 2 You are supposed to design the software that downloads a website and makes it available for offline view. How you will go about the design? What are the problems you may face and how will you solve them? Write the pseudo code for the highest level routines in the software. (We were discussing this for over an hour and that was the only question he asked me in the interview.)
Interview 3
1) How was the aptitude test? Are you satisfied with the solutions you gave or now you know better ways to solve any of the problems? Why you are so inconsistent in your academic grades?
2) He asked me to explain one of my projects.
3) What are the considerations while designing a scheduler?
4) What are different methods for synchronizing the access to shared resource? Implement readers and writers problem with semaphores. (After reading the code I wrote) is it possible one of the processes waits forever? How will you prevent that?
5) Rate yourself as a C programmer on the scale of 10. Write a macro to reverse 4-byte string.
6) You have a hash table and each hashed record has a character field called flag. Write a function which takes pointer to the hash table and a key and returns true if corresponding record has flag with third byte set false otherwise. (It seems he wanted to test whether I know simple basics about hashing)
Resources
1) Algorithms books
• Introduction to algorithms by Thomas Cormen.
• Algorithm design manual by Steven Skiena. – Good book. More practical than Coreman but far less formal.
• Data structures and algorithm analysis in C++ by M. A. Weiss. – Good exercise problems.
2) How Would You Move Mount Fuji? by William Poundstone. – Past Microsoft interview questions in one place.
3) Websites
• http://www.topcoder.com/tc
• http://acm.uva.es/problemset/
Suggestion
I had studied mainly algorithm analysis but there was no question requiring clever algorithm design or in depth analysis. Still having strong algorithm base does give you confidence while speaking about your projects and answering their objections and arguments. Besides you require that to clear aptitude test and some people got direct questions in algorithms design. I would recommend you to study data structures, algorithms analysis and operating systems in depth and thoroughly revise design and implementation of your projects.
