Thursday, October 7, 2010

Array sorted by frequency

You are given a large array of integers, output them sorted by frequency. What if the array is too large to fit in memory?
Pubblicato da a
Reazioni: 

1 comment:

  1. With no memory limit, just build a histogram in a hash table then sort all the histogram bins at the end.

    But WITH memory limit, it's a better puzzle. You must have multiple passes.. an example is a list where every integer is unique. After streaming in some number of values, you will have filled your fixed memory size, but you still can't output anything since the very next value may change the (tied) ordering of everything you've seen so far.

    Hmm, but such a finite state algorithm still isn't obvious even when you do allow multiple passes. One terribly ugly algorithm could use N^2 passes to find the POPULATION of the most popular value, then use another N^2 passes to output all the values with that pop, then repeat again finding the max pop that's still less than the last passes.. repeat until all pops are done. But that's O(N^3), ugly ugly!

    ReplyDelete

Subscribe to: Post Comments (Atom)