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. 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......
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:
Friday, June 03, 2005
My Experience with Microsoft Interview (Part 1)
Subscribe to:
Post Comments (Atom)
19 comments:
eb2a kammel ana basma3 asli 3awez a3raf koll 7omoreieti gatt feen
Try it yourself first ;)
What do you mean?!
No, they won't wait for you, and for me, I was postponed from the military service
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
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
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.
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
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.
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
This won't return all pairs in o(n)
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
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)
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
Yup
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
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.
how to find all pairs of element whose sum is 20,using array
Very Helpful. Thanks for sharing!
Post a Comment