title: C++ design: Given a list of scores of students, get the frequence of scores in order
body: <p>I have a C++ interview question: </p>
  
  <p>Given a list of scores of students, get the frequence of scores in order.
  [use c++ container map]</p>
  
  <p>My idea: put the list of scores into a map with score as key and frequency as value. Before add a key, search it. If a key is new, add it and set its freq as 1. If not, update its freq by ++1.  O(nlgn)</p>
  
  <p>Then, reverse key and value in a new map, in which set freq as key and its score as value.  O(nlgn) because map do sorting itself. </p>
  
  <p>memory: O(n)</p>
  
  <p>It is not very efficient because I have to use 2 maps and do sorting 2 times. </p>
  
  <p>Any comments or ideas are welcome. </p>
  
  <p>Thanks</p>
  
  <hr>
  
  <pre><code>  My code
  
  
      #include &lt;iostream&gt;
      #include &lt;map&gt;
      #include &lt;algorithm&gt;
  
      #include &lt;time.h&gt;
  
    using namespace std;
    const int M =10;
    int A[M] ;
    bool myFunc(pair&lt;int, int&gt; p1 , pair&lt;double, int&gt; p2)
    {
      //return p1.second &gt; p2.second;
    }
  
     int scoreMap(int *A, const int&amp; N)
     {
      if (A == NULL)
              return 1;
      map&lt;int, int&gt; map1;
      map&lt;int, int&gt;::iterator itr;
      int j = 0 ;
      while(j &lt; N)
      {
              int myKey = (A[j]) ;
              itr = map1.find(myKey);
              if (itr == map1.end())
              {
                      map1.insert(pair&lt;int, int&gt;(myKey, 1));
              }
              else
              {
                      ++(itr-&gt;second);
              }
              ++j;
      }
      // print map1
      cout &lt;&lt; "socre \t freq " &lt;&lt; endl;
      for(itr = map1.begin(); itr != map1.end(); ++itr )
      {
              cout &lt;&lt; itr-&gt;first &lt;&lt; "\t" &lt;&lt; itr-&gt;second &lt;&lt; endl;
      }
      // use multimap
      multimap&lt;int, int&gt; map2;
      multimap&lt;int, int&gt;::iterator itr2;
      for (itr = map1.begin() ; itr != map1.end() ; ++itr )
      {
              map2.insert(pair&lt;int, int&gt;((*itr).second, (*itr).first)) ;
      }
  
      // print map2
      cout &lt;&lt; "after sort " &lt;&lt; endl;
      cout &lt;&lt; "freq \t socre " &lt;&lt; endl;
      for(itr2 = map2.begin(); itr2 != map2.end(); ++itr2 )
      {
              cout &lt;&lt; (double)(itr2-&gt;first)/N &lt;&lt; "\t" &lt;&lt; itr2-&gt;second &lt;&lt; endl;
      }
      return 0;
     }
  
     int main()
     {
      int N = 10;  int range=10;
      for (int i = 0 ; i &lt; M ; ++i)
      {
              srand(time(NULL)+rand());
              //A[i] = rand()%range + (double)rand()/INT_MAX;
              A[i] = rand()%range ; // + (double)rand()/INT_MAX;
      //      sleep(1);
      }
      scoreMap(A, M);
      return 0;
     }
  </code></pre>
  
  <p>// EOF</p>
  
  <p>time O(nlgn), space O(n), are there more efficient solutions ? 
  thanks</p>