I'm going to answer this a bit more meta:
Seeing this question I ask myself: What does the interviewer whatwant to know from me?
Does he expect
- a low-level, highly optimized algorithm (as you are attempting)
- or does he want to see, that I can apply the standard Java API to the problem (as Landei suggests)
- or maybe something in between, like the optimized implementation and use of a multi-set/counted set/bag (as Bart and Scott do)
Possibly the interviewer just expects you to discuss exactly that with him, so that he sees that you know that these alternatives exist and which advantages and disadvantages they have.