Interview experiences

Once upon a time there lived two giants Miso and Goog. They amassed great empires and were greedy to expand their realms. They were in need of minions to do their dirty biddings. Who they gonna call?

Yes I was fortunate enough to get interview calls from Microsoft and Google. This post is about how I wasted both the oppurtunities. Both were phone interviews. First was the MS interview. I wasn't very tense. I was absolutely unprepared and had infact taken a mid-day nap before it. And when the interviewer threw me an easy question to see if I was worth his while I was dumbstruck. I knew it was a very easy question, but I just couldnt answer it. Two weeks after the interview I got their reject mail. It was as expected.

After two more weeks I get an email from Google (everyones dream company) about an interview. Today, after another two weeks, the interview happened. It wasn't as bad as the MS one, but again I didn't perform well. What irks me is that this time I had over two weeks notice and I still botched it up. So a friendly advice to all readers - before applying for a job, start your preparation. What? You knew it already? Fine. OK OK. I am an idiot.

Heres an excerpt from the Google e-mail:

"Your technical phone interview may include questions from one or more of the following areas: coding, algorithms and design and problem solving. For more information on Algorithms you can visit:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index

Don't forget to have an active dialogue with the interviewer and talk through how you are solving the problems throughout the interview. I recommend you spend some time exploring our website to get into the right mind frame. Google Labs is a good starting point and can be found at http://labs.google.com. I also recommend you take a look at our resume and interview tips pages as well at
http://www.google.com/support/jobs/bin/static.py?page=students.html&sid=tip"

The questions asked were:

MS -

1. Implement in Cpp Fibonacci number generation both recursively and non-recursively. Give their complexities.
   
2. Given two strings how would find the characters they have in common. Give complexity.
   
3. Give test cases for unit testing the algorithm above.
4. A lot of questions were asked about the projects in my resume.
   

Google -

1. Some basic questions about a project in my resume.
   
2. Given a set of coins of various denominations how would you find the minimum number of coins that is required to make up $x.
   
3. Given two strings determine if they are anagrams using O(n) algorithm.
   
4. Given a matrix of numbers with all rows sorted left to right and all columns sorted top to bottom, how would you find the position of a number x in the matrix. What is the complexity?

Links that you might useful if you are also preparing for interviews (will be expanded as I find more):
http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html