Для поиска талантливых программистов написал тестовое задание 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’е идет наполнение базы данных, сортировки и вывод результатов в консоль.
#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 элемента для сравнения. Поскольку указатель на класс не передается, то эта функция не может быть методом класса, а только статической. Разрешается менять код в любом месте.
Вариантов решения множество, и я не претендую на знание оптимального решения. Под спойлером мой вариант решения.
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)); }
ссылка на оригинал статьи http://habrahabr.ru/post/195138/
Добавить комментарий