Re: Microsoft Interview Questions

While I doubt that Microsoft is a monolithic entity, so that the
chances of such a question being asked by an interviewer, are about
the same as at any other medium-to-large company doing software, I do
recall that I was asked similar questions when I interviewed there a
deozen years ago or so--in my case, the questions were about
quicksort. More recently, I interviewed at Mathworks and got asked
questions about a hypothetical "pong" style game.

In both cases, the exact question wasn't important other than the
interviewer had familiarity with it. However, my experience is that
it isn't that helpful to go in a non-traditional direction. In my
case, the quicksort question got very sidetracked in how to select the
pivot and the interviewer didn't get to answer his follow up
questions, so it wasn't that successful of an interview, because you
want the interviewer to "get what they want" out of the interview.
In contrast, I actually not only designed but even implemented the
pong game and it worked after fixing one bug--and that was a very
successful interview.

I like solutions where you create an "empty" array and set bits for
"is this there" type problems. You can do that with hashing to get a
roughly O(n) solution to the duplicate problem. However, the
interviewer might be looking for a balanced tree solution, which would
make it O(n log n).

I would use roughly the same approach for the second problem. If the
two strings are permuations, then they must have the same distribution
of characters (e.g. both have 2 a's, 5 b's, 3 c's, ...). So, instead
of using a single bit per array element, use a counter, that is one
has an array of 256 (or whatever your number of characters is)
counters. You count up while processing the 1st string and down on
the 2nd, and you should end with an array of all 0s. You can
terminate early if any element of the array attempts to go negative,
but that's a minor point. It's still O(n). Bonus question, can you
modify this algorithm to work if the problem online (i.e. you have to
process the strings as they go by and can't keep either of them in
memory)? If I were the interviewer at this point, I'd ask, what about
if we are looking at unicode strings?