主题：求教大家一个算法问题 -- looklook

要建一个万能hash table也要费不少代价。

There are lots of variation of the classic issue.

One variation is: there is a character sequence composed of 26 English alphabets: a-z, assuming all lower case. How to find the duplicate character in the sequence if there is any?

The solution is to use an array of 26 to hold a-z. If there is an array element being written twice, then that\'s the duplicate.

As a matter of fact, this is one of the questions in a Microsoft interview.

bigbug

As for contains() implementation, check out Sun's JDK implementation. I believe it's O(1) as the Javadoc declared.

Well, there are always two solutions for the classic issue. One is the solution you mentioned above, and the other is the one I gave.

bigbug

平均情况为O(n log n)

you sure this is the solution for msft interview question?

if the sequence is continuous (but one missing/duplicating) and bounded, the solution is to take the summation and then get the one missing/duplicating by comparing with the summation of the whole continuous sequence. (actually, i guess one more function, e.g. summation of squres is needed to find the duplicating/missing couple).

Yes, I am sure it's the solution for Microsoft interview question because I had it before and confirmed with the interviewer.