Pull to refresh

Тестовое задание C++, функтор для сортировки

Reading time 6 min
Views 23K
image
Для поиска талантливых программистов написал тестовое задание C++. Вкратце, сложность задачи состоит в передачи дополнительных данных в функцию сравнения, которая используется сортировкой из стандартной библиотеки.
Из википедии:
Функциональный объект (англ. function object), так же функтор, функционал и функционоид — распространённая в программировании конструкция, позволяющая использовать объект как функцию. Часто используется как callback, делегат, либо как замена лямбда-выражениям в нефункциональных языках программирования.

Данное тестовое задание не требует знания решения сходу, хотя опытный программист, думаю, запросто так и сделает. Разрешается использовать интернет. Я без подсказки на stackoverflow не мог найти красивое решение. Цель задания — понять, умеет ли соискатель читать код, находить решения поставленных задач.


Консольная программа на C++ состоит из одного файла main.cpp из 150 строк. Наполняем условную базу данных работников. Есть классы Person (человек), Job (место работы), Position (должность).

#include <string>

struct Person{
    Person();
    Person(const string& _lastName, const string& _firstName, int _age, int _job_id, int _position_id);
    string lastName;
    string firstName;
    int age;
    int job_id;
    int position_id;
};

struct Job{
    Job();
    Job(const string& _name, int _id);
    string name;
    int id;
};

struct Position{
    Position();
    Position(const string& _name, int _id);
    string name;
    int id;
};


Класс PersonsList хранит список людей в std::vector, а места работы и должности в map-ах, которые индексируются по id. Класс Person ссылается на Job и Position по их id.

#include <vector>
#include <map>

class PersonsList{
public:
    void addPerson(const Person& person);
    void addPosition(const Position& position);
    void addJob(const Job& job);

    void print();

    void sortByName();
    void sortByAge();
    void sortByJob();

private:
    std::vector<Person> persons;
    std::map<int,Job> jobsMap;
    std::map<int,Position> positionsMap;
};


В программе реализована функция сортировки по именам с помощью статической функции сравнения и std::stable_sort.

#include <algorithm>

bool compareByName(const Person& person1, const Person& person2){
    if(person1.lastName==person2.lastName){
        return person1.firstName<person2.firstName;
    }
    return person1.lastName<person2.lastName;
}

void PersonsList::sortByName(){
    stable_sort(persons.begin(),persons.end(),compareByName);
}


В main'е идет наполнение базы данных, сортировки и вывод результатов в консоль.
int main()
#include <iostream>

int main()
{
    PersonsList list;

    Job google("Google",1);
    Job microsoft("Microsoft",2);
    Job hp("Hewlett-Packard",3);

    list.addJob(google);
    list.addJob(microsoft);
    list.addJob(hp);

    Position junior("Junior developer",1);
    Position senior("Senior developer",2);
    Position manager("Manager",3);

    list.addPosition(junior);
    list.addPosition(senior);
    list.addPosition(manager);

    list.addPerson(Person("Ivanov","Ivan",21,google.id,junior.id));
    list.addPerson(Person("Sidorov","Nikolay",28,google.id,senior.id));
    list.addPerson(Person("Ivanov","Maxim",28,google.id,manager.id));

    list.addPerson(Person("Volkova","Katerina",22,microsoft.id,junior.id));
    list.addPerson(Person("Demidov","Vitaly",35,microsoft.id,manager.id));

    list.addPerson(Person("Bodrov","Boris",40,hp.id,senior.id));

    list.sortByName();
    cout<<"Sorted by name:"<<endl;
    list.print();

    cout<<endl;

    list.sortByAge();
    cout<<"Sorted by age:"<<endl;
    list.print();

    cout<<endl;

    list.sortByJob();
    cout<<"Sorted by job:"<<endl;
    list.print();

    return 0;
}



В исходникках, которые я привел выше, я упустил реализацию множества функций. Для интересующихся, полный исходник:

Полный исходник
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

struct Person{
    Person():lastName("noname"),firstName(""),age(0),job_id(0),position_id(0){}
    Person(const string& _lastName, const string& _firstName, int _age, int _job_id, int _position_id)
        :lastName(_lastName),
          firstName(_firstName),
          age(_age),
          job_id(_job_id),
          position_id(_position_id)
    {}
    string lastName;
    string firstName;
    int age;
    int job_id;
    int position_id;
};

struct Job{
    Job():name("invalid job"),id(-1){}
    Job(const string& _name, int _id):name(_name),id(_id){}
    string name;
    int id;
};

struct Position{
    Position():name("invalid position"),id(-1){}
    Position(const string& _name, int _id):name(_name),id(_id){}
    string name;
    int id;
};

bool compareByName(const Person& person1, const Person& person2){
    if(person1.lastName==person2.lastName){
        return person1.firstName<person2.firstName;
    }
    return person1.lastName<person2.lastName;
}

class PersonsList{
public:

    void addPerson(const Person& person){
        persons.push_back(person);
    }
    void addPosition(const Position& position){
        positionsMap[position.id]=position;
    }
    void addJob(const Job& job){
        jobsMap[job.id]=job;
    }

    void print(){
        for(int i=0;i<(int)persons.size();i++){

            Person& person=persons[i];

            Job& job=jobsMap[person.job_id];
            Position& position=positionsMap[person.position_id];

            cout << setfill (' ') << std::setw (15) << person.lastName;
            cout << setfill (' ') << std::setw (10) << person.firstName;
            cout << setfill (' ') << std::setw (5) << person.age << " years";
            cout << setfill (' ') << std::setw (20) << job.name;
            cout << setfill (' ') << std::setw (20) << position.name;
            cout << endl;
        }
    }

    void sortByName(){
        stable_sort(persons.begin(),persons.end(),compareByName);
    }

    void sortByAge(){
        // ================================================= TODO
        // programmer also want to change something else, not only this fucntion



    }

    void sortByJob(){
        // ================================================= TODO




    }

private:
    std::vector<Person> persons;

    std::map<int,Job> jobsMap;
    std::map<int,Position> positionsMap;
};

int main()
{
    PersonsList list;

    Job google("Google",1);
    Job microsoft("Microsoft",2);
    Job hp("Hewlett-Packard",3);

    list.addJob(google);
    list.addJob(microsoft);
    list.addJob(hp);

    Position junior("Junior developer",1);
    Position senior("Senior developer",2);
    Position manager("Manager",3);

    list.addPosition(junior);
    list.addPosition(senior);
    list.addPosition(manager);

    list.addPerson(Person("Ivanov","Ivan",21,google.id,junior.id));
    list.addPerson(Person("Sidorov","Nikolay",28,google.id,senior.id));
    list.addPerson(Person("Ivanov","Maxim",28,google.id,manager.id));

    list.addPerson(Person("Volkova","Katerina",22,microsoft.id,junior.id));
    list.addPerson(Person("Demidov","Vitaly",35,microsoft.id,manager.id));

    list.addPerson(Person("Bodrov","Boris",40,hp.id,senior.id));

    list.sortByName();
    cout<<"Sorted by name:"<<endl;
    list.print();

    cout<<endl;

    list.sortByAge();
    cout<<"Sorted by age:"<<endl;
    list.print();

    cout<<endl;

    list.sortByJob();
    cout<<"Sorted by job:"<<endl;
    list.print();

    return 0;
}



Тестовое задание состоит в реализации сортировки по месту работы, причем не по id, а по названию. Сложность в том, что в std::stable_sort третим параметром передается функция, которая принимает только 2 элемента для сравнения. Поскольку указатель на класс не передается, то эта функция не может быть методом класса, а только статической. Разрешается менять код в любом месте.

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

bool compareByJobName(const Person& person1, const Person& person2, PersonsList* list){
    Job& job1=list->getJobById(person1.job_id);
    Job& job2=list->getJobById(person2.job_id);
    return job1<job2;
}

class sorter {
      PersonsList* listPointer;
public:
      sorter(PersonsList* _listPointer) : listPointer(_listPointer) {}
      bool operator()(const Person& person1, const Person& person2) const {
            return compareByJobName(person1, person2, listPointer );
      }
};

void PersonsList::sortByJob(){
    stable_sort(persons.begin(),persons.end(),sorter(this));
}

Tags:
Hubs:
-11
Comments 14
Comments Comments 14

Articles