Задача с собеседования в Яндекс

Вполне себе прикладная задача, которая может встретиться в проде.
Поисковая формулировка: для двух поисковых выдач, заданных массивами DocId-ов (векторы целых чисел) длины N, для всех k от 1 до N нужно посчитать количество общих документов в топах размера k.

Формальная формулировка: Для двух массивов целых чисел длины N, для всех k от 1 до N, посчитать количество общих чисел на префиксах длины k. Числа в пределах массива могут повторяться, пересечение считается без учета кратности.

Решение:

Пройдемся по префиксу, параллельно поддерживая два хешсета для первого и второго массива с элементами на префиксе. Когда начинаем обрабатывать новый элемент, проверяем его в хешсете второго, если есть то += 1, также для второго. При этом если элемент уже был в префиксе, то прибавлять 1 к ответу не нужно.

int n = A.size();
vector<int> result(n);
unordered_set<int> setA, setB;
int common = 0;

for (int i = 0; i < n; ++i) {
int a = A[i];
int b = B[i];

if (!setA.count(a)) {
setA.insert(a);
if (setB.count(a)) {
common++;
}
}

if (!setB.count(b)) {
setB.insert(b);
if (setA.count(b)) {
common++;
}
}

result[i] = common;
}

Если повторы внутри одного вектора запрещены, то возможно решение с одним хешсетом всех встреченных элементов двух массивов
Нужно отдельно обговорить допускаем ли мы повторы чисел внутри одного вектора. Хорошо, если вы сами спросите об этом на собесе

В результате решение O(N)

@algoses