Re: Microsoft Interview Questions

Ben Pfaff <blp@xxxxxxxxxxxxxxx> wrote:
I'd normally suggest using a hash table. But I'd want some more
information about the particular problem.

Right, so there's another question. Do you want good worst-case running
time, or good average case (or probablistic expected) running time? If
the former, then hash tables are going to run in n^2 time, and are no
better than the obvious algorithm. In the latter case, though, hash
tables can run in O(n) expected/average time, and improve on the n log n
time bound from the worst case.

--
Chris Smith
.

Relevant Pages