Re: Microsoft Interview Questions
 From: "Le Chaud Lapin" <jaibuduvin@xxxxxxxxx>
 Date: 20 Jan 2007 16:32:59 0800
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 worstcase 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 RedBlack or AVL tree", in which case
O(nlogn).
My guess is that AVL/RedBlack BST O(nlogn) would be an acceptable
answer.
Le Chaud Lapin
.
 FollowUps:
 Re: Microsoft Interview Questions
 From: Bryan Olson
 Re: Microsoft Interview Questions
 From: Ben Pfaff
 Re: Microsoft Interview Questions
 References:
 Microsoft Interview Questions
 From: kool_guy
 Re: Microsoft Interview Questions
 From: Chris Smith
 Microsoft Interview Questions
 Prev by Date: Re: Microsoft Interview Questions
 Next by Date: Re: Microsoft Interview Questions
 Previous by thread: Re: Microsoft Interview Questions
 Next by thread: Re: Microsoft Interview Questions
 Index(es):
Relevant Pages
