сеньорчикОткрыть в Telegram
← все вопросывопросы для собеседований · Алгоритмы и структуры данных

Алгоритмы и структуры данных на собеседовании

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

158 вопросов в банке·9 подтем·ниже разбор 9

Что спрашивают

Из чего состоит тема

Так тема разложена в тренажёре: движок ведёт прогресс по каждой подтеме отдельно и возвращает те, где вы ошибаетесь.

Разборы подтем

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

Примеры вопросов с разбором

  1. #arrays_hashing1 / 9
    Проверить, есть ли в массиве из миллиона элементов дубликаты. Как уложиться в O(n)?
    A)Двойной вложенный цикл: сравнить каждый элемент с каждым другим и искать совпадения
    B)Идти по массиву, класть виденные в set; если элемент уже там — дубликат
    C)Отсортировать и сравнить с соседями
    D)Ничего не получится — задача требует минимум O(n²)
    показать ответ и разбор
    +B)Идти по массиву, класть виденные в set; если элемент уже там — дубликат

    // разбор: Проход по массиву с множеством виденных: на каждом шаге проверка «x in seen» амортизированно O(1), всего O(n) времени и O(n) памяти. Сортировка + сравнение соседей даёт O(n log n) — тоже приемлемо, но медленнее и меняет порядок. Вложенный цикл O(n²) на миллионе — сотни миллиардов операций, неприемлемо.

  2. #complexity2 / 9
    Что описывает O-нотация (например, O(n log n))?
    A)Как растёт время с ростом входа, с точностью до констант и младших членов
    B)Точное число процессорных тактов на конкретной машине для данного входа размера n
    C)Объём исходного кода алгоритма в строках
    D)Среднее время на случайных данных
    показать ответ и разбор
    +A)Как растёт время с ростом входа, с точностью до констант и младших членов

    // разбор: O описывает порядок роста при n→∞, отбрасывая константы и младшие члены: O(2n²+n) = O(n²). Она не про такты конкретного железа и не про строки кода. По умолчанию говорят про худший случай, если не оговорено иное.

  3. #sorting_searching3 / 9
    Counting sort сортирует за O(n + k), обходя границу n log n. Когда он уместен и в чём подвох?
    A)Это лучшая сортировка без недостатков
    B)Для строк произвольной длины
    C)Когда данные уже отсортированы
    D)Когда ключи — целые из небольшого диапазона k: при огромном k память и время O(n+k) взрываются
    показать ответ и разбор
    +D)Когда ключи — целые из небольшого диапазона k: при огромном k память и время O(n+k) взрываются

    // разбор: Counting sort считает частоты значений в массиве размера k (диапазон ключей), поэтому не сравнивает элементы и обходит n log n. Цена: нужен целочисленный (или дискретный) ключ из ограниченного диапазона. Если k огромно (64-битные числа), массив счётчиков и время O(n+k) становятся неподъёмными. Для больших диапазонов берут radix sort.

  4. #stacks_queues_heaps4 / 9
    Куча (heap / priority queue) даёт O(1) на...
    A)Поиск произвольного элемента по его значению где угодно внутри структуры
    B)Полную сортировку всех элементов за один шаг
    C)просмотр минимума (или максимума) на вершине; извлечение — O(log n)
    D)Вставку с последующим полным упорядочиванием
    показать ответ и разбор
    +C)просмотр минимума (или максимума) на вершине; извлечение — O(log n)

    // разбор: Бинарная куча держит минимум (или максимум) в корне — peek за O(1). Вставка и извлечение корня — O(log n) на просеивание. Поиск произвольного элемента не ускорен — O(n). Куча идеальна, когда нужен постоянный доступ к экстремуму: топ-k, слияние потоков, Дейкстра, планировщики.

  5. #dynamic_programming5 / 9
    С чего начинают решение задачи динамическим программированием?
    A)Сразу пишут тройной вложенный цикл по всем индексам и перебором подбирают ответ, а формулу выводят после
    B)Определяют состояние (что описывает подзадача), формулу перехода к меньшим состояниям и базовые случаи
    C)Сортируют вход и берут жадно наибольшие элементы
    D)Перебирают все варианты и выбирают лучший
    показать ответ и разбор
    +B)Определяют состояние (что описывает подзадача), формулу перехода к меньшим состояниям и базовые случаи

    // разбор: Ядро DP — правильно выбрать состояние (какие параметры однозначно задают подзадачу и её ответ), затем выписать переход (рекуррентность), связывающий состояние с меньшими, и определить базу. Если состояние и переход найдены, реализация (мемоизация или табуляция) уже механическая. Ошибки DP чаще всего не в коде, а в неудачно выбранном состоянии — избыточном или, наоборот, теряющем нужную информацию.

  6. #graph_algorithms6 / 9
    Что такое топологическая сортировка и для каких графов она определена?
    A)Упорядочивание вершин по числу входящих рёбер; годится и для графов с циклами, порядок всё равно найдётся
    B)Обход графа в ширину с сохранением расстояний
    C)Сортировка рёбер по весу для построения кратчайших путей
    D)Линейный порядок, где каждое ребро ведёт от раннего к позднему; существует только для DAG (без циклов)
    показать ответ и разбор
    +D)Линейный порядок, где каждое ребро ведёт от раннего к позднему; существует только для DAG (без циклов)

    // разбор: Топологический порядок раскладывает вершины DAG в линию так, что все рёбра направлены слева направо — это порядок выполнения задач с зависимостями. Он существует тогда и только тогда, когда граф ориентированный и без циклов: цикл создаёт взаимную зависимость, которую линейно не разложить. Строят через DFS (по завершению) или алгоритм Кана (по нулевой входящей степени).

  7. #recursion_backtracking7 / 9
    Как «разделяй и властвуй» на примере сортировки слиянием (merge sort) даёт O(n log n)?
    A)Она попарно сравнивает каждый элемент с каждым при слиянии, отчего и набегает квадратичная стоимость n·n
    B)Она сортирует за линейное время, log появляется случайно
    C)log n уровней деления пополам, на каждом слияние обрабатывает все n элементов — итого O(n log n)
    D)Сложность зависит только от начального порядка данных
    показать ответ и разбор
    +C)log n уровней деления пополам, на каждом слияние обрабатывает все n элементов — итого O(n log n)

    // разбор: Merge sort делит массив надвое до одиночных элементов — это дерево рекурсии высотой log n. На каждом уровне суммарно сливаются все n элементов за линейное время. Перемножая: n работы × log n уровней = O(n log n), причём стабильно, независимо от исходного порядка (в отличие от quicksort с его худшим O(n²)). Плата — O(n) дополнительной памяти под слияние.

  8. #tree_structures8 / 9
    Почему у обычного (несбалансированного) BST операции могут деградировать до O(n)?
    A)Отсортированный ввод вырождает дерево в список высотой n — операции падают до O(n)
    B)Из-за коллизий хешей в узлах
    C)У BST сложность операций — O(n)
    D)Из-за накладных расходов на указатели детей: когда узлов много, кэш процессора промахивается и всё замедляется
    показать ответ и разбор
    +A)Отсортированный ввод вырождает дерево в список высотой n — операции падают до O(n)

    // разбор: Сложность операций BST пропорциональна высоте дерева. При случайных вставках высота ~log n, но если ключи приходят уже отсортированными, каждый следующий больше (или меньше) предыдущего и цепляется к одной ветке — дерево превращается в линейный список высотой n. Тогда поиск/вставка/удаление становятся O(n). Отсюда самобалансирующиеся деревья (AVL, красно-чёрные), удерживающие высоту логарифмической.

  9. #trees_graphs_recursion9 / 9
    Что обязательно должно быть у корректной рекурсии?
    A)Обязательно хотя бы два входных аргумента, иначе рекурсия не сможет корректно ветвиться
    B)Глобальная переменная-счётчик вызовов
    C)Базовый случай (условие остановки) и движение к нему на каждом шаге
    D)Возврат значения через print
    показать ответ и разбор
    +C)Базовый случай (условие остановки) и движение к нему на каждом шаге

    // разбор: Рекурсия без базового случая (или без гарантированного приближения к нему) не завершается и упирается в переполнение стека вызовов (RecursionError). Два обязательных ингредиента: (1) база — когда перестаём вызывать себя; (2) рекурсивный шаг, уменьшающий задачу к базе. Число аргументов и способ вывода к корректности отношения не имеют.

это 9 из 158

Ещё 149 вопросов по теме — в тренажёре, с движком повторения

Прочитать разбор и ответить самому — разные навыки. В Сеньорчике вопросы идут сессиями, а движок возвращает подтемы, где вы ошибаетесь, пока они не начнут отскакивать. Бесплатно, лимит по энергии.

Открыть тренажёрДругие темы

Частые вопросы

куда дальше