Re: Microsoft Interview Questions

Ben Pfaff wrote:
"Le Chaud Lapin" <jaibuduvin@xxxxxxxxx> writes:
But if this is for a "regular" engineering position instead of
research, I would imagine that the purpose of the question would be to
probe the candidate to test familiarity with standard data structures
for implementing sets [the kind that Ben Pfaff have done so much work
with. :)]. If the candidate mentions binary tree/O(nlogn) without
asking about the order of extraction from source set of the numbers,
that would be not as good an answer as saying "I do not care about the
order of extraction. I choose Red-Black or AVL tree", in which case

That's an interesting suggestion, but I would have, personally,
guessed that the stipulation "no sorting" applied to other
methods that are equivalent to sorting. The construction of any
kind of binary search tree falls into that category, seeing as
a sorted array can be derived from the BST in O(n) time.

I did consider this fact before posting, but still felt that the
interviewer was looking for a stock answer. It is true that a BST
gives you a sort automatically, but technically speaking, you will know
the answer to Microsoft question either before the numbers are sorted,
or precisely at the point where the last element is inserted, in which
case, if the interviewer were to claim, "you cheated, you implemented a
sort..", the applicant could retort, "I found the answer to your
question without having to perform a sort...first." :)

But again, I doubt that the interviewer was looking for anything beyond
stock, obvious answers.

-Le Chaud Lapin-