Outputting the names of cars, without repetitions, with the number of occurrences in order of decreasing repetitions

Question

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

#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));       
    }
}

Answer 1

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;}
        friend 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;
        }
        friend std::ostream& operator<<(std::ostream& stream, Car const& self)
        {
            return stream << self.name << "\n";
        }
    private:
        std::string   name;
};

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.
    for(auto const& car: count) {
        std::cout << car.first << ":   " << car.second << "\n";
    }
}

Answer 2

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++.

Answer 3

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;
}

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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?

Answer 8

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

Answer 9

@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.

Answer 10

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);

Answer 11

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;
}

Answer 12

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.

Answer 13

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.

Answer 14

This is my take on this. I used a map and multiset and a sort predicate.

struct sort_pred {
    bool operator()(const std::pair<string,int> &left, const std::pair<string,int> &right) {
        return left.second > right.second;
    }
};

int main()
{
   multiset< pair<string,int> ,sort_pred > myset;
   map<string,int> mymap;
   readfile(mymap);
        for(map<string,int>::iterator it=mymap.begin();it!=mymap.end();it++)
        {
                myset.insert(make_pair<string,int>(it->first,it->second));
        }
        cout<<"Elements in the set:"<<endl;
        for(multiset<pair<string,int>,sort_pred >::iterator it=myset.begin();it!=myset.end();it++)
                cout<<it->first<<" "<<it->second<<endl;
                return 0;
}

void readfile(map<string,int> &t)
{
       string filename="temp.txt";
       ifstream file;
       file.open(filename.c_str());

       if(!file.is_open())
       {
              cerr<<"Error opening file : "<<filename.c_str()<<endl;
              exit(0);
       }

      string line;
      while(getline(file,line))
      {
          if(t.find(line)!=t.end())
                  t[line]++;
                  else
                  t.insert(std::make_pair(line,1));
      }
}

Answer 15

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)..

Answer 16

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++.