DSA Cheatsheet: C++ STL, Graph and DP Templates

Learning Outcome

Keep implementation syntax and template decisions close to the interview patterns.

Pattern Recognition

Intuition

Templates are not shortcuts for thinking; they remove avoidable syntax load so attention stays on invariants.

Exact Practice Question Names

• C++ STL map/set lower_bound and upper_bound
• Priority queue min-heap syntax
• BFS and DFS traversal
• Dijkstra template
• DSU template
• DP state checklist

Interview Approach

1. Write common container operations.
2. Keep graph traversal templates compact.
3. Use long long for sums/distances when constraints are large.
4. Memorize binary search boundary variants.
5. Define DP state in comments before loops.

Pseudocode

before coding:
  choose container
  write invariant/state
  write boundary checks
  dry-run sample
  then implement
  

Sample Dry Run

For map.upper_bound(x), remember it returns the first key greater than x; use prev(it) only after checking it is not begin().

Edge Cases

• Calling top on empty stack/heap
• Iterator underflow
• sqrt precision
• Integer overflow

Common Mistakes

• Using a max-heap when a min-heap is needed
• Forgetting visited array in graph traversal
• Using pow/sqrt when squared distance is enough

Complexity

Java, C++ and Python Notes

• Java: prefer explicit classes and clear helper methods over clever one-liners.
• C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
• Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

• Name the pattern before coding.
• State the invariant or DP state in one sentence.
• Dry-run the smallest non-trivial example.
• Close with time and space complexity.