Тест по алгоритмам

Q: Сколько вопросов в тесте по алгоритмам?

20 вопросов с выбором ответа: 7 junior, 8 middle и 5 senior. Их берём из банка в 116 вопросов с разборами.

Q: Как считается уровень?

Каждый ответ весит по сложности: junior 1 балл, middle 2, senior 3. Senior дают только тем, кто закрыл и сложные вопросы, поэтому угадать уровень на лёгких не выйдет.

Q: Нужна ли регистрация?

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

Q: Таймер строгий?

Нет. На тест отводится около 10 минут, таймер просто показывает время. Когда оно выйдет, можно спокойно закончить.

Q: Вопросы каждый раз одни и те же?

Набор вопросов теста постоянный, а порядок вопросов и вариантов меняется при каждом прохождении. Остальные вопросы ждут в билетах тренажёра.

Q: Можно поделиться результатом?

Да. Ссылка показывает только тему, уровень, процент и дату, без имени и почты.

Question 1

Что вернёт функция для [3, 1, 4, 1] и какая у неё сложность?

Accepted Answer

true, O(n)

Answer

false, O(n)

Answer

true, O(n²)

Answer

true, O(n log n)

Question 2

Какое сочетание в условии сильнее всего указывает на динамическое программирование?

Accepted Answer

«Сколько способов» или «минимум» плюс повторяющиеся подзадачи в рекурсии

Answer

«Отсортированный массив» и «найти элемент с заданным значением»

Answer

«Кратчайший путь в графе без весов» от одной вершины до другой

Answer

«Найти пару с суммой» в массиве и вернуть индексы этой пары

Question 3

Какое выражение проверяет, что положительное целое n является степенью двойки?

Accepted Answer

(n & (n - 1)) === 0

Answer

n % 2 === 0

Answer

(n | (n - 1)) === 0

Answer

n >> 1 === 0

Question 4

Какая сложность поиска в бинарном дереве поиска?

Accepted Answer

O(h): O(log n) у сбалансированного, O(n) в худшем

Answer

Всегда O(log n): каждый шаг отбрасывает половину

Answer

Всегда O(n): в худшем случае обходится всё дерево

Answer

O(1) в среднем, как у хеш-таблицы с ключами

Question 5

Что выведет код?

Accepted Answer

[1, -1, 3, -1, -1]

Answer

[1, -1, 3, 4, -1]

Answer

[5, -1, 3, -1, -1]

Answer

[1, 2, 3, 4, -1]

Question 6

Удаляем дубликаты из отсортированного массива на месте. Какой инвариант держит указатель w?

Accepted Answer

arr[0..w) содержит уникальные элементы в исходном порядке

Answer

arr[w] всегда равен максимуму уже просмотренной части

Answer

w всегда равен r - 1, то есть отстаёт ровно на один

Answer

arr[w..] отсортирован по убыванию после каждого шага

Question 7

Нужно найти k наибольших из n чисел, k много меньше n. Какой подход лучше сортировки?

Accepted Answer

Min-куча размера k с заменой вершины, O(n log k)

Answer

Max-куча из всех n элементов и k извлечений, O(n log n)

Answer

Сортировка, O(n log n), быстрее для этой задачи нельзя

Answer

Два указателя с концов массива после разбиения

Question 8

Какая сложность у функции с мемоизацией для сетки m × n?

Accepted Answer

O(m · n) времени и памяти на кеш

Answer

O(2^(m+n)), как без мемоизации

Answer

O(m + n): длина одного пути

Answer

O((m + n)!) по числу путей

Question 9

Как определить цикл в односвязном списке с O(1) памяти?

Accepted Answer

Указатели Флойда: быстрый догонит медленного

Answer

Set посещённых узлов: повтор значит цикл

Answer

Посчитать длину списка и сравнить с числом узлов

Answer

Развернуть список и сравнить головы до и после

Question 10

Почему в C или Java пишут l + (r - l) / 2, а в JS часто пишут (l + r) >> 1?

Accepted Answer

В Java l + r переполняет int, а в JS >> годится для индексов

Answer

В JS >> быстрее деления примерно в 100 раз, и это критично в цикле

Answer

Это одно и то же во всех языках, выбор только дело стиля кода

Answer

>> округляет вверх, поэтому mid никогда не совпадёт с l

Question 11

Рюкзак 0/1 со сжатием до одномерного dp[w]. Почему внутренний цикл по весу идёт **от большего к меньшему**?

Accepted Answer

Иначе предмет возьмётся повторно: dp[w - weight] уже обновлён

Answer

Так быстрее: обратный цикл лучше попадает в кеш процессора

Answer

Иначе выйдем за левую границу массива при w - weight < 0

Answer

Порядок не важен: ответ одинаков, это вопрос стиля записи

Question 12

В задаче о n ферзях как проверить за O(1), что клетка (r, c) не бьётся?

Accepted Answer

Три Set: столбцы, диагонали r - c и антидиагонали r + c

Answer

Проверять всю доску на каждом шаге: это O(1), так как n фиксировано

Answer

Три множества: столбцы, диагонали r - c и антидиагонали r + c

Answer

Сортировать позиции ферзей и проверять бинпоиском соседние клетки

Senior	от 80% баллов и от 60% senior-вопросов
Middle	от 60% баллов и от половины middle-вопросов
Junior	от 30% баллов или от 70% junior-вопросов
Пока стажёр	меньше, чем нужно для junior

Тест по алгоритмам онлайн

20 вопросов по алгоритмам

Примеры вопросов по алгоритмам

Какие темы проверяет тест

Как считается уровень

Ещё тесты

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