2

Possible Duplicate:
Finding the max repeated element in an array

If there is a word stream, with one word having an occurrence rate of 51% or more, how can we find the most frequent word if only string, and an int can be stored in the memory at a time to help us find it.

We can only access each word a single time, since this is a stream.

No specific language is necessary, but this is mainly intended with Java in mind.

Also I'm not asking for code, just the idea. :)

Community
  • 1
  • 1
GG GG
  • 23
  • 1
  • 3

1 Answers1

0

For completeness, implementation in Java of the algorithm presented in the duplicate I pointed at, applied to an example:

public static void main(String[] args) throws InterruptedException {
    List<String> list = Arrays.asList("a", "b", "c", "a", "d", "e", "a", "a", "b", "b", "a");
    int counter = 0;
    String mostFrequentWord = "";
    for (String streamed : list) {
        if (streamed.equals(mostFrequentWord)) {
            counter++;
        } else if (counter == 0) {
            mostFrequentWord = streamed;
            counter = 1;
        } else {
            counter--;
        }
    }
    System.out.println(mostFrequentWord);
}
Community
  • 1
  • 1
assylias
  • 321,522
  • 82
  • 660
  • 783
  • Thank you for your help! Greatly appreciated! I thought I hit a dead end! – GG GG Jul 18 '12 at 18:35
  • I don't believe this works, seems like garbage. Try it against a a b b b a a, I believe the answer will be "b" because it forgets about the first two a's when it switches to b, right? You seriously can't do it without knowing the history (remember every word sent and a count), but if I'm wrong about this I'd love to know how... Seems like the older I get the more often I turn out wrong about things I'm absolutely certain about. – Bill K Jul 19 '12 at 15:54
  • @BillK Before saying it is garbage, you should check your conclusions. Using `a a b b b a a` as an input returns `a` as expected (if you don't believe it, it is fairly easy to check by amending the code and running it). – assylias Jul 19 '12 at 15:56
  • @BillK You should check the duplicate for a complete explanation of how the algorithm works. In particular, this answer: http://stackoverflow.com/a/3740548/829571 for a great visual explanation. – assylias Jul 19 '12 at 15:58
  • 1
    @BillK Note that the algorithm only works if one of the items appears more than 50% of the time. If you have 3 items that appear 30%, 30% and 40% of the time for example, the result is undefined. – assylias Jul 19 '12 at 15:59
  • Okay, sorry, that works. See told you about being wrong alot these days :) – Bill K Jul 19 '12 at 16:01