Friday, June 03, 2005

My Experience with Microsoft Interview (Part 1)

Hii again, now I've some time to write my own experience with Microsoft during their interviews in Cairo, Egypt 2005 for SDE/SDET positions.

The whole game had started when I knew (I think I knew about these interviews on July 2004) that Microsoft will come to Egypt to make some interviews for some positions in Redmond campus, so I sent my CV to them along with my teammates CVs, after a short period they had answered me and had asked me about the expected graduation date for us, I told them it'll be after one year, nearly on July 2005, she replied by fine and then I hadn't heard any thing from them for about 4 months.

After this long period they had contacted me, and I knew after that, that the process is done through 4 main steps:

  1. They watch your CV, if it's good with good list, they will jump to the second step, if not they may reply you saying sorry and may not reply at all.
  2. They call you and make an initial phone interview asking you about some very simple things just to know about your way in thinking and try to deduce whether you had just written alot of things in your CV without real knowledge about them or not, usually it takes from 45-60 min, after passing this test, if you passed, you'll jump to the third step, if not, they will call you, and tell you sorry your qualifications don't meet our needs.
  3. HR test, some IQ questions, and some questions to test you way of thinking, and your ability to think for any solutions for some really weird questions and so on, this also takes between 45-60 min, and if you passed you'll jump to the final and main interview (all the above tests were just pre-tests to see whether you can go for the interview or not), also as the same 2 steps, if you passed you'll go to the interview and if not they will tell you sorry, usually no one will pass the second step and fails in the third step unless he was too sleepy or too stupid or no afraid (too afraid mean really toooooo afraid for the extend of not being able to even speak well).
  4. The main interview, it consists of 5-6 interviewers from Microsoft, every one of them will make an interview with you alone for 45-60 min, so it may take up to 6-7 hours (we were soooo tired after this interview), they will ask you alot of questions about many things, testing your ability in programming, writing an efficient algorithms, write programs free of bugs, making program to test others code to see whether it's free of bugs or not, and finally if you passed all these, you'll be setting with them in a good friendly interview and then they will ask you alot of questions about why you want to join Microsoft and what you think you'll do there and such questions.

Now I'll take you through these steps and my results during them.

1- CV: no need for talking about it, it's just CV no more no less, I think it was written in a good way, that's all, and they asked me about my military status and I told them I dont know about it yet, that's all.

2- Technical phone interview: After the 4 months I had told you about, I had got an email asking me for the best time to hold a phone interview with me, after I had replied, and in the day of the interview, I had got an international phone call (with un-able to get the caller ID msg) from a member in the Office team, his name was Mike, he had talked with me in a very friendly way, had talked about himself and his position in the company, then he asked me to open a kind of web whiteboard to begin the small test, it was mainly about sorting algorithms, and in which cases X algorithm will be better than Y, and how could we remove or add a line of code to make X works like Y and so on.

3- HR test, Caroline hadn't asked me to do this test, and I don't know why, and as I know, Iam the only one from those people whom I knew they had made their interview with Microsoft (in this year or in the past) who hadn't taken an IQ test till the end!!!

4- The main interview, the whole game began at 8:00 AM at Conrad Hotel in Cairo, I had went there with my teammates, we had found another two members there whom will have their interview with us(we discovered later that they had chosen only 20 developers for the final interviews, they had grouped them into 4 groups, 5 each, 2 groups per day), so after 10 min, we had seen someone heading to us, ohhh, it's Caroline, Hi Caroline, Hii guys, how are you, we hope you enjoyed your time in Egypt, so we had entered the elevator all, and had gone into their main room, we meet their another 5 members from Microsoft (I don't remember the names) one of them way a program manager in SQL Server, another one was program manager in XML team, the third one was working as SDET(SDET means Software Design Engineer in Test) in SQL Server team, the forth (I don't remember his position too), and the final one was HR(her name is Holly), and Caroline, so they were six members.

The interview had started in this way: we're 5, and the team (excluding Caroline) was 5, so everyone from the team will take one from us to his own room for 1 hour interview, my interview gone in this way:

First Interview:

My first interview gone with the first interviewer with Soner Terek, SQL Server Development Manager, he told me that he used to be a manager in his own company before he joined Microsoft, and that he had been in Microsoft since 11 years ago, had worked in many places like Windows and finally had reached SQL Server, and had asked me why I want to join Microsoft, and so on, after that he had asked me one question, Imagine you have a array of integer, and you want to get any two numbers whose sum is 51, what you'll do?

I asked him, do you want only 2 numbers or all 2 numbers whose combination is 51?

He told me only two in both O(n^2) and O(n) and try to parallize the both solution if we've up to n processors.

After making the whole solution set he told me that I did fine and to go back to the main room.

Second interview:

The second interview was fine, and more easy, I had made it with these one who's working as SDET(SDET means Software Design Engineer in Test) in SQL Server, it was simply about how could I make a code without any known or unknown bug, so he asked me to do 2 simple programs, the first one was a simple dynamic string array class, and had looked much into how could I handle every known and unknown bug (even the buffer over-run error) try to think about cases which can't be happened even you intended to do it, and then asked me to make another program which is handling a problem which I forgot its name (modified Josephus problem), afterthat he told me fine, nice work, let's head back to the main room.

Now I'll write the.......

To Be Continued......

24 comments:

Yasser Rihan said...

eb2a kammel ana basma3 asli 3awez a3raf koll 7omoreieti gatt feen

Avi said...

How do you find if the array contains two numbers whose sum is a given number in O(n) time?

Thanks

Mohamed Meshref said...

Try it yourself first ;)

Moustafa said...

And what about the military service,
if it hasn't been comleted, they wouldn't have taken you ?

Mohamed Meshref said...

What do you mean?!

Moustafa said...

I mean if one had to do the military service, and microsoft accepted him, does he have to do it before going to microsoft?, and will it wait?

Moustafa said...

I mean if one had to do the military service, and microsoft accepted him, does he have to do it before going to microsoft?, and will it wait?

Moustafa said...

And have you done it?, or what did u do?

Mohamed Meshref said...

No, they won't wait for you, and for me, I was postponed from the military service

fayyaz said...

Hi,

How do u find two numbers summing upto 51 in O(n). Don't say try it urself. I did and here are my results.

One is O(n2) trivial checking every combination of two numbers. Second is sorting both arrays in nlgn. Then looping first n times and checking if 51-n exists in the second using binary search. So this given nlgn. Even if u sort using say counting sort in O(n), still finding 51-n will be lgn so this will result in nlgn in the worst case since we dont know if only one such combination is there and we find it in the very last combination. Similary, u have written in your interview with XML lead that u reduced select to O(n) called x merge sort. Could u please eloborate a little or give pointer to where i could find some implementation or pseudo code.
Thanks
Fayyaz Khan Lodhi

fayyaz said...

Hi,

How do u find two numbers summing upto 51 in O(n). Don't say try it urself. I did and here are my results.

One is O(n2) trivial checking every combination of two numbers. Second is sorting both arrays in nlgn. Then looping first n times and checking if 51-n exists in the second using binary search. So this given nlgn. Even if u sort using say counting sort in O(n), still finding 51-n will be lgn so this will result in nlgn in the worst case since we dont know if only one such combination is there and we find it in the very last combination. Similary, u have written in your interview with XML lead that u reduced select to O(n) called x merge sort. Could u please eloborate a little or give pointer to where i could find some implementation or pseudo code.
Thanks
Fayyaz Khan Lodhi

Mohamed Meshref said...

You need to ask him "is it already sorted?"

So now, if it's already sorted, how can you use this to solve it in O(n)?

And about the other problem, I can't really remember anything about it now.

fayyaz said...

Even if it is sorted, then for each number n checking whether 51-n exists in the array means nlgn since we dont know which n will have the right solution. So i dont see a way to bring it to O (n). Plus it was included in the question "try to parallelize this to n processors". I dont see a way here to complete tasks in parallel? Please elaborate, i have spent some considerable time thinking about it. And i have a good record in programming and algorithms. But simply cant figure it out yet.

Thanks

Fayyaz

Mohamed Meshref said...

What if you have a loop and 2 indexes one to the first item and one to the last one?

Add them, if the sum sum is < 51 then increase the first index, if it's > 51 decrease the second one untill you either find 51 or first > last.

fayyaz said...

okay now i got it. And it's pretty much plausible. The idea of incrementing or decrementing with comprasion simply didnt occur to me. Although i considered comparing from both ends. Why did u ask the interviewer "a single pair or all pairs" since this approach gives all such pairs if sorted. Simply start with next element from both sides once u find a suitable pair.

Thanks for responding and clarifying.

- Fayyaz

Mohamed Meshref said...

This won't return all pairs in o(n)

fayyaz said...

Can u give a simple test case which fails this approach of not returning all pairs? I tried quite many and i found all to be sucessfull?

Thanks

Mohamed Meshref said...

1 1 50

If we're not looking into a single pair, then it can't be o(n) because if we used the O(n) method it will return only (1,50) not (1,50) (1,50)

fayyaz said...

AOA!

I somehow assumed that elements would not be repeated in the array. But ofcourse, you are right when they are repeated. However, if they are not repeated and the array is sorted, then it gives all pairs with in O(n), right?

regards,

Fayyaz

Mohamed Meshref said...

Yup

fayyaz said...

Even if it is repeated, we need to add a few checks.

There are four scenarios. First, the next element is not repeated at both ends. In this case, increment both. If either one of them is repeated only, then increment the other element once and proceed. If both are repeated then generate both sides i.e. increment one side and pair out on the other while keeping track of the increment. then repeat the same on the other side. (It is like generating four possible combinations in case you have two equal elements.)

I believe this way, we can have all such pairs in O(n).

regards,

Fayyaz

Mohamed Meshref said...

When you measure the complexity of an algorithm, you do it in the worst case, so in our example, imagine an array which containts only 1 and the rest is 50, now you'll do it O(n^2), there's another solution which is to mark your places but in this case it will ne array of size n to mark all these.

GenesisCEO said...

how to find all pairs of element whose sum is 20,using array

Allinn1 said...

Very Helpful. Thanks for sharing!