Какая сложность операции `x in lst` для list, set, dict? Что выбрать для поиска по 1М элементов?
Pythonmediummiddle
Проверяет знание Python и pandas для анализа данных.
big-olist-vs-setoptimizationpython
Варианты ответа
list — O(n) линейный поиск, set/dict — O(1) average через хеш-таблицу. Для 1М элементов set даст разницу в 1000+ раз. Но set требует hashable элементов и не поддерживает индексацию
list — O(n²) из-за внутренней организации, set/dict — O(n log n) через B-tree. Для миллиона записей нужен dict, потому что у него быстрее iteration через keys()
Все три — O(1) благодаря оптимизациям CPython 3.10+. Для in-операции выбор контейнера не важен, можно использовать любой. Главное — память: list занимает меньше всего
list — O(log n) благодаря binary search, set — O(1), dict — O(n) из-за hash collision. Set оптимален для маленьких коллекций до 10K элементов, дальше — list с binary search
Как разобрать этот вопрос на собеседовании
Подумай, какая структура данных и какой инструмент pandas решают задачу с наименьшей сложностью: векторизация вместо циклов, groupby/merge вместо ручных склеек, корректная работа с NaN и типами. Интервьюер смотрит на читаемость кода и на то, понимаешь ли ты, что происходит «под капотом» — копия или вью, сложность операции, утечки памяти на больших данных.
На собеседовании по такому вопросу важно не только назвать ответ, но и кратко объяснить, почему он верный.
Тема вопроса — «Python». Чтобы подготовиться к похожим задачам, отрабатывай их на практике: python-тренажёр помогает довести навык до автоматизма, а раздел вопросов — увидеть формулировки, которые реально встречаются на интервью аналитика данных.
Разбор ответа
Подробный разбор с объяснением «почему правильный ответ верный» и почему остальные неверны — после регистрации.
3000+ вопросов с разбором, quiz-режим с проверкой, AI-собес и подготовка к интервью аналитика.