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

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

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

Я рассмотрел два алгоритма.

Первый работает на основе std::unordered_set, так как вставка и проверка на наличие в нем элемента работают в среднем за O(1), то построив сет на одном из массивов и проверив наличие в этом сете элементов из второго можно найти количество общих элементов за O(n + m), где n и m - размеры массивов. Случай сильно отличающихся массивов по размеру: чтобы сэкономить память и время строю сет на меньшем из двух массивов, также может оказаться, что все элементы меньшего могут быть сразу в начале большего массива, и дальше проверять наличие не имеет смысла, поэтому процесс завершается.

Второй же алгоритм работает при помощи сортировки. Отсортировав меньший массив (опять в угоду случаю сильно отличающихся по размеру массивов) с помощью бин поиска проверяем наличие элементов меньшего массива в большем. Итоговая асимптотика O(n * log n + n * log m), где n - размер меньшего, а m - большего.

Почему два алгоритма? Потому что при особо больших размерах массивов вставка и поиск в сете чаще может работать за линейное время из-за чего скорость работы портится.

• Main - запуск тестов.
• Header алгоритмов.
• Реализация алгоритмов.
• Header тестов
• Реализация тестов

Необходимо написать алгоритм, который приблизительно подсчитывает количество различных чисел в массиве, используя константный объём памяти.

Более формально, надо реализовать класс с двумя функциями:

• void add(int x); — добавить число x к набору;
• int get_uniq_num(); — возвращает приблизительное количество различных чисел, которые были переданы в функцию add.

Ваш класс должен использовать не более 32 Кб памяти.

Для решения задачи подсчета различных элементов используется HyperLogLog. Алгоритм написан на основе описания из источников:

• https://www.hindawi.com/journals/sp/2017/2040865/
• https://stefanheule.com/papers/edbt13-hyperloglog.pdf
• http:https://www.moderndescartes.com/essays/hyperloglog/

По умолчанию разрядность регистра равна 8, но для повышения точности можно её увеличить.

• Main - запуск тестов.
• Header алгоритма.
• Реализация алгоритма.
• Header хешей
• Реализация хешей