title: Java: Random element from the most popular category
body: <p>I need to find the most effecient way to find a random element from the most popular category</p>
  
  <p>From</p>
  
  <pre><code>4 Cheese
  1 Olive
  2 Mushroom
  4 Ham
  2 Chicken
  4 Salad
  </code></pre>
  
  <p>I want either <code>Cheese</code> or <code>Ham</code> or <code>Salad</code>. If there are multiple top categories I don't care which category I will get my item from.</p>
  
  <p>On the input I have <code>Iterator&lt;Foo&gt;</code> where <code>Foo</code> implements</p>
  
  <pre><code>Interface Foo {
      int getCategory();
  }
  </code></pre>
  
  <p>My current code looks like this:</p>
  
  <pre><code>Foo getItem(Iterator&lt;Foo&gt; it) {
      Map&lt;Integer, List&lt;Foo&gt;&gt; categoryMap = new HashMap&lt;Integer, List&lt;Foo&gt;&gt;();
      while(it.hasNext()) {
          Foo foo = it.next();
          int category = foo.getCategory();
  
          List&lt;Foo&gt; l = categoryMap.get(category);
          if(l == null) {
              l = new ArrayList&lt;Foo&gt;();
              categoryMap.put(category, l);
          }
  
          l.add(foo);
      }
  
      int longest_list_size = 0;
      int longest_category_id = -1;
  
      Set&lt;Integer&gt; categories = categoryMap.keySet()
  
      for(Integer c:  categories ) {
          int list_size = categoryMap.get(c).size();
          if(list_size  &gt; longest_list_size) {
             longest_list_size = list_size;
             longest_category_id = c;
          }
      }
  
      if(longest_list_size == 0)
          return null;
  
      int r = new Random().nextInt(longest_list_size);
      return categoryMap.get(c).get(r);
  }
  </code></pre>