title: MultiMap Data Structure for constant time ranking
body: <p>let me just say this is a HW project from UC Berkeley, so If you could give me a hint instead of the solution, It'd be great.</p>
  
  <p>The problem is to create a data structure called "YearlyRecord" that maps a word to the number of times it is encountered in an ngram file. Here are the restrictions.</p>
  
  <ul>
  <li>getting the count must be <em>O(1)</em></li>
  <li>getting the number of mappings must be <em>O(1)</em></li>
  <li>"put" must be on average <em>O(log n)</em></li>
  <li>getting the "rank" must be <em>O(1)</em></li>
  <li>counts, which provides a data structure of all of counts in increasing order</li>
  <li>words, which provides a data structure of all words, in the order of counts</li>
  </ul>
  
  <p>Note: "rank" is a function that takes a word and tells me its rank (e.g. <code>1</code>, <code>2</code>, <code>3</code>, <code>4</code>), which is based on the number of occurrences we have of it.</p>
  
  <p>My solutions so far:</p>
  
  <ul>
  <li>Hashmap (word -> count) provides <em>O(1)</em> getCount operation and
  <em>O(1)</em> size operation </li>
  <li>make a private inner class that implements Comparator which compares based on the number of occurrences in the hashmap. Then use
  this comparator as input to a TreeSet of the words. This provides the
  "words" collection, which we can return in <em>O(1)</em> time.</li>
  <li>Make another TreeSet of the counts. This provides an <em>O(1)</em> return of the counts in increasing order.</li>
  <li>rank: Here is where I am stuck. It is clear that rank should be a map as well. I have the words in the TreeSet in increasing order of rank, but no indices to map to.</li>
  </ul>