vk-internship

Project for VK Internship 2019.

В основном каталоге проекта находятся следующие файлы:

• intersection.h - заголовочный файл реализуемой функции.
• intersection.cpp - файл с исходным кодом функции, которая находит количество общих элементов двух массивов int-ов.
• IntersectionTest.h - заголовочный файл класса для тестирования функции из intersection.cpp.
• IntersectionTest.cpp - файл с исходным код класса для тестирования функции из intersection.cpp.
• main.cpp - главная точка входа, запускает написанные тесты из IntersectionTest.cpp для функции из intersection.cpp.

В связи с тем, что "приветствуется, когда решение не зависит от посторонних моделей" (со слов администрации VK Education), я решил не использовать gtest/Boost Test, а написал собственный класс для тестирования.

Сборка и запуск

$ mkdir build
$ cd build
$ cmake ..
$ make
$ ./vk_internship

Задание

Необходимо написать код, который эффективным образом найдёт количество общих элементов в двух массивах int-ов. Можно считать, что элементы внутри каждого массива не повторяются. Уделите внимание случаю, когда один список намного меньше другого по размеру. Кроме того, необходимо написать код, который тестирует правильность алгоритма.

Что будет оцениваться:

1. Правильность работы алгоритма.
2. Скорость работы. Важна не только асимптотика, но и скрытая в ней константа.
3. Полнота тестов. Неправильно написанный алгоритм не должен проходить ваш тест.
4. Читаемость кода.

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

Рекомендуется использовать C++, но другие языки программирования тоже допустимы.