Skip to content
elevatedevco

Cheat sheet · Careers & Interviews

Big-O & DSA for Interviews cheat sheet

The key ideas on one page — plus common pitfalls and interview tips. Skim it before an interview, or print it for revision.

Cheat sheet

A dense, interview-grade reference on asymptotic analysis and the core data structures and algorithm patterns most asked of data scientists and ML engineers, with Python-specific complexity notes, formulas, and code idioms.

Big-O Fundamentals & Notation

  • Big-O is an asymptotic UPPER bound on growth as n grows large; Omega is the lower bound, Theta is the tight bound (matching upper and lower). Unless they ask for average/amortized, interviewers usually want the WORST-CASE bound, stated in Big-O.
  • Drop constants and lower-order terms: O(2n+5) = O(n), O(n^2 + n) = O(n^2). Constants matter in practice but not in the notation.
  • Common growth order, slowest-growing first: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!).
  • Analyze TIME and SPACE separately; recursion adds O(depth) call-stack space even when no explicit data structure is allocated.
  • Amortized analysis averages cost over a sequence of ops (e.g. Python list append is amortized O(1) despite occasional O(n) resize); this is distinct from average-case, which depends on the input distribution.
  • Multi-variable inputs need multi-variable bounds: graph traversal is O(V+E), not O(n); matrix ops on an r x c matrix are O(r*c).

Python Built-in Complexities (CPython)

  • list: index/append amortized O(1); insert(0,x) / pop(0) / 'x in list' / del of a middle element = O(n). Use collections.deque for O(1) ops at both ends.
  • dict & set: average O(1) insert/lookup/delete; O(n) worst case under pathological hash collisions. 'x in set' is O(1) vs 'x in list' O(n) - a very common fix.
  • Sorting: sorted() / list.sort() use Timsort = O(n log n) worst case, O(n) on already/nearly-sorted data, and stable; O(n) extra space.
  • heapq: heappush/heappop O(log n), heapify O(n), peek heap[0] O(1). Min-heap only - negate values (or use tuples) to simulate a max-heap.
  • String concatenation in a loop is O(n^2); collect parts in a list and ''.join() for O(n). Slicing s[a:b] copies -> O(b-a).
  • Counter / defaultdict are dict subclasses with the same O(1) average ops; ideal for frequency-map and grouping patterns.

Core Data Structures & When to Use

  • Hash map/set: O(1) avg lookup - dedup, frequency counts, two-sum, caching/memoization, group-by.
  • Stack (list/deque): LIFO - valid parentheses, monotonic stack (next greater element), DFS, expression eval, undo.
  • Queue/deque: FIFO/double-ended - BFS, sliding-window max (monotonic deque), level-order traversal.
  • Heap/priority queue: top-k, k-way merge, Dijkstra, running median (two heaps), scheduling.
  • Trees/BST: ordered data and range queries; a balanced BST gives O(log n) search/insert; a trie gives O(L) prefix/autocomplete lookups per word of length L.
  • Union-Find (DSU): near-O(alpha(n)) ~ O(1) amortized with path compression + union by rank - connected components, cycle detection, Kruskal's MST.
  • Graph as adjacency list: O(V+E) space, efficient traversal; adjacency matrix is O(V^2) space but gives O(1) edge lookup, better for dense graphs.

Algorithm Patterns (the 80/20)

  • Two pointers / sliding window: O(n) on sorted arrays or contiguous-subarray problems - often replaces an O(n^2) brute force.
  • Binary search: O(log n) on a sorted/monotonic search space; also 'binary search on the answer' for min/max feasibility problems.
  • BFS = shortest path in UNWEIGHTED graphs, O(V+E); DFS = connectivity, topological sort, backtracking.
  • Dijkstra (binary heap) O(E log V) for non-negative weights; Bellman-Ford O(V*E) handles negative edges; topo-sort + DP for DAGs.
  • Dynamic programming: confirm overlapping subproblems + optimal substructure; complexity ~= (#states) x (work per state). Memoize top-down or tabulate bottom-up.
  • Backtracking: prune the search tree (subsets O(2^n), permutations O(n!)); apply constraints early to cut branches.
  • Greedy: only valid when the greedy-choice / exchange-argument property holds - often O(n log n) after sorting.

Recursion, Recurrences & the Master Theorem

  • A recurrence T(n) = a*T(n/b) + f(n) describes divide-and-conquer: a = #subproblems, n/b = subproblem size, f(n) = split/merge cost.
  • Master Theorem compares f(n) to n^(log_b a): if f is polynomially smaller -> O(n^(log_b a)); if they match -> O(n^(log_b a) * log n); if f is polynomially larger AND the regularity condition holds -> O(f(n)).
  • Merge sort T(n)=2T(n/2)+O(n) -> O(n log n); binary search T(n)=T(n/2)+O(1) -> O(log n); naive Fibonacci T(n)=T(n-1)+T(n-2) -> O(phi^n) ~ O(1.618^n).
  • Recursion uses O(depth) call-stack space; deep recursion risks Python's default ~1000-frame RecursionError - convert to iteration or raise the limit deliberately.
  • Memoization turns exponential recursion into polynomial by caching states (functools.cache / lru_cache or a dict).

ML/DS-Flavored Complexity

  • Vectorize with NumPy: a Python loop over n is O(n) interpreted ops; the NumPy equivalent is still O(n) but runs in optimized C - same asymptotics, a large constant-factor win.
  • Common training costs: linear/logistic regression via the closed-form normal equation O(n*d^2 + d^3); gradient descent O(n*d) per epoch; k-NN has no train cost but O(n*d) per query.
  • Tree ensembles: training one decision tree ~ O(n*d*log n); k-means O(n*k*d) per iteration; naive self-attention O(L^2*d) in sequence length L.
  • Sorting/dedup/joins dominate data pipelines: hash join O(n+m) avg vs nested-loop O(n*m); pandas groupby is hash-based, ~O(n).
  • Space matters at scale: prefer generators/iterators (O(1) extra) over materializing lists (O(n)); watch for O(n^2) memory in pairwise distance matrices.
  • Approximate/streaming structures trade accuracy for complexity: HyperLogLog (count-distinct), Bloom filter (membership), reservoir sampling - all sublinear space.
Read the full lesson