Challenge: Most Frequent Element

Here’s a nice problem from Notes on Streaming Algorithms:

Suppose we have sequence delim{lbrace}{x_1, x_2, ..., x_n}{rbrace} from a set epsilon, and that we know that one value from epsilon occurs more than n/2 times in the sequence; find the most frequent value using only two variables having total memory of only lg(n) + lg(max value) bits and in only a single sweep.

Spoiler 1
Spoiler 2
Answer

My implementation is in git and below.

Leave a Reply