[eli_gottlieb]

Err, plenty of answers would get you the job besides sorting, including order insensitive hash functions and tables, neat automata based solutions, etc.

I actually gave hashing/hash-table of a small character-bag of my own making as the first answer. The interviewer then told me to solve the problem "without any [standard-library] data-structures". I had to question that, and was told I had to come up with everything myself, as if writing my own standard library in C. The interviewer was then satisfied when I gave the sorting answer, and I did get the positive call-back.

It was a matter of giving him what he wanted, not necessarily just solving the problem.

[DannyBee]

Your interviewer was an idiot. Again, if this was at google, please let me know privately who it was, and i'll take care of it.