Новая задача Яндекса.

Для двух массивов целых чисел длины N, для всех K от 1 до N, посчитать количество общих чисел на префиксах длины K.
Числа в пределах массива могут повторяться, пересечение считается без учета кратности.
Пример
a = [1, 1, 2, 3]
b = [2, 1, 3, 1]

k = 1 ответ 0
k = 2 ответ 1
k = 3 ответ 2
k = 4 ответ 3

Решение:
У тебя есть решение за O(n), но твое решение требует использование две хеш-таблицы (хеш-сета) то к сожалению твое решение не примут.

Нужно завести одну хеш-таблицу, назовем has.
Ключом хеш-таблицы будет число из массивов, а значение будет принимать три значения.
0-если число встречается ТОЛЬКО в первом массиве
1-если число встречается ТОЛЬКО во втором массиве
2-если число встречается одновременно в первом и во втором массиве.

Пройдемся циклом с k = 1 до k=n.
-Если a[k] есть в has и has[a[k]] = 1 то увеличим ответ и сделаем has[a[k]]=2.
-Если has[a[k]] не равен 2 то делаем has[a[k]] = 0
-Если b[k] есть в has и has[a[k]] = 0 то увеличим ответ и сделаем has[a[k]]=2
-Если has[b[k]] не равен 2 то делаем has[b[k]] = 1

Если не понятны выше четыре условия то просто подумайте, а как бы обновляли хеш-таблицу имея новые числа a[k], b[k].

(Эту задачу можно решить разными способами, самое главное использовать один хеш)
Решение O(n).

Код из собеседования в комментариях.