Как объединить списки без использования джойнов

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

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

Как отвечать

Сначала уточните смысл. «Объединить» может значить склеить два списка подряд, это list1 + list2, extend() или itertools.chain(). Но в data-задачах почти всегда имеется в виду соединение записей по ключу без pd.merge и SQL JOIN.

Каркас решения это хеш-соединение:

• индекс по меньшему списку: by_id = {u["id"]: u for u in users}, это O(m) по времени и памяти;
• проход по большему: для каждой записи ищете пару в словаре за O(1) в среднем, итого O(n + m) против O(n·m) у вложенных циклов;
• дубли ключа: если на ключ приходится несколько записей, индекс строится через collections.defaultdict(list), и связь становится один-ко-многим;
• тип соединения: для inner пропускаете записи без пары, для left подставляете None или значения по умолчанию.

Если оба списка уже отсортированы по ключу, работает соединение слиянием: два указателя идут по спискам параллельно, и каждый раз сдвигается тот, у кого ключ меньше. Дополнительной памяти почти не нужно, поэтому так соединяют и потоки, которые не влезают в память. Для слияния отсортированных последовательностей есть heapq.merge().

В pandas тот же приём выглядит как orders["user_name"] = orders["user_id"].map(names), где names это словарь или Series. В Spark на той же идее построен broadcast: маленький справочник рассылается на все исполнители, и большая таблица не гоняется через shuffle.

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

Отвечают про конкатенацию и не замечают, что спрашивали про ключи. Уточняющий вопрос в начале экономит всё собеседование.

Пишут вложенные циклы. На двух списках по сто тысяч записей это десять миллиардов сравнений.

Строят словарь по ключу и забывают про дубли: dict молча перезаписывает значение, и часть записей теряется без единой ошибки.