Re:Lessons from 3,000 technical interviews
by SomeStupidPoint on Thursday December 29, 2016 @03:25PM
(#13279826)
Again, you're assuming count has a bound size per word, which isn't true for an unbounded stream.
Step 3 of your algorithm either requires unboundedness of count (ie, count can use arbitrary amounts of memory) or can overflow on arbitrary length streams of words (and hence, has cases where it produces the wrong output).
You only need one counter per word.
a quick sketch of the basic algorithm is:
This algorithm is O(N) space where N is the number of distinct items, as I mentioned previously.