LINQ Ruined My Favorite Interview Question

Re:LINQ Ruined My Favorite Interview Question by navinp1912 on Friday July 12, 2013 @12:11AM (#6030874)

     string s,f;
     map<string,int> M;
     set<pair<int,string> > S;
     while(cin >> s) {
             M[s]++;
             int x=M[s];
             if(x>1) S.erase(make_pair(x-1,s));
             S.insert(make_pair(x,s));
     }
     set<pair<int,string> >::reverse_iterator it=S.rbegin();
     int topK=10;
     while(topK-- && (it!=S.rend())) {
             cout << it->second<<" "<<it->first<<endl;
             it++;
     }

[ Parent | on HN ]

Re:LINQ Ruined My Favorite Interview Question by kragen on Friday July 12, 2013 @03:09AM (#6031310)

Not bad. I think it would be a little simpler and faster with:

    while (cin >> s) M[s]++;
    for (map<string,int>::iterator i = M.begin(); i != M.end(); i++) {
             S.insert(make_pair(i->second, i->first));
    }

But maybe there's a downside to that approach that isn't obvious to me?

[ Parent | on HN ]

Re:LINQ Ruined My Favorite Interview Question by navinp1912 on Friday July 12, 2013 @07:40AM (#6032057)

If you move what while (topK--) into the map loop , it becomes an online code for topK whereas what you wrote is an offline . If you want offline then pushing it into a priority_queue and then popping it out would be much faster.

[ Parent | on HN ]