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
.