Task

solution.cpp

#include <algorithm>
#include <cassert>
#include <iostream>
#include <functional>
#include <random>
#include <vector>
#include <unordered_set>


/* C++ 17,  GCC 8 */

using std::vector;

size_t hash_solution(vector<int> const & first, vector<int> const & second) {
    /* Алгоритм работает за время О(n + m)
     * Сохраняем в хеш-таблице значения из наиболее короткого массива, O(n) памяти
     * Проходимся по значением второго массива, если такое значение есть в хеш таблице, тогда добавляем к результату + 1
     * Преимущество перед sort_solution, в большей скорости работы если один из массивов сильно меньше
     * и в том что требуется немного меньше памяти, если мы хотим, чтобы массивы данные в условие были неизменны
     * Но в std::unordered_set большая константа,
     * поэтому если самый короткий из массивов длиннее 100'000 это решение работает плохо
     */
    std::unordered_set<int> a(first.begin(), first.end());
    size_t result = 0;
    for (int x: second) {
        result += a.count(x);
    }
    return result;
}

size_t sort_solution(vector<int> first, vector<int> second) {
    /* Алгоритм работает за время О(n*log(n) + m*log(m))
     * O(n + m) памяти
     * Идем по массиву с меньшими числами пока значения не совпадают, совпали,
     * прибавляем к результату и индексам обоих массивов +1
     */
    sort(begin(first), end(first));
    sort(begin(second), end(second));

    size_t result = 0;
    for (size_t i = 0, j = 0; i < first.size() && j < second.size();) {
        if (first[i] < second[j]) {
            ++i;
        } else if (first[i] > second[j]) {
            ++j;
        } else {
            ++i;
            ++j;
            ++result;
        }
    }
    return result;
}

size_t my_solution(vector<int> const & first, vector<int> const & second) {
    if (first.size() > 200'000 && second.size() > 200'000) {
        return sort_solution(first, second);
    } else if (first.size() < second.size()) {
        return hash_solution(first, second);
    } else {
        return hash_solution(second, first);
    }
}


size_t simple_solution(vector<int> a, vector<int> b) {
    /* Главный недостакток этого решения то что оно медленное когда один массив большой а другой < 200'000
     * Второй недостаток что требует дополнительно памяти О(n), помимо памяти на оба массива
     */
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    vector<int> intersection;

    set_intersection(
        a.begin(), a.end(),
        b.begin(), b.end(),
        back_inserter(intersection)
    );

    return intersection.size();
}

using solution_t = std::function<size_t(vector<int> const & first, vector<int> const & second)>;

void simple_test(solution_t const & solution = my_solution) {
    vector a = {1, 2, 343, 352, 43, 2134, 233, 421};
    vector b = {1, 343233, 2, 421};
    size_t ans_one = solution(a, b);
    size_t ans_two = simple_solution(a, b);

    assert(ans_one == 3);
    assert(ans_two == 3);
}

void zero_result_test(solution_t const & solution = my_solution) {
    vector a = {1, 2, 343, 352, 43, 2134, 233, 421};
    vector b = {1213, 343233, 43122, 21};
    size_t ans_one = solution(a, b);
    size_t ans_two = simple_solution(a, b);

    assert(ans_one == 0);
    assert(ans_two == 0);
}

void same_vectors_test(solution_t const & solution = my_solution) {
    vector a = {1, 2, 343, 352, 43, 2134, 233, 421};
    size_t ans_one = solution(a, a);
    size_t ans_two = simple_solution(a, a);

    assert(ans_one == a.size());
    assert(ans_two == a.size());
}

vector<int> random_vector(size_t size) {
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<int> uni(-2'000'000'000, 2'000'000'000);
    vector<int> v(size);
    for (size_t x = 0; x < v.size(); ++x) {
        v[x] = uni(rng);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    shuffle(v.begin(), v.end(), rng);
    return v;
}

void stress_test(solution_t const & solution = my_solution) {
    std::random_device rd;
    std::mt19937 g(rd());
    size_t ans_one = 0, ans_two = 0;
    for (size_t i = 1; i < 1'000'000'000; i *= g() % 1000) {
        for (size_t j = 1; j < 1'000'000'000; j *= g() % 1000) {
            vector a = random_vector(i);
            vector b = random_vector(j);
            ans_one = solution(a, b);
            ans_two = simple_solution(a, b);
            assert(ans_one == ans_two);
        }
    }
}

int main() {
    //simple_test(your_solution)
    simple_test();
    zero_result_test();
    same_vectors_test();
    stress_test();
    std::cerr << "All test passed\n";
    return 0;
}