related posts:
the technical interview
the phone interview
Face To Face (Also, A Microsoft interview)
It has been a while since I wrote the last post.. sorry, I had a presentation to prepare, but it seems that it will not see the light for a while so I'm back.
Lets get back to our topic, shall we!
My second interview at Microsoft, started after my first interview at Microsoft .. (you don't say!!)
actually it started about half an hour later, we got a break after each interview, where our recruiter introduces us to Microsoft, and how things work there, and answer our questions.
In the beginning, the interviewer introduced himself to me, and started to talk with me about some general topics, my education and background.. etc.
So, I told him that I'm (was) a student at the faculty of Engineering, computer and system Engineering department.
Just as I said that, it seems like it triggered a question in his brain.
Interviewer: Engineering.. eh!! so what is the difference between computer science and computer Engineering??
At this point, I thanked God that I actually searched for such a thing before (but it was the difference between science and Engineering... close enough, so I started from there.)
Me:.... hmm, let's see.... The difference between science and Engineering is that science is more concerned with the theory behind a subject, and Engineering with the application of this theory to our day -to-day life.
Interviewer: ok, but what is the difference between computer science and computer engineering??
Me: well, as in general science and engineering, I guess the difference is that, science is more interested in the theory of computation, algorithms, and stuff like that, that don't address a certain problem we usually deal with in our lives, but general problems... and engineering is using these theories, and tune them to our applications that actually solve the users problems.....
This is how I remember I said it, and the interviewer didn't put much pressure on me in that question.
He kept talking with me about my education, till we got to systems programming.. assembly language and stuff like that. He seemed very interested in that subject, so, I added that I wrote a paint program in assembly when I was in 2nd year, with a friend of mine and a class project (it was a cool project) in less than 2 days, and how was writing the code for drawing a line was the hardest part.
He then took me to the white board to continue the interview there.
He asked me one coding question, and changed it while I went through it.
Interviewer: so, you have a file containing at most 32000 non repeated integers each is 16 bits unsigned, ranging from 0 -> 31999 , and you want to copy them sorted to another file // you can think of it as if the files are on different hard drives or computers, but it shouldn't affect your code... also note: you only have 32000 locations in memory.
Me: so, I think we need to fully read the file containing the numbers, so no where around that.. which at least takes O(n). And since they are non repeating and there is enough memory for all of them, we can just read them one by one, and the one we read we put it in an array with the index being its value, I even (stupidly) added that we can initialize the array with -1 (they are unsigned man), so he said 0, and I said right 0.
I also said that we can use a boolean array, to save space, as in java for example an integer is 4 bytes, and a boolean is 1 byte. So he said, yes we can, but some times compilers use 4 bytes for booleans to reduce the overhead on the processor in calculating their values and I agreed.
This algorithm is surprisingly a simplified version of count sort (which will probably come up in an interview not related to Microsoft later).
He then introduced a new variant to the problem.
Interviewer: So, now lets assume that you only have 2000 locations in memory, not 32000. how would you attempt to solve that..??
Although this question struck me like a lightning, I kept my cool attitude :\
Me: well, all I can think of right now is to read the numbers 2000 by 2000 and sort them (or read them the way we read them before ) then add them to the file, and some how try to merge these entries together... !
He didn't seem to like that answer very well, so I asked for a hint..
Interviewer: each integer is 16 bit...
Me: ohhh, sorry I forgot about that, 16 * 2000 is 32000, so we can represent each number with one bit hmmmmmm.
Interviewer: So, how would you implement that?
Me: let's see, we read them one by one, then determine their location using an equation that gives me the place in memory, and the number of bit:
( (int) number / 16 ) gets you the index in which the number should be located in the array.
(number % 16) to get the bit index of the number in the location (the +1 is because numbers like 16, 32, 48 should be in the next location as 16%16 = 0, and we need them in location 1 bit 0, not location 0 bit 0)
NOTE:
If you shift the number (ONE) you should shift it with (number % 16), as (ONE) already covers the first bit
so, zero goes in the first bit , one in the second and so on... till 15 in the last (all in the first entry in the array).
I used a loop to shift the number 1, the number of shifts is the number that represents the bit location, then OR it with the number in the array, to get the new number that should be in the array.
He said: ok, go ahead and write the code, while I get me something to drink.
He went to get something to drink (he asked me if I want something to drink and I politely said thank you :) )
When he came back, I was about to finish the part that reads the file and encode the numbers in their locations.
When I was about to write the code to write the array back to the 2nd file, he stoped me and looked at the code... he seemed to like what he saw, So, he asked me how will I do it...
Me: I'll read the numbers one by one, then loop from 0->15 (or 1-> 16) then AND that number with 1 that is shifted each loop (so we get 00......1, 00......10, 00....100 and so on till 100...00), if the result is one, then the number exists, and should be written else it shouldn't and so on.
the technical interview
the phone interview
Face To Face (Also, A Microsoft interview)
It has been a while since I wrote the last post.. sorry, I had a presentation to prepare, but it seems that it will not see the light for a while so I'm back.
Lets get back to our topic, shall we!
My second interview at Microsoft, started after my first interview at Microsoft .. (you don't say!!)
actually it started about half an hour later, we got a break after each interview, where our recruiter introduces us to Microsoft, and how things work there, and answer our questions.
In the beginning, the interviewer introduced himself to me, and started to talk with me about some general topics, my education and background.. etc.
So, I told him that I'm (was) a student at the faculty of Engineering, computer and system Engineering department.
Just as I said that, it seems like it triggered a question in his brain.
Interviewer: Engineering.. eh!! so what is the difference between computer science and computer Engineering??
At this point, I thanked God that I actually searched for such a thing before (but it was the difference between science and Engineering... close enough, so I started from there.)
Me:.... hmm, let's see.... The difference between science and Engineering is that science is more concerned with the theory behind a subject, and Engineering with the application of this theory to our day -to-day life.
Interviewer: ok, but what is the difference between computer science and computer engineering??
Me: well, as in general science and engineering, I guess the difference is that, science is more interested in the theory of computation, algorithms, and stuff like that, that don't address a certain problem we usually deal with in our lives, but general problems... and engineering is using these theories, and tune them to our applications that actually solve the users problems.....
This is how I remember I said it, and the interviewer didn't put much pressure on me in that question.
He kept talking with me about my education, till we got to systems programming.. assembly language and stuff like that. He seemed very interested in that subject, so, I added that I wrote a paint program in assembly when I was in 2nd year, with a friend of mine and a class project (it was a cool project) in less than 2 days, and how was writing the code for drawing a line was the hardest part.
He then took me to the white board to continue the interview there.
He asked me one coding question, and changed it while I went through it.
Interviewer: so, you have a file containing at most 32000 non repeated integers each is 16 bits unsigned, ranging from 0 -> 31999 , and you want to copy them sorted to another file // you can think of it as if the files are on different hard drives or computers, but it shouldn't affect your code... also note: you only have 32000 locations in memory.
Me: so, I think we need to fully read the file containing the numbers, so no where around that.. which at least takes O(n). And since they are non repeating and there is enough memory for all of them, we can just read them one by one, and the one we read we put it in an array with the index being its value, I even (stupidly) added that we can initialize the array with -1 (they are unsigned man), so he said 0, and I said right 0.
I also said that we can use a boolean array, to save space, as in java for example an integer is 4 bytes, and a boolean is 1 byte. So he said, yes we can, but some times compilers use 4 bytes for booleans to reduce the overhead on the processor in calculating their values and I agreed.
This algorithm is surprisingly a simplified version of count sort (which will probably come up in an interview not related to Microsoft later).
He then introduced a new variant to the problem.
Interviewer: So, now lets assume that you only have 2000 locations in memory, not 32000. how would you attempt to solve that..??
Although this question struck me like a lightning, I kept my cool attitude :\
Me: well, all I can think of right now is to read the numbers 2000 by 2000 and sort them (or read them the way we read them before ) then add them to the file, and some how try to merge these entries together... !
He didn't seem to like that answer very well, so I asked for a hint..
Interviewer: each integer is 16 bit...
Me: ohhh, sorry I forgot about that, 16 * 2000 is 32000, so we can represent each number with one bit hmmmmmm.
Interviewer: So, how would you implement that?
Me: let's see, we read them one by one, then determine their location using an equation that gives me the place in memory, and the number of bit:
( (int) number / 16 ) gets you the index in which the number should be located in the array.
(number % 16) to get the bit index of the number in the location (the +1 is because numbers like 16, 32, 48 should be in the next location as 16%16 = 0, and we need them in location 1 bit 0, not location 0 bit 0)
NOTE:
If you shift the number (ONE) you should shift it with (number % 16), as (ONE) already covers the first bit
so, zero goes in the first bit , one in the second and so on... till 15 in the last (all in the first entry in the array).
I used a loop to shift the number 1, the number of shifts is the number that represents the bit location, then OR it with the number in the array, to get the new number that should be in the array.
He said: ok, go ahead and write the code, while I get me something to drink.
He went to get something to drink (he asked me if I want something to drink and I politely said thank you :) )
When he came back, I was about to finish the part that reads the file and encode the numbers in their locations.
When I was about to write the code to write the array back to the 2nd file, he stoped me and looked at the code... he seemed to like what he saw, So, he asked me how will I do it...
Me: I'll read the numbers one by one, then loop from 0->15 (or 1-> 16) then AND that number with 1 that is shifted each loop (so we get 00......1, 00......10, 00....100 and so on till 100...00), if the result is one, then the number exists, and should be written else it shouldn't and so on.
he also added that we can and the shifted number (00...1, 00...10 etc) with the number 65536 (11...1)
then AND them with the number in the array .... then I interrupted him (I guess I did) to know if there are more numbers encoded in that number in the array and if there isn't , then we break from the inner loop and go for the next element in the array..
The interview seemed to have went very well (and I agreed :) );
then it was time for the next interview......
stay tuned for the next interview in the next post.
gr8 post, and I really liked the question of sorting, but I have some questions that I believe are not as stupid as the previous one :) :
ReplyDelete-I think that answer in case of having 32000 locations is hard to be understood in that way , but any way I'll say what I have understood :
did the interviewer say that the 32000 integers in the file are unsigned? (as u said late in initializing array part that they are unsigned)because if they are then the solution would be wrong , as 16 bits will make numbers from 0 to 63999 , so if the file contains for example the number 40000 it won't have a corresponding index in the array.
-in the 2000 locations case, I don't find use for the +1 part (there is contradiction between your explanation and the example you gave after that), the example is correct , if we took 16 as an example
location = 16/16 = 1, bit = 16%16 = 0 which is correct (so why do we have to add another 1?)
but really I enjoyed reading this post (more that any of this series :) )
keep it up ;)
You are absolutely right... I think I forgot to mention that the numbers range from 0->31999, which is now fixed in the post
ReplyDelete// note: that was over a year ago
But even though, if it contains all the range in an unsigned integer, it would also have more than 32000 numbers (32768), so it would break anyway.
I think the interviewer meant for the numbers to be all positive to make the array index easy, and only 32000 number so that the range would not get to the end of the integer range.
About the second question:
In arrays that are zero based, you don't get the 2000 location... the array range is (0-> 1999)
But I think you are right...
I meant the location of the bit (I wrote: the bit index), as you have 1st location, 2nd location .... etc
not like arrays, so, this is for explanation, and I'll probably rewrite it now :)
Thanks man for the (honest/ frank ) review (if you know what I mean :)).