Как реализовать join с повторяющимися ключами в отсортированных списках?

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

Умеете ли вы довести sort-merge join до правильного результата на повторах, а не только на уникальных ключах. Следом просят оценить сложность и объяснить, почему в худшем случае она квадратичная.

Как отвечать

Сначала договоритесь о семантике. Join по ключу с повторами даёт декартово произведение групп: если ключ 2 встречается слева дважды, а справа трижды, в результате шесть пар. Возвращать их удобно как record Pair<L, R>(L left, R right).

Алгоритм на двух указателях:

• сравнение: ключ слева меньше, двигаете i, справа меньше, двигаете j. Ключи-объекты сравниваются через Comparator или compareTo, а не <;
• поиск групп: при равенстве находите конец группы слева iEnd и справа jEnd, пока ключ совпадает с текущим;
• выдача: двойной цикл по [i, iEnd) и [j, jEnd) добавляет все пары;
• сдвиг: i = iEnd, j = jEnd, и продолжаете.

Сложность O(n + m + k), где k размер результата. Без повторов это линейный проход, а если у всех элементов один ключ, k равно n × m, и быстрее нельзя: столько пар нужно выдать. Дополнительная память, кроме результата, O(1).

Если данные приходят потоком через Iterator, а не списком, правую группу придётся буферизовать: к ней нужно вернуться для каждого элемента левой группы. Левую буферизовать не нужно.

Назовите альтернативу: если списки не отсортированы, hash join через HashMap<K, List<V>> даёт O(n + m), а сортировка перед merge join стоит O(n log n). Заодно проговорите left и full outer join: они отличаются только тем, что делать с непарными элементами.

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

Складывают совпавшие записи обеих сторон в один плоский список. Теряется, какая запись с какой в паре, и повторы не дают произведения.

Сравнивают ключи Integer через ==. Для значений от -128 до 127 это работает благодаря кэшу, а на больших числах сравниваются ссылки, и совпадения теряются.

Передают LinkedList и ходят по нему через get(i). Каждый вызов проходит список с начала, и линейный алгоритм превращается в квадратичный. Нужен ArrayList или итераторы.