Вопросы на собеседовании в Т-Банке
Т-Банк (бывший Тинькофф) любит проверять не только знания, но и продуктовое мышление: LLM и классический ML в связке с метриками и аналитикой, плюс алгоритмы. Ниже — вопросы формата секций Т-Банка из банка Сеньорчика, с разбором.
В хеш-таблице при большом числе коллизий средний O(1) может деградировать. До чего в худшем случае и почему?
A)До O(log n), потому что бакеты внутри организованы как сбалансированное дерево и потому поиск в них остаётся логарифмическимB)до O(n): если все ключи попадают в один бакет, поиск вырождается в обход цепочкиC)Не деградирует — на то она и хеш-таблицаD)До O(n²), потому что коллизии удваивают работупоказать ответ и разбор
+B)до O(n): если все ключи попадают в один бакет, поиск вырождается в обход цепочки// разбор: Если хеш плохой или данные подобраны злонамеренно, все ключи садятся в один бакет, и поиск/вставка идут по цепочке — O(n). Отсюда hash-flooding атаки. Защита: хороший рандомизированный хеш (SipHash в Python), рехеширование при росте загрузки, а в некоторых реализациях (Java 8+) длинные цепочки превращают в дерево — тогда худший O(log n).
Почему у quicksort в среднем O(n log n), а в худшем O(n²), и когда худший случай реально стреляет?
A)Худший — когда пивот делит массив крайне неравномерно (1 и n−1), например на уже отсортированных данных с наивным выбором опорногоB)Худший случай не выходит на практикеC)В среднем и в худшем одинаково, разница в памятиD)Худший — когда все элементы различныпоказать ответ и разбор
+A)Худший — когда пивот делит массив крайне неравномерно (1 и n−1), например на уже отсортированных данных с наивным выбором опорного// разбор: Quicksort рекурсивно разбивает по пивоту. Если пивот каждый раз почти крайний, разбиение выходит 1 и n−1 — глубина рекурсии n, работа n на уровень → O(n²). Классический триггер: наивный выбор пивота (первый/последний) на уже отсортированном входе. В среднем разбиение сбалансированно → O(n log n). Рандомизация пивота делает худший случай маловероятным.
Как поддерживать топ-k наибольших элементов в потоке из миллионов чисел, не храня весь поток?
A)Держать min-heap размера k: новый элемент больше корня — заменяем корень и просеиваем; иначе пропускаемB)Сортировать весь поток после каждого нового элементаC)Хранить всё в списке и брать max k разD)Использовать стек и снимать верхние kпоказать ответ и разбор
+A)Держать min-heap размера k: новый элемент больше корня — заменяем корень и просеиваем; иначе пропускаем// разбор: Min-heap размера k держит k текущих кандидатов, на вершине — наименьший из них. Новый элемент сравниваем с корнем: если больше — вытесняем корень (заменяем и просеиваем, O(log k)); если меньше — он в топ-k не попадёт, пропускаем. Память O(k), время O(n log k), поток целиком хранить не нужно.
Что делает динамическое программирование (DP) применимым к задаче?
A)Задача обязательно должна формулироваться в терминах графов и путей между их вершинами без исключенийB)Наличие случайности во входных данныхC)Оптимальная подструктура и перекрывающиеся подзадачи: ответ собирается из меньшихD)Возможность решить всё жадным алгоритмом за O(n)показать ответ и разбор
+C)Оптимальная подструктура и перекрывающиеся подзадачи: ответ собирается из меньших// разбор: DP применимо при двух свойствах: (1) оптимальная подструктура — оптимум задачи выражается через оптимумы подзадач; (2) перекрывающиеся подзадачи — одни и те же подзадачи встречаются много раз (иначе хватило бы «разделяй и властвуй»). Тогда кэшируем подзадачи и решаем каждую однажды. Если подзадачи не пересекаются — DP выгоды не даёт.
Чем опасен target encoding категорий, посчитанный по всей обучающей выборке без сглаживания и разбиения?
A)Утечка таргета: значение признака напрямую содержит ответ, особенно для редких категорийB)Кодировка теряет информацию о частоте категории и обедняет модельC)Он не работает с бустингом: деревья не умеют в непрерывные кодировки категорийD)Ничем: без сглаживания target encoding безопасен, пока категорий меньше тысячипоказать ответ и разбор
+A)Утечка таргета: значение признака напрямую содержит ответ, особенно для редких категорий// разбор: Для категории из одного объекта target encoding равен его таргету — модель «читает ответ» из признака и идеально переобучается. Защита: out-of-fold кодирование, сглаживание к глобальному среднему, шум (как в CatBoost с ordered target statistics).
В логистической регрессии признаки сильно коррелируют между собой (мультиколлинеарность). Что произойдёт с моделью в первую очередь?
A)Оценки весов станут нестабильными: большие по модулю, с раздутой дисперсией — интерпретация ломаетсяB)Модель перестанет сходиться, оптимизатор начнёт зацикливаться между эквивалентными решениямиC)Качество предсказаний резко упадёт даже на обучающей выборкеD)Логрег сам удалит один из коррелирующих признаков за счёт регуляризации по умолчаниюпоказать ответ и разбор
+A)Оценки весов станут нестабильными: большие по модулю, с раздутой дисперсией — интерпретация ломается// разбор: Мультиколлинеарность раздувает дисперсию оценок весов: знаки и величины скачут от выборки к выборке, интерпретация «вклада признака» теряет смысл. Предсказательная сила при этом может почти не страдать. Лечится регуляризацией или удалением/объединением признаков.
Почему feature importance по gain в бустинге может систематически обманывать, и что использовать вместо неё для интерпретации?
A)Gain занижает важность категориальных признаков; вместо него смотрят accuracy по классамB)Gain считается по первым деревьям ансамбля, а хвост игнорируетсяC)Gain смещён к признакам с большим числом сплитов и делится произвольно между коррелирующими; честнее permutation или SHAPD)Gain корректен по построению: это суммарный вклад признака в снижение лосса по всем сплитам всех деревьев ансамбля, что и есть важностьпоказать ответ и разбор
+C)Gain смещён к признакам с большим числом сплитов и делится произвольно между коррелирующими; честнее permutation или SHAP// разбор: Непрерывный признак даёт больше кандидатов на сплит и чаще «выигрывает» чисто комбинаторно; коррелирующие признаки делят важность произвольно. Permutation importance меряет реальное падение качества, SHAP даёт локальные вклады с теоретическими гарантиями — но оба тоже страдают от корреляций, что стоит проговорить на собесе.
Почему мешок слов часто ошибается на сентименте фразы «фильм был совсем не хорош»?
A)BoW теряет порядок и область отрицания: видит «хорош» → позитив, а «не» отдельным токеном слабо помогаетB)В этой фразе отсутствуют эмоционально окрашенные или тональные словаC)BoW не умеет читать кириллические символыD)Отрицание в тексте усиливает позитивную оценкупоказать ответ и разбор
+A)BoW теряет порядок и область отрицания: видит «хорош» → позитив, а «не» отдельным токеном слабо помогает// разбор: Тональность зависит от порядка и области действия отрицания: «не хорош» = негатив, но BoW видит независимые токены и сильное позитивное «хорош» перетягивает, а «не» без привязки к отрицаемому помогает слабо. Классические обходы: биграммы («не_хорош»), склейка отрицания с последующими словами (negation tagging), лексиконы с правилами. Полноценно решают модели с порядком (RNN/трансформеры).
Когда классический TF-IDF/BM25 всё ещё предпочтительнее плотных эмбеддингов?
A)Редко: плотные нейросетевые эмбеддинги превосходят лексический поиск по большинству критериевB)При работе с изображениями, а не текстомC)При полном отсутствии электричества и вычислительных ресурсовD)Точный лексический матч, редкие термины/коды/имена, интерпретируемость и дешевизна без обучения — тут sparse сильнеепоказать ответ и разбор
+D)Точный лексический матч, редкие термины/коды/имена, интерпретируемость и дешевизна без обучения — тут sparse сильнее// разбор: Плотные эмбеддинги ловят семантику, но у sparse есть устойчивые преимущества: точное совпадение терминов (коды ошибок, артикулы, имена), где важен буквальный токен; редкие слова, на которых эмбеддинги шумны; интерпретируемость (видно, какие слова сработали); отсутствие обучения/инференса (дёшево, воспроизводимо). Поэтому продовый поиск берёт гибрид (BM25 + dense).
это девять из 42
Ещё 33 вопросов уровня Т-Банк — внутри тренажёра.
Они входят в общий банк Сеньорчика: 2899 вопросов по 44 темам. Выбираете роль, тренируетесь ежедневными сессиями, а движок повторения возвращает темы, где вы плывёте, — как раз те, на которых валят секции. Начать можно бесплатно.