Выводить названия машин, без повторений, число повторений в порядке убывания повторений


Некоторое время назад я внес кодирования в потенциального работодателя. Ответ пришел на следующий утро и вы можете догадаться, что это было от темы в этот пост.

Я не совсем в убыток, но мне нужен еще один программист перспективы. Что-нибудь выскакивает?

Идея мероприятия проста: я дан входной файл с названия машин, по одному в строке, возможно, повторялись и в нет определенного порядка.

Программа должна вывести те же имена, за исключением не повторений, количество повторений, указанное рядом с каждой автомобиля, и в порядке убывания повторений.

Пример:

Хонда\Н Ауди\Н Хонда\Н -> Хонда 2 \н Ауди 1\н

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


8225
87
задан 29 июля 2011 в 04:07 Источник Поделиться
Комментарии
15 ответов

Проблемы я вижу:

Моя проблема с вашим кодом заключается в том, что вы представления много вещей, которые просто должны быть объекты.

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

Оба эти должны быть простые объекты.

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

Этот факт вызвал бы вас, чтобы быть отвергнутым. Я бы видел это, и я не прочитал бы любой-далее в коде прямо на мусор. Этот фундаментальный изъян в ваш стиль показывает, что вы не программист на C++.

Следующие объекты, которые вы новые хранятся в сырых указателей. Это мертвый отдать, что вы не опытный C++ программист. Там практически никогда не будет каких-либо указателей в коде. (Все указатели должны быть управляемый объект). Даже если вы вручную не удалите эти два это не делается в исключение безопасным способом (так они еще может течь).

Вы неправильно читает файл.

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

Это стандартный анти-паттерн для чтения файла (даже в C). Проблема вашей версии в том, что последние успешное чтение будет читать до , а не мимо ВФ. Таким образом, состояние файл по-прежнему хорошо, но там сейчас не осталось содержимого. Так что вы вновь войти в цикл и первая операция чтения вызовом getLine() будет потом плохо. Хотя он может подвести вас, не проверяет.

Я бы ожидать, чтобы увидеть это:

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

Далее вам демонстрируют фундаментальное непонимание того, как работают карты:

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

При использовании оператора[] на карте он всегда возвращает ссылку на внутреннее значение. Это означает, что если значение не существует, будет вставлен. Поэтому нет необходимости делать эту проверку. Просто увеличить значение. Если это не их значения будут вставлены и инициализирован для вас (таким образом чисел будет равна нулю). Хотя не большая проблема, ее обычно предпочтительно использовать пре-инкремент. (Для тех, кто собирается сказать, что это не важно. Для целочисленных типов не имеет значения. Но вы должны планировать для будущего, где кто-то может изменить тип объекта класса. Таким образом, вы в будущем свой код от изменения и проблемы обслуживания. Поэтому предпочитаю пре-инкремент).

Вы делаете лишнюю работу вам не надо:

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

Библиотека потоков уже отбрасывает пробелы, когда используется правильно. Также ';' в конце. Это считается плохой практикой. Это действительно сложно и любой ответственный собирается спрашивать, действительно ли он имел в виду. Когда у вас есть пустое тело это всегда лучше, чтобы использовать {} и поставить комментарий в {/*намеренно пусто*/}

Здесь вы в основном нижней части корпуса строку.

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

Вы могли бы использовать библиотеку алгоритмов C++, чтобы делать вещи, как это:

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

Правильность константный.

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

Параметр линии не видоизменяется функцией не следует. Я ожидаю, что он будет принят в качестве константной частью документации функции, которые вы не собираетесь мутировать его. Это также помогает в будущем техническое обслуживание, поскольку это останавливает людей от случайного изменения объекта таким образом, что последующий код не будет ожидать.

Мое последнее дело, я не вижу никакой инкапсуляции концепции автомобиля. Ты поступила как строки текста. Если вы изобрели объекта автомобиля можно определить, как вагоны чтения из потока и записи в поток и т. д. Таким образом, Вы воплощаете понятие в одном месте.

Я бы сделал что-то вроде этого:
Наверное все-таки перебор.

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

94
ответ дан 29 июля 2011 в 07:07 Источник Поделиться

Вы делаете ручного управления памятью. Это не очень хорошая идея. На самом деле, это то, что вам не надо делать вообще в современном C++. Вы либо использовать автоматические объекты, или использовать смарт-указатели на динамически выделенные объекты.

В вашем случае, нет необходимости делать динамическое размещение на всех. Вместо:

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;

Вы должны просто использовать автоматические объекты:

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

То же самое касается ifstream , который вы использовали. Это наглядно показывает, Вы не понимаете один из самых важных аспектов языка C++.

48
ответ дан 29 июля 2011 в 05:07 Источник Поделиться

В качестве одного из комментаторов я считаю, что это может быть сделано в несколько, скажем 10 строк кода. Пишу длинные методы-это часто признак того, что один делает что-то неправильно.

Моя точка зрения заключается в том, что размер сделает интервьюер сказал, что это не достаточно хорошо. Я думаю, что они хотят короткий чистый кусок кода, который делает то, что они просили, и не каждый трюк в книге, чтобы показать.

по предложению @Мартиньо я добавить мой пример здесь

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

16
ответ дан 29 июля 2011 в 05:07 Источник Поделиться

Я предполагаю, что это работает, но не пробовал. Я бы рассматривал его не закончил. В интервью ситуацию, они хотят, чтобы вы сделали ваш самый лучший, и больше, чтобы доказать, что вы в курсе таких вещей, как проверить статус возврата, и делать правильные вещи, даже если проблема небольшая, и может быть накатаю быстро, они, вероятно, все еще хотите ознакомиться с полной программой.

Вот что бросилось в глаза:


  • Должны использовать 'АГДС', 'имена агду' за знакомство.

  • линии и lines_by_count построены на куче без причины - надо просто использовать стек.

  • Проверил, нет средств.

  • Команда обрабатывает аргументы строке Не либо (а) пожаловаться на избыток аргументов или (B) использовать их.

  • Не использование или помочь ей поддержку.

  • Код содержит предположения о входных ASCII, но не заявляю, что.

  • Обработка ошибок просто завершает работу без сообщения.

14
ответ дан 29 июля 2011 в 05:07 Источник Поделиться


Я был бы благодарен за любое честное мнение.

Код в 5 раз больше, чем он должен быть, благодаря, в частности, лишнего кода, который делает то, что не предусмотрено в спецификации.

Вам понадобится 3 или 4 строки кода, чтобы прочитать линии на карте. Вы используете 40 делать такие вещи, как... рекапитализации, но только первое слово в каждой маркой, без видимых причин, без объяснений. Вы также прокладки из любых буквенно-цифровых символов, которые будут нарушать такие бренды, как Мерседес-Бенц и Роллс-Ройс, опять же без объяснения причин.

Комментарии несколько бедных/противоречивы. Комментарии должны сообщить читателю что-то код не. Например, вы объясните, что у вас пробел в каждой строке (что-то код уже говорит нам), но не объясняют, почему вы не обнажая пробелы (то, что мы не можем читать в коде).

Имена переменных, как ТМП тоже оставляет желать лучшего (за редким исключением, как возможно поменять обычной). Мы знаем переменной является временным, потому что это рамки. Название должно сказать нам, что это для. В этом случае, он содержит строки мы читаем, Так что название типа линии было бы лучше.

Как другие указали, вы также выделение объектов в куче без видимых причин. Вы не удалите их в конце основной, но не в начале вернуть, что это огромный красный флаг (учитывая, что это является основным источником головной боли в C++).

У вас также есть некоторый код, который показывает, что вы незнакомы, не как стандартные классы библиотечной работы (например, присвоение 0 до записи карты, которые уже есть 0).


Как только я прочитал описание проблемы, я альт-вкладками, чтобы мой редактор и написал эту программу. Я в конечном итоге с почти точно, что epatel написал (хотя его код разбивается на несколько слов автоматический имена). Я не программист на C++ почти 10 лет, так что я не знаю, если есть какие-то новые новомодные штучки, о которых я не знаю (например, лямбды поможет), но компания, вероятно, искал что-то простое и лаконичное.

10
ответ дан 30 июля 2011 в 05:07 Источник Поделиться

Вот несколько проблем, которые я обнаружил :


  • не использовать сырые указатели. Там редко бывает нужен для необработанного указателя в C++. Если вы должны использовать смарт-указатели.

  • какой смысл Мультикарты? Вы может карте переменные, которые вы определили.

  • использование C бросает плохо (в этой строке : ((ifstream *)в)->закрыть();)

  • функция collect_lines слишком сложная и не слишком много.

8
ответ дан 29 июля 2011 в 05:07 Источник Поделиться

Да все, что было сказано до сих пор. Одна дополнительная вещь, которую я видел:

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

Все, кроме последней строке лишнее. Когда линии[ТМП] осуществляется впервые, ключ ТМП автоматически создается в линии, и инициализируется с по умолчанию значение int (который, оказывается, 0). См http://en.cppreference.com/w/cpp/container/map/operator_at

7
ответ дан 29 июля 2011 в 05:07 Источник Поделиться

Это интересное упражнение.

Это интересно, потому что ни один здравомыслящий человек не позволит решить эту проблему в C++. По очень простой причине, что решение в сценарии оболочки:

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

Или, если вы настаиваете на счету следующих имен:

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

Платформы, которые не в Unix будет иметь другие инструменты, которые могут быть использованы для ее решения.

Таким образом, они пытаются увидеть, если вы придумаете толкового не решением C++, или это бессмысленная задача, которая используется исключительно для того, чтобы увидеть, какой код вы пишите?

6
ответ дан 30 июля 2011 в 06:07 Источник Поделиться

Комментарии @Мартиньо на цели (как это обычно для него), но я думаю, что есть больше, чем просто. @iammilind и @epatel может быть немного амбициозным надеялся на 10 строк кода, но на основе кода, который я написал в предыдущем ответе удовлетворения аналогичных требований, я думаю, около 15 до 20 может быть достаточно разумно.

Я тоже не в восторге о том, как вы организовали свой код. В частности, я не люблю collect_lines не только значение входных и положить его на карту, а также обрезки пробел и делаю название-стиль капитализации. Отсутствует определенное требование, чтобы сделать так, я бы, наверное, пропустить тех, кто на интервью вопрос, но если они необходимы, они должны быть в отдельной функции.

5
ответ дан 29 июля 2011 в 07:07 Источник Поделиться

Почему эти возвращать?

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

Там нет необходимости, чтобы пройти по ссылке в данном случае, просто сделать это:

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

4
ответ дан 29 июля 2011 в 06:07 Источник Поделиться

Вот мое улучшение за ответ epatel по.


  • Он использует карты вместо список, как предложил в одном из комментариев.

  • Он использует стандартный скопировать алгоритм вместо того, чтобы делать это вручную.

  • Он импортирует каждое имя из СТД пространства имен явным образом, чтобы избежать импорта несвязанные имена.

  • Функции my_pair_less и my_pair_output не изменять пары, поэтому они получают дополнительную константный квалификатор для их аргументов.

  • Файл считывается построчно, что позволяет сэкономить несколько строк кода, а также позволяет названий автомобилей, которые состоят из нескольких слов.

И вот код:

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

4
ответ дан 20 августа 2011 в 06:08 Источник Поделиться

После @Мальволио идея, я думаю, эта задача может быть выполнена в Неум.

Awk-это сделано для программ такого рода. Это событийная, для axample он имеет обработчики событий для каждой строки и конца файла. Она также имеет структуру данных карты и можете печатать в stdout.

3
ответ дан 30 июля 2011 в 03:07 Источник Поделиться

Учитывая, что другие уже исправили ваш код я бы хотел предложить несколько иной подход к проблеме.

Я думаю, что мы можем избавиться от лишних проход сортировки вспомогательную карту/Мультикарты в конце, чтобы сохранить в порядке убывания.

Для этого мы можем использовать вектор, который держит частоту автомобильная информация и карта, которая связывает название автомобиля для этого вектора.

Это гораздо легче выразить это в коде, так вот он идет:

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

Таким образом, вместо сортировки в конце мы лишь поменять местами две записи в вектор при изменении частоты автомобиля изменения.

2
ответ дан 1 августа 2011 в 02:08 Источник Поделиться

Просто выкинуть мысли, что никто не упомянул, все здесь через карту (которая, как я на C# разработчика, мне показалось, что более или менее словарь/хэш-таблицы всякие), я бы подумал, что это heapsort как на заполненный массив строк из файла, затем перебрать его просто считая простофилями и вывода предыдущего члена С это граф каждый раз член не совпадает с предыдущей.

извините за мое отсутствие C++, но это будет что-то вроде, после чтения файла или стандартного потока ввода в массив и heapifying его (возможно, вам придется реализовать свой собственный компаратор текст, не уверен, что в 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;
}

Я понимаю, что это не вам кому-либо работу, я просто пытаюсь предложить разные решения, учитывая, что они знали с++ синтаксис/стл/и т. д. (который я, определенно, не)..

-2
ответ дан 30 июля 2011 в 10:07 Источник Поделиться

Вот что я бы ответил:

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

И тогда они сказали бы: "это не C++" и я бы сказал, что "с++ не подходит для такого рода работы, которая на порядок быстрее писать на высокоуровневых языков и работает ИО-связаны так или иначе." и тогда они не будут нанимать меня, и я бы пошел работать в компанию, которая использует языки, которые не являются достаточно стар, чтобы арендовать автомобиль.

Идти вперед, пламя, какое мне дело...

Позже:
Возникает мысль, может быть, при приеме на работу компания не укажите язык, и это было ошибкой ФП, выбирая эпоху Рейгана провести-за таких как C++.

-7
ответ дан 30 июля 2011 в 02:07 Источник Поделиться