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 3^rd 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 1^st 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 1^st 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 1^st 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 1^st 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 1^st 3 chars of the 1^st string “aaa” against the 2^nd string “aac” , and finds no match, then it matches the 2^nd 3 chars “ccc” against the 2^nd string “aac” and finds no match, and so on

the interviewer then asked:

Interviewer: so, how would you test it??

Me: 1^st, 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 3^rd 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 1^st 2 elements in both arrays and then swap them to have the smallest in the 1^st 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 1^st 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 2^nd 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 1^st 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.