Re: Microsoft Interview Questions

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."