На вход подаются два неупорядоченных слайса любой длины. Вернуть их
пересечение с учётом количества повторов: значение, которое встречается
x раз в a и y раз в b, попадает в ответ min(x, y) раз.
func Intersect(a, b []int) []int
Требования
- Количество каждого значения в ответе —
min(x, y). Порядок элементов в
ответе любой.
- Время O(len(a) + len(b)). Дополнительная память — O(min(len(a), len(b))):
счётчики строятся по меньшему слайсу.
- Входные слайсы не меняются.
nil и пустые входы — пустой результат.
Пример
Intersect([]int{40, 12, 8, 9}, []int{15, 9, 20, 40}) // [9 40] или [40 9]
Intersect([]int{2, 2, 2}, []int{2, 2, 2, 2}) // [2 2 2]
Intersect([]int{1, 2, 2, 1}, []int{2, 2}) // [2 2]
Устно: как решить, если оба слайса отсортированы? А если b не помещается
в память и читается потоком?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.