# Re: Microsoft Interview Questions

*From*: Chris Smith <cdsmith@xxxxxxx>*Date*: Sat, 20 Jan 2007 09:44:19 -0700

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, you're forbidden from sorting, so I would have pressed for a

reason for this restrictions. Do they want to preserve the original

data? If so, then copy it elsewhere and then sort. If it truly is an

entirely arbitrary and unmotivated restriction, then I'd just throw up

my hands and give the obvious n^2 solution, assuming that there's no use

doing more work until I understand the requirements better than they are

willing to explain. After all, anything else you come up with may be

arbitrarily forbidden as well; for example, could you do a merge sort

but just abort as soon as you find a duplicate? That would sort lists

without duplicates, but it wouldn't sort a list if it had a duiplicate.

Would that count as sorting? Until you have a reasonably formed

problem, these semantic games are going to come up.

If you're willing to abandon algebraic decision tree and make additional

assumptions about your input, then you could do it in linear time.

You'd need a better assumption than "numbers", though. Are they

integers? Natural numbers? Constrained to fit within some range?

--

Chris Smith

.

**Follow-Ups**:**Re: Microsoft Interview Questions***From:*Le Chaud Lapin

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

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

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