Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

A short while ago, I have submitted a coding exercise to a potential employer. The response came back the next morning and you can guess what it was from the subject of this post.

I am not totally at loss, but I need another programmer's perspective. Is there anything that jumps out?

The idea of the exercise is simple: I'm given an input file with names of cars, one per line, possibly repeated and in no particular order.

The program should output the same names, except with no repetitions, the number of occurrences listed next to each car, and in order of decreasing repetitions.

Example:

Honda\n Audi\n Honda\n -> Honda 2 \n Audi 1\n

I'd be grateful for any brutally honest feedback.

[Edit 7/31] I'm surprised nobody commented on my usage of i variable in collect_lines. Probably overshadowed by other problems.

#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <algorithm>
#include <cctype>

using namespace std;


// helper functions ///////////////////////////////////////

// reads lines from instream
void collect_lines(istream &in, map<string, int> &lines);

// given lines->num_occurs map, reverses mapping
void reorg_by_count(map<string, int> &lines, 
                    multimap<int, string> &bycount);
///////////////////////////////////////////////////////////




int main(int ac, char* av[])
{
    istream *in;
    map<string, int> *lines = new map<string, int>();
    multimap<int, string> *lines_by_count = new multimap<int, string>();

    if (ac < 2)
    {
        in = &cin;       
    }
    else 
    {
        in = new ifstream(av[1]);
    }

    if (!in->good()) return 1;

    collect_lines(*in, *lines);
    reorg_by_count(*lines, *lines_by_count);

    if (in != &cin)
          {
        ((ifstream *)in)->close();
        delete in;
    }

    cout << "=====================\n\n";

    multimap<int, string>::reverse_iterator it 
        = lines_by_count->rbegin();

    for (; it != lines_by_count->rend(); it++)        
    {
        cout << it->second << " " << it->first << '\n';
    }


    delete lines;
    delete lines_by_count;

    return 0;
}


// Read the instream line by line, until EOF.
// Trim initial space. Empty lines skipped
void collect_lines(istream &in, map<string, int> &lines)
{
    string tmp;

    while (in.good())
    {
        getline(in, tmp);

        int i = 0;

        // trim initial space (also skips empty strings)
        for (i = 0; i < tmp.length() && !isalnum(tmp[i]); i++);
        if (i >= tmp.length()) continue;
        tmp = tmp.substr(i);

        for (i = 0; i < tmp.length(); i++)
        {
            if (!isalnum(tmp[i]))
            {
                tmp[i] = ' ';
            }

            // thus, HoNdA == Honda
            if (i == 0)
            {
                tmp[i] = toupper(tmp[i]);
            }
            else
            {
                tmp[i] = tolower(tmp[i]);
            }
        }

        // and record       the counts
        if (lines.count(tmp) == 0)
        {
            lines[tmp] = 0;
        }

        lines[tmp]++;
    }
}


// given lines->num_occurs map, reverses mapping
void reorg_by_count(map<string, int> &lines, 
                                                                                multimap<int, string> &bycount)
{
    map<string, int>::iterator it = lines.begin();

    for (; it != lines.end(); it++)
    {
      bycount.insert(pair<int, string>(it->second, it->first));       
    }
}
share|improve this question
5  
I think the question is simple and you have put much more coding efforts. I believe in 3 kind of optimizations; "time, space, text"; "text" optimization is called readability. You could have solved this problem with probably 10 lines of code. I won't be able to provide code now; may be tomorrow. –  iammilind Jul 29 '11 at 16:51
1  
Its a good C answer. But its not C++. –  Loki Astari Jul 29 '11 at 18:59
    
Huh? I see references and STL use... –  Thomas Eding Jul 30 '11 at 0:32
5  
@trinithis: C++ is a style. The code may have been using C++ types but the style was C like (not C++ like). The trouble is people think that because both languages have the same basic syntax that moving from one to the other is trivial. I find that converting C programmers to C++ is really difficult because you have to move them past the whole C mindset. Hence I would not consider the above code to be C++. Some people use the term "C with classes" as a distinct language the lies somewhere between C and C++, here people use C++ features but still code with a C style. –  Loki Astari Jul 30 '11 at 0:56
    
Please have proper thread titles like "Critique requested on the program to output the names without repetitions with the number of occurrences in order of decreasing repetitions." - to make other people's lives easier. –  TheIndependentAquarius May 8 '12 at 7:07
add comment

migrated from stackoverflow.com Jul 29 '11 at 16:51

This question came from our site for professional and enthusiast programmers.

15 Answers

Problems I see:

My problem with your code is that you are newing a lot of stuff that should just be objects.

map<string, int> *lines = new map<string, int>();
multimap<int, string> *lines_by_count = new multimap<int, string>();

Both of these should just be plain objects.

map<string, int>        lines;
multimap<int, string>   lines_by_count;

This one fact would have caused you to be rejected. I would have seen this and I would not have read any-further into your code straight onto the reject pile. This fundamental flaw in your style shows that you are not a C++ programmer.

Next the objects you new are stored in RAW pointers. This is a dead give away that you are not an experienced C++ programmer. There should practically never be any pointers in your code. (All pointers should be managed by an object). Even though you manually do delete these two it is not done in an exception safe way (so they can still potentially leak).

You are reading a file incorrectly.

while (in.good())
{
    getline(in, tmp);

This is the standard anti-pattern for reading a file (even in C). The problem with your version is that the last successful read will read upto but not past the EOF. Thus the state of the file is still good but there is now no content left. So you re-enter the loop and the first read operation getline() will then fail. Even though it can fail you do not test for that.

I would expect to see this:

while (getline(in, tmp))
{
    // Line read successfully
    // Now I can processes it
}

Next you are showing a fundamental misunderstanding of how maps work:

    if (lines.count(tmp) == 0)
    {
        lines[tmp] = 0;
    }
    lines[tmp]++;

If you use the operator[] on a map it always returns a reference to an internal value. This means if the value does not exist one will be inserted. So there is no need to do this check. Just increment the value. If it is not their a value will be inserted and initialized for you (thus integers will be zero). Though not a big problem its usually preferable to use pre-increment. (For those that are going to say it does not matter. On integer types it does not matter. But you have to plan fro the future where somebody may change the type to a class object. This way you future proof your code against change and maintenance problems. So prefer pre-increment).

You are doing extra work you don't need to:

// trim initial space (also skips empty strings)
for (i = 0; i < tmp.length() && !isalnum(tmp[i]); i++);

The streams library already discards spaces when used correctly. Also the ';' at the end of the for. This is considered bad practice. It is really hard to spot and any maintainer is going to ask did he really mean that. When you have an empty body it is always best to use the {} and put a comment in their {/*Deliberately empty*/}

Here you are basically lower casing the string.

    for (i = 0; i < tmp.length(); i++)
    {
        if (!isalnum(tmp[i]))
        {
            tmp[i] = ' ';
        }

You could use the C++ algorithms library to do stuff like this:

std::transform(tmp.begin(), tmp.end(), tmp.begin(), ::tolower());
                           //                       ^^^^^^^^^^^ or a custom 
                           //                        functor to do the task

Const correctness.

void reorg_by_count(map<string, int> &lines, multimap<int, string> &bycount)

The parameter lines is not mutated by the function nor should it be. I would expect it to be passed as a const reference as part of the documentation of the function that you are not going to mutate it. This also helps in future maintenance as it stops people from accidentally mutating the object in a way that later code would not expect.

My final thing is I did not see any encapsulation of the concept of a car. You treated it all as lines of text. If you had invented a car object you can define how cars are read from a stream and written to a stream etc. Thus you encapsulate the concept in a single location.

I would have done something like this:
Probably still overkill.

#include <algorithm>
#include <iterator>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <map>
#include <cctype>

class Car
{
    public:
        bool operator<(Car const& rhs) const {return name < rhs.name;}
    private:
        friend std::istream& operator>>(std::istream& stream, Car& self);
        friend std::ostream& operator<<(std::ostream& stream, Car const& self);
        std::string   name;
};
std::istream& operator>>(std::istream& stream, Car& self)
{
    std::string   line;
    std::getline(stream, line);

    std::stringstream linestream(line);
    linestream >> self.name;  // This strips white space

    // Lowercase the name
    std::transform(self.name.begin(), self.name.end(), self.name.begin(), ::tolower);
    // Uppercase first letter because most are proper nouns
    self.name[0] = ::toupper(self.name[0]);
    return stream;
}
std::ostream& operator<<(std::ostream& stream, Car const& self)
{
    return stream << self.name << "\n";
}

//Print out map members
struct MapPrinter
{
    MapPrinter(std::map<Car,int>::value_type const& d): data(d) {}
    std::map<Car,int>::value_type const& data;
};
std::ostream& operator<<(std::ostream& stream, MapPrinter const& item)
{
    return   stream << item.data.second << ":   "  << item.data.first;
}

int main(int argc, char* argv[])
{
    if (argc < 2)
    {    exit(1);
    }
    std::ifstream      cars(argv[1]);
    std::map<Car,int>  count;

    Car  nextCar;
    while(cars >> nextCar)
    {
        ++count[nextCar];
    }

    // PS deliberately left the sorting by inverse order as an exercise.
    std::copy(count.begin(),
            count.end(),
            std::ostream_iterator<MapPrinter>(std::cout));
}
share|improve this answer
9  
+1 Many good points, like const correctness. Creating a Car object, however, is--in my mind--overkill. –  Adrian McCarthy Jul 29 '11 at 20:16
2  
@Adrian McCarthy: I like the Car object as it lets me do this: while(cars >> nextCar) which is very intuitive to read. (If this was a bigger program) then it also it centralized the code where we read a car from a stream. So if we modify the representation of a car we only have to modify one piece of code and all loops will still work. –  Loki Astari Jul 29 '11 at 23:02
    
@Martin Thanks for a generously informative answer. (BTW, EVERYONE, thanks for your time). Martin, in my "defense" (well, not really) I've seen a lot of raw pointers in production code :) Or should I say :( –  Jozin S Bazin Jul 31 '11 at 20:38
1  
@Jozin S Bazin: There is a lot of C code that pretends to be C++ (AKA C with classes). –  Loki Astari Jul 31 '11 at 22:24
2  
@Seth Carnegie: Find an article on RAII. In my opinion this is the MOST important concept in C++ that must be learned. –  Loki Astari Aug 2 '11 at 14:23
show 2 more comments

You're doing manual memory management. That's not a good idea. In fact, that's something that you don't need to do at all in modern C++. You either use automatic objects, or use use smart pointers to dynamically allocated objects.

In your case, there's no need to do dynamic allocation at all. Instead of:

map<string, int> *lines = new map<string, int>();
multimap<int, string> *lines_by_count = new multimap<int, string>();
// more things
delete lines;
delete lines_by_count;

You should have just used automatic objects:

map<string, int> lines;
multimap<int, string> lines_by_count;
// things

The same goes for the ifstream you used. This clearly shows you don't understand one of the most important facets of C++.

share|improve this answer
8  
I think this is probably the biggest one. If their prospective employer is looking for C++ skills, using pointers and new all the time shows exactly the opposite. –  Brendan Long Jul 29 '11 at 18:36
19  
Agreed. Having been the interviewer, I'll share my thoughts with you. When I see this kind of code, I think "This person doesn't understand stack vs heap, references, or memory management in general. They probably learned Java first, and then tried to jump into C/C++." (Note that I don't hate Java, I just speculate on why this code was written this way). Based on the code, I assume large gaps in the coder's knowledge, and move on. Since you posted here, asking what's wrong, I assume you actually want to learn, which is a very good quality in a coder. Good luck to you. –  Tim Jul 29 '11 at 18:58
4  
oh, and your for loop. You declared the iterator before the loop and left the first part of the for blank, when there was no need to do that. –  Tim Jul 29 '11 at 19:01
7  
@Tim: There's no NEED to put the iterator declaration inside the for loop control region either, and this way the lines are shorter and easier to read. –  Ben Voigt Jul 29 '11 at 19:41
5  
@Ben: You can insert line breaks inside the for statement. And the needlessly extended scope of the iterator is far worse than any long line could ever be –  Fabio Fracassi Aug 1 '11 at 8:56
show 2 more comments

As one of the commenter I believe this could be done in a few, say 10 lines, of code. Writing to long methods is often a sign that one is doing something wrong.

My point is that the sheer size will make the interviewer say it's not good enough. I imagine they want a short clean piece of code that does what they asked for, and not every trick in the book to show off.

on @Martinho suggestion I add my example here

#include <iostream>
#include <list>
#include <map>

using namespace std;

bool my_pair_compare(pair<string,int> &a, pair<string,int> &b) { 
  return a.second > b.second; 
}

void my_pair_output(pair<string,int> &p) { 
  cout << p.first << " " << p.second << endl; 
}

int main() {
  map<string,int> cars;

  while (1) {
    string name;
    cin >> name;
    if (cin.eof()) break;
    cars[name]++;
  }

  list<pair<string,int> > names;

  map<string,int>::iterator citer = cars.begin();
  while (citer != cars.end()) 
    names.push_back(*citer++);

  names.sort(my_pair_compare);
  for_each(names.begin(), names.end(), my_pair_output);

  return 0;
}
share|improve this answer
3  
I didn't downvote, but I would be interested to see those 10 lines :) –  BЈовић Jul 29 '11 at 17:31
    
Here is a gist (35 lines total, ~10 active lines) –  epatel Jul 29 '11 at 19:10
    
@epatel: post the gist in the answer! –  R. Martinho Fernandes Jul 29 '11 at 20:16
3  
Wow! It's at least half shorter than the solution I thought! Thanks for the good programming techniques you displayed! –  Fezvez Jul 30 '11 at 1:34
2  
The list would be better replaced with a vector, then std::sort() instead of .sort(). –  Jon Purdy Jul 30 '11 at 19:39
show 1 more comment

I assume it works, but didn't try it. I would consider it not finished. In an interview situation, they will want you to do your best, and it's more about proving that you are aware of things like checking return status, and doing the right thing, even though the problem at hand is small, and can be dashed off quickly, they probably still want to see a complete program.

Here's what stood out to me:

  • Should use 'argc', 'argv' names for familiarity.
  • lines and lines_by_count are constructed on the heap for no reason - should just use the stack.
  • No allocations are checked.
  • Processes command line arguments, doesn't either (a) complain about excess arguments or (b) use them.
  • No usage or '-help' support.
  • Code contains assumptions about ASCII input, but doesn't declare that.
  • Error handling just quits with no message.
share|improve this answer
13  
"No allocations are checked" new throws, there's nothing to check. Of course, he shouldn't be using new... –  ildjarn Jul 29 '11 at 17:25
3  
This is kinda a tangent and I'll probably get flamed for my heretic view but I would say in most programs (including this) checking allocations is not necessary. It's an extremely rare occurrence that they fail, and when they do in 99.9% of cases you want to crash. In 99.9% of cases (excluding absurd implementations of undefined behavior) the difference is simply crashing with or without an error message. If the computer is out of memory, a lot of applications will crash at the same time, most with segfault-like error messages, so it should be clear to the user what's going on –  Andreas Bonini Jul 29 '11 at 21:04
    
Also don't misunderstand what I said; for big applications an allocation failure check in the application's global allocation manager is certainly a good idea. I'm just saying that for small applications like this it's just overkill. –  Andreas Bonini Jul 29 '11 at 21:06
    
For small applications, yes, it is overkill, I agree. But for an interview question? You do it by the book. –  Paul Beckingham Jul 30 '11 at 1:19
2  
@Andreas: "If the computer is out of memory, a lot of applications will crash at the same time, most with segfault-like error messages, so it should be clear to the user what's going on" <- The idea that the computer is out of memory when allocations fail for "out of memory" is bogus. Because an application does not have enough free contiguous memory in its address space it doesn't mean no one else has. –  R. Martinho Fernandes Jul 30 '11 at 21:33
add comment

I'd be grateful for any brutally honest feedback.

The code is 5 times longer than it needs to be, thanks in part to superfluous code which does things that weren't called for in the specification.

You need 3 or 4 lines of code to read the lines into a map. You use 40 doing things like... recapitalizing, but only the first word in each brand name, for no apparent reason, without explanation. You also strip out any non-alphanumeric characters, which will break brand names like Mercedes-Benz or Rolls-Royce, again without explanation.

The comments are somewhat poor/inconsistent. Comments should tell the reader something the code doesn't. For instance, you explain that you're stripping leading space from each line (something the code already tells us), but don't explain why you aren't stripping trailing space (something we can't read in the code).

Variable names like tmp are also poor (with a few exceptions, like perhaps a swap routine). We know the variable is temporary because of it's scope. The name should tell us what it's for. In this case, it contains the line we're reading, so a name like line would have been better.

As others have pointed out, you're also allocating objects on the heap for no apparent reason. You delete them at the end of main, but not in your early return, which is a huge red flag (given that this is a major source of headaches in C++).

You also have some code that shows you're unfamiliar without how standard library classes work (like assigning 0 to a map entry which is already 0).


As soon as I read the problem description, I alt-tabbed to my editor and wrote this program. I ended up with almost exactly what epatel posted (although his code is broken for multi-word auto names). I haven't been a C++ programmer in nearly 10 years, so I don't know if there's some new fangled stuff I don't know about (lamdas would help here), but the company was probably looking for something straightforward and succinct.

share|improve this answer
add comment

Here are problems that I detected :

  • do not use raw pointers. There is rarely a need for a raw pointer in c++. If you must, use smart pointers.
  • what is the point of multimap? You could that map variable that you defined.
  • use of c casts is bad (in this line : ((ifstream *)in)->close();)
  • the collect_lines function is too complex and does too much.
share|improve this answer
    
More importantly, there's no reason to use pointers at all in this code. –  Brendan Long Jul 29 '11 at 18:06
    
@Brendan: Actually, since the stream is polymorphic, pointers are helpful. But dynamic allocation is still not needed. –  Ben Voigt Jul 29 '11 at 18:44
add comment

This is an interesting exercise.

It's interesting because no sensible person would solve this problem in C++. For the very simple reason that the solution in shell script is:

sort cars.txt | uniq -c | sort -rn

Or, if you insist on counts following names:

sort cars.txt | uniq -c | sort -rn | sed 's/ *\([0-9]*\) \(.*\)$/\2 \1/'

Platforms that aren't unix will have other tools that could be used to solve it.

So, were they trying to see if you'd come up with a sensible non-C++ solution, or was this a pointless task that was being used purely to see what sort of code you write?

share|improve this answer
2  
An answer like this definitely deserves some extra points (if you also give a c++ solution) but you have to understand it's a small exercise. Can you come up with a good task that doesn't take to much time to code and can be used to measure your coding skills, yet it's only solvable with C++ and not with shell script, python or ruby? Can you come up with something that's not a pointless task? –  yi_H Jul 30 '11 at 23:13
    
Fair point. The test we give people at my company (in Java) involves a small but realistic already-existing class that's part of an imaginary web application - a registration handler, in fact, which takes a username and password and creates an account. We ask interviewees to add some more features to it. I don't think that's pointless (perhaps only because J2EE doesn't provide this out of the box, but should!). –  Tom Anderson Jul 31 '11 at 17:00
    
@Tom Pointless task. Thanks! –  Jozin S Bazin Jul 31 '11 at 20:23
add comment

Yes to everything that was said so far. One additional thing which I saw is:

// and record       the counts
if (lines.count(tmp) == 0)
{
    lines[tmp] = 0;
}
lines[tmp]++;

Everything except the last line is unnecessary. When lines[tmp] is accessed for the first time, the key tmp is automatically created in lines, and initialized with the default-constructed value of int (which happens to be 0). See http://en.cppreference.com/w/cpp/container/map/operator_at

share|improve this answer
add comment

@Martinho's comments are on target (as is usual for him), but I think there's more to it than just that. @iammilind and @epatel may have a bit ambitious hoping for 10 lines of code, but based on code I posted in a previous answer meeting similar requirements, I'd guess around 15 to 20 could be fairly reasonable.

I'm also less than enthused about how you've organized your code. In particular, I dislike having collect_lines not only reading input and putting it into the map, but also trimming leading white space and doing name-style capitalization. Absent a specific requirement to do so, I'd probably skip those for an interview question, but if they are required they should be in separate functions.

share|improve this answer
    
10 or 15, think we are in the same ballpark at least ;) got a question of what I was thinking of so made a gist (35 lines total, ~10-15 active lines) –  epatel Jul 29 '11 at 19:48
add comment

Why do these return void?

// reads lines from instream
void collect_lines(istream &in, map<string, int> &lines);

// given lines->num_occurs map, reverses mapping
void reorg_by_count(map<string, int> &lines, 
                    multimap<int, string> &bycount);

There's no need to pass by reference in this case, just do this:

// reads lines from instream
map<string, int> collect_lines(istream &in);

// given lines->num_occurs map, reverses mapping
multimap<int, string> reorg_by_count(map<string, int> &lines);
share|improve this answer
    
pre-C++0x, the pass-by-reference versions will save an expensive copy –  Ben Voigt Jul 29 '11 at 18:43
    
@BenVoigt: I don't think so. RVO and NRVO will likely kick in on functions where the return logic is non-complex. –  DeadMG Jul 29 '11 at 19:06
    
Oh, and in addition, that's quite premature optimization, I'd go for clarity first. In addition, you can "swaptimize" the return value too, if you want. –  DeadMG Jul 29 '11 at 19:22
1  
@DeadMG: Do many compiler even consider RVO and NRVO on functions that aren't inlined? Being defined after use, and fairly long, I'm doubtful that inlining would occur here. –  Ben Voigt Jul 29 '11 at 19:43
    
@Ben Voigt: Modern compilers inline across translation units. A function defined later in the same TU is child's play in comparison. Plus, my points about premature optimization and swaptimization still apply. –  DeadMG Jul 30 '11 at 11:08
add comment

Following @Malvolio idea I guess this task might have been done in AWK.

AWK is made for programs of this kind. It is event driven, for axample it has event handlers for each line and end of file. It also has map data structure and can print to stdout.

share|improve this answer
    
Or shell script. sort cars.txt | uniq -c | sort -rn, and relax. –  Tom Anderson Jul 30 '11 at 18:06
    
@Tom You made my day sir. :) –  user712092 Jul 31 '11 at 10:27
    
Yes, this! Add find for unbridled power. –  Jonathan Watmough Aug 4 '11 at 17:18
add comment

Here is my improvement over epatel's answer.

  • It uses a map instead of a list, as suggested in one of the comments.
  • It uses the standard copy algorithm instead of doing that manually.
  • It imports every name from the std namespace explicitly, to avoid importing unrelated names.
  • The functions my_pair_less and my_pair_output don't modify the pairs, so they get an extra const qualifier for their arguments.
  • The file is read in line by line, which saves a few lines of code and also allows car names that consist of multiple words.

And here's the code:

#include <iostream>
#include <map>
#include <vector>

using std::cin;
using std::cout;
using std::map;
using std::pair;
using std::string;
using std::vector;

bool my_pair_less(const pair<string, int> &a, const pair<string, int> &b) {
  return b.second < a.second;
}

void my_pair_output(const pair<string, int> &p) {
  cout << p.first " " << p.second << "\n";
}

int main() {
  map<string, int> cars;

  string name;
  while (getline(cin, name)) {
    cars[name]++;
  }

  vector<pair<string, int> > names;
  copy(cars.begin(), cars.end(), back_inserter(names));
  sort(names.begin(), names.end(), my_pair_less);

  for_each(names.begin(), names.end(), my_pair_output);

  return 0;
}
share|improve this answer
add comment

Considering that others have already corrected your code I'd like to propose a somehow different approach to the problem.

I think that we can get rid of the extra pass of sorting an auxiliary map/multimap at the end to preserve the decreasing order.

In order to do that we can use a vector that holds car frequency information and a map that links the car name to that vector.

It's much easier to express this in code so here it goes:

#include <string>
#include <iostream>
#include <fstream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main( int numberOfArguments, char** arguments )
{
    typedef map< string, unsigned int > CarEntryMap;

    typedef pair< unsigned int, CarEntryMap::iterator > CarFrequency;

    typedef vector< CarFrequency > CarFrequencyVector;

    fstream file( "C:\\Cars.txt" );

    if( !file.is_open() )
    {
        return 0;
    }

    CarEntryMap carEntries;

    CarFrequencyVector carFrequencies;

    string carName = "";

    while( getline( file, carName ) )
    {
        CarEntryMap::iterator it = carEntries.find( carName );

        if( it == carEntries.end() )
        {
            CarEntryMap::iterator entry = carEntries.insert( it, pair< string, unsigned int >( carName, carFrequencies.size() ) );

            carFrequencies.push_back( CarFrequency( 1, entry ) );
        }
        else
        {
            unsigned int index = it->second;

            pair< unsigned int, CarEntryMap::iterator >& currentEntry = carFrequencies[ index ];

            currentEntry.first++;

            if( index != 0 )
            {
                unsigned int updatedIndex = index;

                for( int i = index - 1; i >= 0; i-- )
                {
                    if( currentEntry.first <= carFrequencies[i].first )
                    {
                        break;
                    }

                    updatedIndex = i;
                }

                if( index != updatedIndex )
                {
                    carFrequencies[ updatedIndex ].second->second = index;

                    currentEntry.second->second = updatedIndex;

                    swap( carFrequencies[ updatedIndex ], currentEntry );
                }
            }
        }
    }

    for( CarFrequencyVector::iterator it = carFrequencies.begin(); it != carFrequencies.end(); ++it )
    {
        cout << it->second->first << " " << it->first << endl;
    }

    return 0;
}

This way, instead of sorting at the end we only swap two entries in vector when the car frequency order changes.

share|improve this answer
add comment

Just to throw out a thought that nobody else mentioned, everybody here is using a map (which as I'm a C# dev I'm imagining that's more or less a dictionary/hashtable of sorts), I would have thought of doing this as a heapsort on a filled in string array from the file, then iterate over it just counting dupes and outputting the previous member with it's count everytime a member doesn't match the previous.

sorry for my lack of C++ but it would be something like, after reading the file or stdin into the array and heapifying it (you may need to implement your own text comparer, not sure on that in C++)

string previousCar = sortedArray[0];
int numberOfConsecutiveDupes = 0;
for(int i = 0; i < length(sortedArray); i++) // Don't know if this is how to retrieve array length in C++ sorry :(
{
    if (sortedArray[i] == previousCar)
    {
        numberOfConsecutiveDupes++;
        continue; // don't know if continue exists in C++?
    }

    SendYourOutputToFileOrWhereverYouWantTo(previousCar + " " + itoa(numberOfConsecutiveDupes)); // itoa, I know this is wrong, I really don't know C++
    previousCar = sortedArray[i];
    numberOfConsecutiveDupes = 1;
}

I realize this would not get anyone the job, I'm just trying to propose a different solution strategy given that they did know C++ syntax/STL/etc (which I def do not)..

share|improve this answer
1  
Everyone is using std::map because it is the textbook example for std::map! An easy while(cin >> name) map[name]++; is enough to read words and count them. Not using a std::map is a clear signal one is not known with C++. –  Sjoerd Oct 29 '11 at 0:43
add comment

Here's what I would answer:

def countCars(fname):
  carCount = {}
  with open(fname, 'r') as f:
    for car in f:
      car = car.strip()
      carCount[car] = 1 + carCount.get(car, 0)
  return carCount

def printCount(carCount):
  items = carCount.items()
  items.sort(lambda a,b:b[1]-a[1])
  for item in items:
    print "%s %d" % item

if __name__ == "__main__":
  import sys
  printCount(countCars(sys.argv[1]))

And then they'd say "That isn't C++" and I'd say "C++ really isn't appropriate for this kind of work, which is an order of magnitude faster to write in higher-level language and runs IO-bound anyway." and then they wouldn't hire me and I'd go work at a company that uses languages that aren't old enough to rent a car.

Go ahead, flame away, what do I care...

Later: The thought occurs, maybe the hiring company didn't specify the language and that was the OP's mistake, choosing a Reagan-era hold-over like C++.

share|improve this answer
1  
Python? Pshaw! Nobody's even heard of the Web when that old language was invented. You should be using Clojure, or Go. They're so much newer! Never mind relevance in the real world, amirite? –  Mud Jul 30 '11 at 4:39
    
@Mud -- in (some degree of) seriousness, I wouldn't defend Python as young, I attended the first world-wide Python conference back in 1996 (there were maybe 30 people there) because I was writing a platform for Internet retail, in Python. The next year, I sold it to Microsoft and mind-bogglingly they're still selling it! Clojure and Go aren't bad choices for this problem (although I would argue, no better than Python), and although Mud is sarcastically correct, popularity matters, technical innovation does too. No chars left! –  Malvolio Jul 30 '11 at 14:14
3  
@Malvolio: it's a coding exercise, what did you expect? They have to give some simple task... About higher-level languages: There are zillions of usages of c/C++ where python (and most other languages) would fail: compilers, modern 3d games, audio and video processing, device drivers, desktop apps (your browser, movie player, chat, ...), embedded devices and almost all the implementation of other languages (including python). Ranting about how easier is to solve a simple task like this in a higher-language shows your ignorance and it is alone enough reason not to hire you. –  yi_H Jul 30 '11 at 22:53
    
@yi_H -- What did I expect? Well, call me ignorant but I expect that an exercise in a job interview is relevant to the actual job. So, if the company is writing device drivers or video processing or whatever C++ shines in, then a string processing function is a poor choice of exercises. In my uninformed opinion. –  Malvolio Jul 31 '11 at 10:05
1  
@Malvolio The task apparently was good enough to weed out those that don't know C++ well. –  Sjoerd Oct 29 '11 at 0:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.