Revision and Interview Questions

Cheat sheet

Complexity: O(1), O(log n), O(n), O(n log n), O(n²); worst, average, amortised; measure with timeit, cProfile, tracemalloc. Object model: names reference objects, mutability, aliasing, shallow vs deep copy, mutable default arguments, hashability. list: dynamic array; index, append, pop() O(1) (append amortised); insert(0)/pop(0)/search O(n); Timsort O(n log n), stable. tuple (immutable, hashable), NamedTuple, dataclass (frozen, slots, default_factory). str immutable, use join; bytes, bytearray, memoryview. dict: hash table, O(1) average, insertion-ordered since 3.7, hash/eq contract, | merge; set/frozenset: membership and algebra; Counter, defaultdict, OrderedDict (move_to_end), ChainMap. Stacks with list, queues with deque (O(1) both ends, maxlen), queue.Queue for threads. Linked lists: O(1) insert at a known node, O(n) search; reverse, Floyd cycle detection. Heaps: heapq min-heap, push/pop O(log n), heapify O(n), nlargest, tie-break with a counter. Trees: traversals (pre, in, post, level), height, recursion limit; BST O(h), degenerate O(n), bisect, sortedcontainers; tries O(m) prefix search. Graphs: adjacency list vs matrix, BFS (shortest unweighted paths), DFS (components, cycles), Dijkstra with heapq, topological sort with graphlib. Union-find with path compression and union by size. LRU caches with OrderedDict and functools.lru_cache. Memory: slots, array, generators, NumPy. Patterns: two pointers, sliding window, prefix sums, monotonic stack.

Common interview questions

Answer each with complexity and a short code example.

1. What are the time complexities of list append, insert at the front, and membership?
2. How does a Python dict work, and why must keys be hashable?
3. What is the difference between a shallow copy and a deep copy?
4. When would you use a deque instead of a list?
5. How does heapq work, and how do you build a max-heap or break ties?
6. Explain BFS vs DFS and when each is appropriate.
7. Implement an LRU cache with O(1) get and put.
8. What is union-find, and what makes it nearly constant time?
9. How does Dijkstra's algorithm work, and why does it fail with negative weights?
10. When is a trie better than a set of strings?
11. How would you find the top 10 most frequent words in a large file?
12. Solve "longest substring without repeating characters" and explain the complexity.

Always state complexity and trade-offs

A strong answer names the structure, gives the time and space complexity of the key operations, and mentions an alternative ("a heap gives O(n log k); sorting would be O(n log n) but simpler").

Quick check: What is the average time complexity of checking `x in some_set`?

• O(n)
• O(log n)
• O(n log n)
• O(1)