Easyarrayshash
Как найти пересечение двух массивов?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 349 (unique) и 350 (с дубликатами). Самый простой подход — пересечение множеств за O(n+m).
# Уникальные элементы
def intersection(nums1, nums2):
return list(set(nums1) & set(nums2))
# С дубликатами (минимум count каждого)
from collections import Counter
def intersect(nums1, nums2):
c1, c2 = Counter(nums1), Counter(nums2)
return list((c1 & c2).elements())Другие подходы:
- Sort + two pointers — O((n+m) log(n+m)) время, O(1) extra;
- Sort one + binary search — O((n+m) log n);
- Для stream/не помещается в память — external sort или Bloom filter.
Связанные операции: union (|), difference (-), symmetric difference (^).
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.