# Revision and Interview Questions — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/p-revision

> Recall data structure concepts quickly for exams and interviews.

## 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.

```text
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").

**Quiz:** What is the average time complexity of checking `x in some_set`?

- [ ] O(n)
- [ ] O(log n)
- [ ] O(n log n)
- [x] O(1)

*Answer:* O(1). Sets are hash tables, giving constant average-time membership tests.