Реализовать алгоритм соединения последовательностей, например hash join

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

Понимаете ли вы, почему соединение по ключу делают через хеш-таблицу, и что происходит, когда одна сторона не помещается в память. Это вопрос про инженерное мышление в обработке данных, а не про умение написать десять строк кода.

Как отвечать

Сначала проговорите схему. Строим хеш-таблицу по меньшей стороне, это фаза build, затем потоком идём по большей, это фаза probe, и для каждой строки ищем совпадения по тому же ключу. Время линейно по сумме размеров, память порядка размера build-стороны. Работает только для равенства ключей: для условий вида «больше» хеш не помогает, там нужен merge join или вложенные циклы.

from collections import defaultdict

def hash_join(left, right, lkey, rkey):
    index = defaultdict(list)
    for row in left:
        index[row[lkey]].append(row)
    for row in right:
        for match in index.get(row[rkey], ()):
            yield match, row

Возвращать пару строк, а не слитый словарь, принципиально: у таблиц бывают одноимённые колонки, и слияние молча теряет одну из них.

Дальше добавьте то, ради чего вопрос и задают. Если build-сторона не влезает в память, применяют grace hash join: обе стороны разбивают одной хеш-функцией на согласованные партиции и соединяют попарно. Перекос ключей ломает этот план, одно очень частое значение собирает гигантскую партицию. Строки с NULL в ключе не соединяются ни с чем, и это учитывают заранее.

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

Строят хеш-таблицу по большей стороне. Формально результат тот же, фактически память уходит в разы, и линейный по замыслу план начинает сбрасываться на диск.

Второе: хранят по ключу одну строку вместо списка. На уникальном ключе тест проходит, на дубликатах строки тихо теряются, а внутреннее соединение обязано вернуть все пары совпавших групп.

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