Re: Microsoft Interview Questions

Chris Smith wrote:
kool_guy <yjaplomb@xxxxxxxxx> wrote:
I went to Redmond, WA for Microsoft interview, but got stumbled upon
two interview questions, I hope our experts can answer them for me.

Q1) You are given a set of n numbers, what is an efficient way to
determine whether there is any duplicate in the set? And what is your
run time? (Note: You are not allowed to sort the numbers first.)

No one seems to have addressed this part yet. In general, this is
called the element uniqueness problem. Under the algebraic decision
tree model, it has a worst-case complexity of O(n log n), which suggests
that you may as well do it by sorting and then scanning for duplicates.

Of course no one can read the mind of the Microsoft person who posed
the question, but I would think that the "no sorting allowed"
stipulation would be to prevent the candidate from sorting the numbers
in a fixed array, then doing a scan, which would yield O(n).

If something were known about the distribution of the numbers in set, a
hash function based on linear transformation might yield fast lookup
in a hash table, which would then yield O(n).

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

My guess is that AVL/Red-Black BST O(nlogn) would be an acceptable

-Le Chaud Lapin-