# Re: Microsoft Interview Questions

*From*: Ben Pfaff <blp@xxxxxxxxxxxxxxx>*Date*: Sat, 20 Jan 2007 09:26:46 -0800

Chris Smith <cdsmith@xxxxxxx> writes:

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.

I'd normally suggest using a hash table. But I'd want some more

information about the particular problem.

--

"...I've forgotten where I was going with this,

but you can bet it was scathing."

--DesiredUsername

.

**Follow-Ups**:**Re: Microsoft Interview Questions***From:*Chris Smith

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

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

- Prev by Date:
**Re: Graph Coloring** - Next by Date:
**Re: Microsoft Interview Questions** - Previous by thread:
**Re: Microsoft Interview Questions** - Next by thread:
**Re: Microsoft Interview Questions** - Index(es):