# 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 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

O(nlogn).

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

answer.

-Le Chaud Lapin-

.

**Follow-Ups**:**Re: Microsoft Interview Questions***From:*Bryan Olson

**Re: Microsoft Interview Questions***From:*Ben Pfaff

**References**:**Microsoft Interview Questions***From:*kool_guy

**Re: Microsoft Interview Questions***From:*Chris Smith

- 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):