Как найти пересечение двух массивов?

Кладёшь первый массив в map[int]bool. Проходишь второй — если элемент есть в map, добавляешь в результат и удаляешь из map (чтобы не дублировать). O(n+m) времени и памяти. Если массивы отсортированы — два указателя: равны → добавить и сдвинуть оба, иначе сдвинуть меньший. O(n+m) времени, O(1) памяти (не считая результата). На собесе обычно спрашивают оба варианта и когда какой лучше.