Как вычислить мощность пересечения множеств

Что проверяют

Знаете ли вы операции над set и их сложность, а не только синтаксис. Задача простая, поэтому её сразу усложняют: а если это списки с повторами, а если множеств десять, а если одно из них огромное.

Как отвечать

Базовый ответ в одну строку: len(a & b). Дальше покажите, что понимаете детали:

• & против intersection(): оператор требует, чтобы оба операнда были set или frozenset, а метод принимает любой итерируемый объект. a.intersection(some_list) сработает, a & some_list упадёт с TypeError;
• сложность: в CPython пересечение идёт по меньшему множеству и проверяет элементы в большем, в среднем O(min(n, m)). Если множества ещё строятся из списков, добавляется O(n + m);
• несколько множеств: set.intersection(*sets), выгоднее начинать с самого маленького;
• проверка на пустоту: a.isdisjoint(b) останавливается на первом общем элементе и не строит результат;
• повторы важны: для мультимножеств берите Counter: sum((Counter(xs) & Counter(ys)).values()), где & берёт минимум счётчиков;
• без хеширования: для отсортированных массивов работает метод двух указателей за O(n + m) и O(1) памяти, это частый уточняющий вопрос.

Упомяните, что элементы множества обязаны быть хешируемыми: список внутрь не положить, кортеж можно.

Если данных миллиарды и нужна оценка, а не точное число, используют вероятностные структуры: MinHash для коэффициента Жаккара и HyperLogLog для мощности объединения. На собеседовании по Python достаточно их назвать.

Где спотыкаются

Пишут вложенный цикл по двум спискам за O(n·m) там, где хватает одной строки с set.

Теряют повторы: len(set(xs) & set(ys)) для [1, 1, 2] и [1, 1] даст 1, хотя по условию могли ждать 2. Уточните у интервьюера, что считается пересечением.

Строят множество из огромного списка ради одного числа. Достаточно множества из меньшей коллекции: small.intersection(big_list) пройдёт по списку без копии в памяти.