The final test gathers the whole course in one place: complexity estimates, choosing a structure and an algorithm, hand traces and bug hunting. It has 23 questions with three options each and 4 trainers (the interactive lesson has 15 questions and 4 trainers). Answer without running code: in an interview you cannot run it either. Check yourself afterwards in the "Answers" section.

A map of the course sections covered by the final test
A map of the course sections covered by the final test

How to take the test

  1. Set aside 40-50 minutes and do not peek into the notes.
  2. For a question with code, first write the variable values step by step, then choose an option.
  3. For complexity questions name n and the most expensive action.
  4. Compare the answers at the end. Every wrong answer is a pointer to a topic to review.

Questions

Part 1. Complexity

1. What is the complexity?

python
for i in range(n):
    for j in range(i):
        pass
  • A) O(n)
  • B) O(n^2)
  • C) O(n log n)

2. What is the complexity?

python
while n > 1:
    n //= 2
  • A) O(log n)
  • B) O(n)
  • C) O(sqrt n)

3. What is the complexity? (b is a list)

python
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. Solution of the recurrence T(n) = 2T(n/2) + n?

  • A) O(n)
  • B) O(n log n)
  • C) O(n^2)

5. list.append called n times: the amortized cost of one append?

  • A) O(1): capacity grows geometrically, rare copies are spread out
  • B) O(n)
  • C) O(log n)

6. How many times does the body of f run in this code?

python
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

Part 2. Choosing a structure and algorithm

7. You often need to take items from the front of a queue. What to choose?

  • A) collections.deque
  • B) list and pop(0)
  • C) heapq

8. Find the k smallest of a stream of a million numbers with O(k) memory.

  • A) Store everything and sort
  • B) A max-heap of size k
  • C) Drop duplicates with a set

9. The shortest path in a weighted graph with no negative edges?

  • A) BFS
  • B) DFS
  • C) Dijkstra

10. Which structure is the fastest on average for millions of membership checks on fixed data?

  • A) set
  • B) a sorted list and bisect
  • C) a list and in

11. Which structures give an LRU cache with O(1) get and put?