Calculating Most Frequent Number

Q

Can you write a computer code for the following problem:

Given an online stream of infinite numbers, print out the most frequent number.

✍: .fyicenter.com

A

Here is a solution in Java:

import java.io.*;
import java.util.*;
public class MostFrequent {
   public static void main(String[] a) {
      int mapMax = 99; // Most frequent item that appears at least 1% of the time
      int mapSize = 0;
      String hiItem = null;
      Hashtable<String, Long> countMap = new Hashtable<String, Long>();
      try {
         BufferedReader input = new BufferedReader(new FileReader(a[0]));
         String line = null;
         while ( (line = input.readLine()) != null ) {
            String item = line.trim();
            Long count = countMap.get(item);
            long curCount = 1;
            if ( count!=null ) {
               curCount = count.longValue()+1;
               countMap.put(item, curCount);
            } else {
               if ( mapSize==mapMax ) mapSize = freeMapSpace(countMap, mapSize, mapMax);
               countMap.put(item, curCount);
               mapSize++;
            }
            if ( hiItem!=null ) {
               Long hiCount = countMap.get(hiItem);
               if ( hiCount==null || hiCount.longValue()<curCount ) hiItem = new String(item);
            } else {
               hiItem = new String(item);
            }
            System.out.println("Most frequent item: "+hiItem);
         }
         input.close();
      } catch (Exception e) {
         e.printStackTrace();
      }
   }
   public static int freeMapSpace(Hashtable<String, Long> countMap, int mapSize, int mapMax) {
      while ( mapSize==mapMax ) {
         Enumeration<String> items = countMap.keys();
         while(items.hasMoreElements()) {
            String item = items.nextElement();
            Long count = countMap.get(item);
            if ( count.longValue() <= 1 ) {
               countMap.remove(item);
               mapSize--;
            } else {
               countMap.put(item, count.longValue()-1);
            }
         }         
      }
      return mapSize;
   }
}

2013-12-19, 2278👍, 0💬