Итоговый тест собирает весь курс в одном месте: оценка сложности, выбор структуры и алгоритма, ручные трассировки и поиск ошибок. Он состоит из 23 вопросов с тремя вариантами ответа и 4 тренажёров (в интерактивном уроке: 15 вопросов и 4 тренажёра). Отвечайте, не запуская код: на собеседовании запускать его тоже нельзя. Проверить себя можно после, в разделе «Ответы».
Как проходить тест
- Отведите 40-50 минут и не заглядывайте в конспекты.
- На вопрос с кодом сначала выпишите значения переменных по шагам, потом выбирайте вариант.
- В вопросах про сложность называйте
nи самое дорогое действие. - Ответы сверьте в конце. Каждый неверный ответ это ссылка на тему для повторения.
Вопросы
Часть 1. Сложность
1. Какова сложность?
for i in range(n):
for j in range(i):
pass- A)
O(n) - B)
O(n^2) - C)
O(n log n)
2. Какова сложность?
while n > 1:
n //= 2- A)
O(log n) - B)
O(n) - C)
O(sqrt n)
3. Какова сложность? (b это список)
for x in a: # a and b are lists of length n
if x in b:
count += 1- A)
O(n) - B)
O(n log n) - C)
O(n^2)
4. Решение рекуррентности T(n) = 2T(n/2) + n?
- A)
O(n) - B)
O(n log n) - C)
O(n^2)
5. Вызов list.append n раз: амортизированная стоимость одного добавления?
- A)
O(1): ёмкость растёт геометрически, редкие копирования распределяются - B)
O(n) - C)
O(log n)
6. Сколько раз выполнится тело f в этом коде?
from functools import lru_cache
calls = 0
@lru_cache(maxsize=None)
def f(n):
global calls
calls += 1
return 1 if n < 2 else f(n - 1) + f(n - 2)
f(10)
f(10)
print(calls)- A)
177 - B)
21 - C)
11
Часть 2. Выбор структуры и алгоритма
7. Нужно часто брать элементы с начала очереди. Что выбрать?
- A)
collections.deque - B)
listиpop(0) - C)
heapq
8. Нужно найти k наименьших из потока в миллион чисел, держа O(k) памяти.
- A) Сохранить всё и отсортировать
- B) Максимальная куча размера
k - C) Убрать повторы через
set
9. Кратчайший путь во взвешенном графе без отрицательных рёбер?
- A) BFS
- B) DFS
- C) Дейкстра
10. Какая структура в среднем быстрее всего для миллионов проверок принадлежности по неизменным данным?
- A)
set - B) отсортированный список и
bisect - C) список и
in
11. Какие структуры нужны для LRU-кэша с get и put за O(1)?
