Monday, May 28, 2012

Face To Face interview 4 ( The last Microsoft interview)


related posts:
the technical interview
the phone interview
Face To Face (Also, A Microsoft interview)
Face To Face 2(yes, you know it.. A Microsoft interview)
Face To Face interview 3 (again, A Microsoft interview)

This was the last interview at Microsoft (finally), but I didn't really knew that.
Some of the interviewees have had 3 interviews, others had 4..... at that time, when the 4th interviewer took me to the interview room, all I though was that he was the one to tell me the
results... but after chatting with him a bit, I realized that it was an interview.

We started by chatting about general topic, how he really wanted to visit Egypt, but couldn't due to the current situation... etc. And I talked to him about my school.. and where it is relative to my home town, and both of them relative to Cairo (the capital), which I then had to demonstrate by drawing a map of Egypt on the white board, where the 3 cities appear like a triangle around the Nile river (which is shown in a different color with low opacity )

We then talked about how crowded Cairo is, which made me realize that he had done some research about the area (probably when he thought he was going to go there), then he asked me if I had a car to drive through all these distances, which I answered..... 

Me: well, I do have a driver's licence, but I don't know how to drive a car!
Interviewer: !!!!!

Me: how stuff works in Egypt is a very long story.

At that moment he said "lets start the interview" .....which should show you why I thought it was not an interview (most of it was just chatting)

The interview went like this....

He asked me to open his laptop on the login screen of Windows 7 and then test it!!

This is the kind of questions that feels like it has no complete answer... when ever you think you are done, there comes something else that can be added to the answer.

I don't remember visually how it was, but I'll try to describe it as far as I remember.

I didn't really try to login using the correct credentials nor did I try to even ask him what they were.... at that time it didn't feel like this is what he was looking for.

I started by writing some random user name and passwords and of course they didn't work, then I changed the language using (Alt + Shift) to see what happens, and the second language got activated.
Then I noticed a button somewhere (I guess it was top left) which indicates the language (or something related to it) so I played with it a bit ,which changed the language of the display (the words written on the screen changed to the other language) unlike (Alt + Shift) which only changed the input language.... but the I noticed that some of the text was not translated... so I pointed that out to him.....

We talked about RTL and LTR languages and how they change the layout, and some characters don't appear as they are intended to be... how the fonts are involved ... etc.

Then I kept clicking the login button repeatedly... so he asked me why??
I tried to explain to him how a miss written if statement could cause the condition to break if you call its code repeatedly.. but he didn't get what I mean...
So,I took the pen, went to the white board and wrote an If statement (from previous experience) that can cause such a condition

This case happened to me once in a Linux course I took a few months before.
(my partner in lab) and I were trying to write an alternating if statement which evaluates the condition different each time {true , false, true, false .... etc} so, we thought we can just divide 1 by any number (in our case was 4) and store it in a variable... then we check if it is 1 else we multiply it by that number...!

x  = 1
y = true

loop
    if x == 1
       y = true
       x /= 4
    else
       y = false
       x *= 4
    endif
    // some code
endloop

now, this code has multiple issues...
1- if you divide by a number then multiply by it, you can't guarantee to get the first number again, due to round off and chopping errors
2- in most programming languages (in this case "bash") this code will result in Integer multiplication and Integer division .... the division will result in zero if this case (1/4 = 0)
3- I don't like this code... it can be cleaner... maybe by using boolean operations or something... anyway we used the number -1 to solve these problems


loop
    if x == 1
       y = true
    else
       y = false
    endif
    x *= -1
    // some code
endloop


So, he understood what I was saying then I went back to the laptop.
I tried every function there is on the screen to see if it does what it is intended to do... even restart :D
I then tried SQL injection (but I knew it wont work :)  just to show him that I know about it) 
I wrote the classic SQL injection code ' or '1'='1' -- '
So, he asked me about it and I explained how it works 
Note: this is a simple SQL injection code, and it rarely work... but it is a good way to demonstrate how SQL injection works and also a good way to show that you understand it.

He asked me will it work??
Me: I don't know!
Him: how would you know??
Me: maybe if I know someone from  the inside, who can tell me if user names and passwords are stored in a SQL database, or if I look at the code or if I walk through the files in the operating system and try to figure out how the data is stored

I then told him about a case that happened to me once, as a friend of mine tried a hacking technique on Windows XP and it worked .... but it only worked on cracked versions of Windows XP, we tried the same technique on an original copy but it didn't work (don't know why)

Then I kept looking around for anything, but didn't find much really and the interviewer didn't ask me for more.

He then started talking to me about testing in general, and how I feel about it.
He then asked me if I had any questions??
So, I did the strangest thing... I asked him a philosophical question ( I decided that putting these questions here is not the best thing to do in this post... so sorry. but I may write about all the philosophical question in some other post  )  

I asked him a philosophical question... which he didn't expect... but he handled it wonderfully.
As we were leaving the interview room.. he had this strange look on his face.. I think it was due to the surprise of the question.


That was all there is.... no more Microsoft interviews.
I hope that you enjoined these posts and benefited from them.. as this was my goal all along.

Friday, May 18, 2012

Face To Face interview 3 (again, A Microsoft interview)


related posts:
the technical interview
the phone interview
Face To Face (Also, A Microsoft interview)
Face To Face 2(yes, you know it.. A Microsoft interview)



It is now time for the 3rd interview at Microsoft....
This interview was somehow more challenging than the others... it had many questions unlike the previous ones and the interviewer was very friendly...

So, at the beginning, the interviewer introduced himself to me and then started right away!

We got to the white board and he started asking..
I don't remember the order of the questions, so, I'll say what comes to my mind first.

Interviewer: write a method that takes a string as a parameter and returns an index to the longest substring such that this substring consists of only one repeated character... eg “doo looo kkkk” would return 8, the index of the “kkkk”

The interviewer wrote on the white board the signature of the method, and I noticed that he represented the string as a char pointer

int longestRepeatedSubString(char * c)

.... or something like that..
So, I looked at it for a while and then said: how about we remove the pointer and just make it an array, and I changed it like this:

int longestRepeatedSubString(char [] c)

It might seem to you that there is not much difference between the two of them, and you might be right... but that if we had agreed that it should be written in C or C++, but by this change I made it more like a Java method, which has no pointers in it, which I like better.

Interviewer: so, you don't want to use pointers??
Me:No, not that …. I'm just trying to make it simpler, but if you want me to use pointers, its ok.... and I tried to change it on the boared, but then he laughed and rewrote it as I wanted!

The implementation is simple:


if(array is empty or null)
return -1

// then the 1st char in array can be the longest so far

maxLen = 1
maxIndx = 0

curMax = 1
curIndx = 0

Loop on the array from char at indx 1
    if it is the same as the previous
        curMax ++
     else
        curMax = 1
        curIndx = indexOfCurrentCharInLoop
    endif
    if curMax > maxLen
        maxLen = curMax
        maxIndx = curIndx
    endif

return maxIndx

This seems about right!! (if you find a bug, don't hesitate to comment,... I wrote this in a couple of minutes!)

While I was writing this, I was thinking out loud, and the interviewer just kept watching to see where I'll go, but he seemed to like the way that I explained what I was writing:

Me: so, we check if the array exist, and if it has chars in it, then we start the real coding...
we know that the array has at least one char, since we already checked the length, and this char can be the 1st longest substring, then we check every char that comes next if it is similar to it and increase the max count else we change the maxIndx!!
This explanation was good for what I was writing, but not for the code you see here....
what happened was that I didn't use curMax , and curIndx in my 1st implementation, only maxLen and maxIndx... which made the algorithm return the index of the last substring, and not what we needed!

The interviewer then notified me that the algorithm doesn't seem right, so I took a second look at it and discovered the “bug”, and then wrote the algorithm the way you see it now (I guess :| )

Then came the testing part.... the interviewer asked me to test it
So, I went like this
Me: we can use an empty string (char array ….. I'll use the word string instead of char array) as parameter and see what comes back..
send a null string, then we can use a one character string.. 2 chars that are the same, 2 that are different, normal strings and so on...

The test case that the interviewer liked was when I said:
Me: and we can even use strings with null characters in them, and maybe the null characters are the longest substring

the white board seemed something like this

a aa xy aaannzzzb aaabbbbc xxx\0yy xxx\0yyyyy xxx\0\0\0\0123

in languages like C, the null character is the end of the string and might break the code if you cast the char array into a string inside your code, or use pointers on the char array, but in Java, where strings are objects, this does not happen. Also char array are object, and have a length value which is used in determining the end of the array not the null character, so Java was a safe bet.

A test case that I don't remember if I said or not, but thought of it while writing this post is trying strings with lower and upper case characters, and see what happens! But the specifications of the method should tell you what to do, other than that, you make assumptions
so something like aaaAAbbbb would return 0 if you ignore case and return 5 if you don't and so on.

The second question was also somewhat easy

Interviewer: write a method that takes 2 strings as parameters, and returns true if the second string is a substring of the first string! (I don't really remember if it returned boolean or int (the starting index) but here we use boolean)

Me: well, that is a very simple question... I actually wrote such a method in assembly in an assignment over a year ago (I like assembly soooo much).... the trick was that when you check a part of the 1st string bu it doesn't match, you return to the character that follows the character you started matching with …. actually I used this case against my friends code and I broke it :) so, if he strings are (“aaacccc” , “aac”) a wrong implementation will return false as it will check the 1st 3 chars of the 1st string “aaa” against the 2nd string “aac” , and finds no match, then it matches the 2nd 3 chars “ccc” against the 2nd string “aac” and finds no match, and so on

the interviewer then asked:

Interviewer: so, how would you test it??
Me: 1st, we can use empty strings as parameters and it should return what ever we agree on (lets say true, as they match, or false, as the strings are empty, but you should tell people who use it (in the documentation) what happens in this case)

Another case is to use null strings, we can also send the second string longer in length than the first one, which should return false by definition, as it is not a substring..... we can use a test case like the one I said at the beginning of the question... we can use a series of method calls to this method where parameters grow in length and see whether the time and memory grow linearly or not...... we can use the null character test here also.

He didn't ask me to implement it.

The 3rd question was actually tricky..

Interviewer: you have 2 sorted arrays, and one of them (say the first array) has empty locations at the end of it enough to put the second array in, but the trick is that the resultant array needs to be sorted, so, how would you implement that??

Me: waw!! you know, I just read that problem a couple of days ago in this book “cracking the coding interview”, and the answer was simple, but I don't really remember it so, I'll try to come up with it..

The interviewer admired my honesty, and then watched me while I try to solve this problem.

My first attempt was to try to compare the 1st 2 elements in both arrays and then swap them to have the smallest in the 1st array, and then move the index to the next element and so on.... I actually couldn't remember the word “swap” and kept explaining it with my fingers till the interviewer said it :)

Then I remembered how it was solved in the book

The solution goes like this: compare the arrays bottom up, meaning compare the last two elements, and put the bigger at the end of the 1st array, and then decrease the index on its array, and so on

so, if we had [1,3,4,6,7,-,-,-,-] and [-1,2,5,9]
we compare 9 and 7, then the greater (9) is put in the array [1,3,4,6,7,-,-,-,9]
then compare 5 and 7 to have
[1,3,4,6,7,-,-,7,9]
then compare 5 with 6 t have
[1,3,4,6,7,-,6,7,9]
then 5 with 4 to have
[1,3,4,6,7,5,6,7,9]
then 2 with 4 to have
[1,3,4,6,4,5,6,7,9]
then 2 with 3 to have
[1,3,4,3,4,5,6,7,9]
then 2 with 1 to have
[1,3,2,3,4,5,6,7,9]
then -1 with 1 to have
[1,1,2,3,4,5,6,7,9]
then as we have one of the array finished, we add the remaining of the 2nd array to have
[-1,1,2,3,4,5,6,7,9]

this is a standard merge (but reversed)

and then the expected question:: how would you test it??
we can use null arrays (:|) empty arrays, and some combinations of both, an empty one, and a full one, but here I assume that the arrays must be sorted, so, I wont try to feed it arrays that are not sorted, I also assume that there is enough space at the end of the 1st array
we can call the method with arrays that grow in size each time to see the time and memory management, see if it is linear(and it should be) or did the programmer just added the second array at the end and sorted it!!

He didn't ask me to implement it either.

The final question he asked me was a pure testing question:
He took me to his laptop, and said

Interviewer: let me just open the notepad..
Me: notepad++ ??
interviewer: haha, no, I'm not that cool.
All I was thinking was that he is going to give me a programming question, and ask me to write the code in notepad and compile and run it, but to my surprise, it was much simpler than that..

Interviewer: now, I want you to test the font feature of this program..
Me: !!! umm ok

So, I just wrote some text in the page, and opened the font window from the menu and started playing with it...
Me: well, there are multiple options here, font size, font type etc, so, we can just try all combinations or some of then

Then I closed it to see the results, then I selected some text from all the text in the page, and opened the fonts again, and changed it a bit, and closed to see the results, and strangely the changes affected all text in the page, not the selected text only, so, I pointed that out to him.

The fields that allows you to choose the font size were writable, so I wrote very big values that are not in the drop down menu, and closed to see the effects, and it worked, I then used negative values, which didn't work, it just remained the same, I tried to enter text, but also didn't cause problems

Then I noticed a hyperlink at the bottom

Me: what is that?
Then I clicked it, and it opened a file chooser, where you can load new fonts, so I said that, we can try to choose files that are not fonts, and if it is not possible, we can just rename some files to look like font files and see if it causes a problem or not.
We can also open a font file in a text editor and add some gibberish to it and see if it causes a problem or not (but I didn't actually try any of this, and he didn't seem to want me to).

And that was it... the interview ended here, and I went back to the recruiter for that quick meeting.

I hope that you found this post helpful.

Stay tuned for the last interview at Microsoft soon. 

Tuesday, May 8, 2012

Face To Face 2(yes, you know it.. A Microsoft interview)

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.


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.