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

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

Solutons:


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

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

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

Related Solutions

When should I not kill -9 a process?

Generally, you should use kill (short for kill -s TERM, or on most systems kill -15) before kill -9 (kill -s KILL) to give the target process a chance to clean up after itself. (Processes can't catch or ignore SIGKILL, but they can and often do catch SIGTERM.)...

Default value for UUID column in Postgres

tl;dr Call DEFAULT when defining a column to invoke one of the OSSP uuid functions. The Postgres server will automatically invoke the function every time a row is inserted. CREATE TABLE tbl ( pkey UUID NOT NULL DEFAULT uuid_generate_v1() , CONSTRAINT pkey_tbl...

comparing five integers with if , else if statement

try this : int main () { int n1, n2, n3, n4, n5, biggest,smallest; cout << "Enter the five numbers: "; cin >> n1 >> n2 >> n3 >> n4 >> n5 ; smallest=biggest=n1; if(n2>biggest){ biggest=n2; } if(n2<smallest){ smallest=n2;...

How to play YouTube audio in background/minimised?

Here's a solution using entirely free and open source software. The basic idea is that although YouTube can't play clips in the background, VLC for Android can play clips in the background, so all we need to do is pipe the clip to VLC where we can listen to it...

Why not use “which”? What to use then?

Here is all you never thought you would ever not want to know about it: Summary To get the pathname of an executable in a Bourne-like shell script (there are a few caveats; see below): ls=$(command -v ls) To find out if a given command exists: if command -v...

Split string into Array of Arrays [closed]

If I got correct what you want to receive as a result, then this code would make what you want: extension Array { func chunked(into size: Int) -> [[Element]] { return stride(from: 0, to: self.count, by: size).map { Array(self[$0 ..< Swift.min($0 + size,...

Retrieving n rows per group

Let's start with the basic scenario. If I want to get some number of rows out of a table, I have two main options: ranking functions; or TOP. First, let's consider the whole set from Production.TransactionHistory for a particular ProductID: SELECT...

Don’t understand how my mum’s Gmail account was hacked

IMPORTANT: this is based on data I got from your link, but the server might implement some protection. For example, once it has sent its "silver bullet" against a victim, it might answer with a faked "silver bullet" to the same request, so that anyone...

What is /storage/emulated/0/?

/storage/emulated/0/Download is the actual path to the files. /sdcard/Download is a symlink to the actual path of /storage/emulated/0/Download However, the actual files are located in the filesystem in /data/media, which is then mounted to /storage/emulated/0...

How can I pass a command line argument into a shell script?

The shell command and any arguments to that command appear as numbered shell variables: $0 has the string value of the command itself, something like script, ./script, /home/user/bin/script or whatever. Any arguments appear as "$1", "$2", "$3" and so on. The...

What is pointer to string in C?

argv is an array of pointers pointing to zero terminated c-strings. I painted the following pretty picture to help you visualize something about the pointers. And here is a code example that shows you how an operating system would pass arguments to your...

How do mobile carriers know video resolution over HTTPS connections?

This is an active area of research. I happen to have done some work in this area, so I'll share what I can about the basic idea (this work was with industry partners and I can't share the secret details ๐Ÿ™‚ ). The tl;dr is that it's often possible to identify an...

How do I change the name of my Android device?

To change the hostname (device name) you have to use the terminal (as root): For Eclair (2.1): echo MYNAME > /proc/sys/kernel/hostname For Froyo (2.2): (works also on most 2.3) setprop net.hostname MYNAME Then restart your wi-fi. To see the change, type...

How does reverse SSH tunneling work?

I love explaining this kind of thing through visualization. ๐Ÿ™‚ Think of your SSH connections as tubes. Big tubes. Normally, you'll reach through these tubes to run a shell on a remote computer. The shell runs in a virtual terminal (tty). But you know this part...

Difference between database vs user vs schema

In Oracle, users and schemas are essentially the same thing. You can consider that a user is the account you use to connect to a database, and a schema is the set of objects (tables, views, etc.) that belong to that account. See this post on Stack Overflow:...