Interview Readiness — Master Recap and Final Cheatsheet

The Complete Interview Cheatsheet

Pattern Recognition — At a Glance

Input is sorted?
  → Binary search, two pointers

Find all combinations / subsets?
  → Backtracking

Shortest path, fewest steps?
  → BFS

Any valid path / all paths?
  → DFS

Minimum cost, maximum value?
  → DP

Overlapping intervals?
  → Sort by start, greedy merge / heap

Top K elements?
  → Heap (min-heap of size K)

Substring with constraint?
  → Sliding window

Contiguous subarray sum?
  → Prefix sum + hashmap

Frequency / duplicates?
  → HashMap / Counter

Prefix match / autocomplete?
  → Trie

Range queries?
  → Segment Tree / BIT

Graph connectivity?
  → Union-Find

Ordering with dependencies?
  → Topological sort

Running median?
  → Two heaps

Next greater / smaller element?
  → Monotonic stack

Complexity Cheatsheet

Algorithm	Time	Space
BFS / DFS	O(V+E)	O(V)
Dijkstra (heap)	O((V+E) log V)	O(V)
Binary Search	O(log n)	O(1)
Merge Sort	O(n log n)	O(n)
Heap push/pop	O(log n)	O(n)
HashMap get/set	O(1) avg	O(n)
Trie insert/search	O(L)	O(ALPHABET × N × L)
Union-Find	O(α(n)) ≈ O(1)	O(n)
Segment Tree	O(log n)	O(n)
LRU get/put	O(1)	O(n)
1D DP	O(n) or O(n²)	O(n) or O(1)
2D DP	O(mn)	O(mn) or O(n)

The STAR Story Index

Story 1: Biggest impact project → "Invent and Simplify" / "Deliver Results"
Story 2: Disagreed with manager → "Have Backbone; Disagree and Commit"
Story 3: Failure and recovery → "Learn and Be Curious"
Story 4: Learned fast → "Learn and Be Curious"
Story 5: Incomplete data decision → "Bias for Action" / "Are Right, A Lot"
Story 6: Improved a process → "Invent and Simplify" / "Frugality"
Story 7: Tough feedback → "Earn Trust"
Story 8: Mentored someone → "Hire and Develop the Best"
Story 9: Competing priorities → "Deliver Results"
Story 10: Above and beyond → "Ownership" / "Customer Obsession"

The UMPIRE Checklist (Per Problem)

U — Understood the problem? (restate + ask edge cases)
M — Matched to a pattern?
P — Planned with pseudocode?
I — Implemented cleanly?
R — Reviewed with test case?
E — Evaluated complexity?

Company Quick Reference

	Google	Meta	Amazon
Rounds	4-5	4	5-6
Style	Analytical	Fast-paced	LP-heavy
Key topics	Graphs, DP	Arrays, Trees	BFS, Design
Values	Googleyness	Move Fast	Leadership Principles
System design	L5+	E5+	SDE II+
Coding speed	Moderate	Fast	Moderate
Hint culture	Will hint	May hint	Expects self-recovery

Closing Mindset

Three things to remember on interview day:

The interviewer wants you to succeed — they're rooting for you, not trying to catch you out.
Communication > cleverness — a clearly explained O(n²) solution beats a silent O(n) one.
Progress is visible — saying "I'd start with X and optimise to Y given more time" shows engineering judgment even if you don't finish.

You've put in the work. Trust the preparation.