Лайвкодинг Data Scientist в Сбер: словарь и префиксное дерево

Это coding-секция собеседования Data Scientist в Сбер. Сначала кандидата спросили про словари, хеш-функции и ссылки в Python, затем предложили реализовать префиксное дерево. Личные данные участников не нужны для разбора: нас интересуют ход решения, проверки и качество объяснения.

Как устроен dict и хорошая хеш-функция

dict хранит пары ключ — значение и использует хеш ключа, чтобы быстро найти нужную запись. В среднем чтение и запись близки к O(1), но это не математическая гарантия для любого входа: коллизии и рост таблицы требуют дополнительной работы.

Хорошая хеш-функция для таблицы должна быть быстрой, давать одинаковый результат для неизменившегося ключа и достаточно равномерно распределять реальные входы. Если a == b, их хеши обязаны совпадать. Обратное неверно: разные ключи могут иметь одинаковый хеш, и словарь должен сравнить сами ключи.

В Python ключ обязан быть хешируемым. Поэтому строка и кортеж из хешируемых элементов подходят, а список — нет. Связь __eq__ и __hash__ подробно описана в модели данных Python.

Коротко: словарь получает быстрый доступ по ключу благодаря хеш-таблице, а корректность зависит от стабильного хеша и сравнения ключей.

Почему список хранит объекты разных типов

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

Это объяснение лучше фразы «Python динамический, поэтому ему можно». Динамическая типизация описывает проверку типа во время выполнения, а способность списка смешивать значения связана с тем, что элементы — ссылки на объекты.

Практический вывод: смешанный список допустим, но часто усложняет код. Аннотация list[int] помогает инструментам и читателю, хотя обычный Python не запрещает добавить туда строку во время выполнения.

Коротко: контейнер Python хранит ссылки на объекты, поэтому один список может содержать значения разных типов.

Как работает префиксное дерево

Trie, или префиксное дерево, хранит строки посимвольно. Слова стол, стул и столовая делят общий путь для первых букв. Поиск занимает O(L), где L — длина строки.

Цветные узлы отмечают окончания слов; промежуточный узел может быть только частью более длинного слова. Источник: Booyabazooka и Superm401, Wikimedia Commons, общественное достояние.

Флаг is_word обязателен. Без него дерево не отличит полное слово стол от префикса в слове столовая. Цена структуры — память: у каждого узла есть контейнер потомков и служебные поля.

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

Как реализовать trie на лайвкодинге

Сначала достаточно двух операций: добавить слово и проверить полное совпадение. Такой минимальный объём легко протестировать и расширить.

class TrieNode:
    def __init__(self) -> None:
        # Ключ — символ, значение — следующий узел дерева.
        self.children: dict[str, TrieNode] = {}
        # Флаг отличает целое слово от обычного префикса.
        self.is_word = False


class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            # Создаём узел только для нового продолжения префикса.
            node = node.children.setdefault(char, TrieNode())
        node.is_word = True

    def contains(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        # Путь существует, но он должен заканчиваться полным словом.
        return node.is_word


trie = Trie()
trie.insert("стол")
trie.insert("столовая")

# «сто» существует как префикс, но не было добавлено как слово.
assert trie.contains("стол") is True
assert trie.contains("сто") is False

Для отладки полезен __repr__: он даёт техническое представление узла, которое видно в консоли и отладчике. Специальные методы представления описаны в документации Python. Не нужно сразу рисовать граф — сначала добейтесь читаемого состояния структуры и тестов на общий префикс, отсутствующее слово и слово, вложенное в другое.

Коротко: на лайвкодинге оценивают не скорость набора, а декомпозицию, проверки, объяснение сложности и удобство отладки.

Итог: получил ли кандидат оффер

Да. В описании исходного материала прямо указано, что это часть собеседования Data Scientist в Сбер с оффером на 350 000 ₽. Coding-секция не была идеальной демонстрацией готового алгоритма: интервьюер помогал уточнять структуру и способ отладки. Но кандидат понимал словари, быстро разобрал новую структуру и довёл решение до рабочего состояния.

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

Коротко: эта coding-секция была частью успешного собеседования в Сбер, после которого кандидат получил оффер на 350 000 ₽.

Чек-лист перед лайвкодингом

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

Источники

• Python: хеширование объектов
• Python: тип отображения dict
• Python: метод repr
• Wikimedia Commons: пример trie