Three essential sorting algorithms and their complexities
Bubble sort: compare adjacent pairs, swap — simple but slow. Merge sort: divide and conquer, always O(n log n), stable. Quick sort: partition around pivot, O(n log n) average but O(n²) worst case.
Algorithm Paradigms
Greedy: local best choice. Dynamic Programming: cache overlapping subproblems.
Algorithm Paradigms
Two major approaches to optimization problems
Greedy: always pick locally optimal — works for some problems (Dijkstra's, Huffman coding). Dynamic programming: break into overlapping subproblems, cache results — works for more complex problems (knapsack, Fibonacci).
Two-Pointer Technique
Two-pointer technique: O(n) solution for sorted array problems — move inward from both ends
Two-Pointer Technique
A powerful O(n) strategy for many array and string problems
Place one pointer at start, one at end. Move inward based on condition. Finds pairs that sum to target in O(n) instead of O(n²). Also used for: removing duplicates, palindrome check, container with most water.
Divide and Conquer
Divide and conquer: split problem in half, solve each half, combine. Merge sort, binary search, FFT.
Divide and Conquer
Breaking problems into smaller subproblems recursively
Three steps: Divide (split into subproblems), Conquer (solve recursively), Combine (merge solutions). Merge sort: split array in half, sort each half, merge → O(n log n). Binary search: split search space in half each time → O(log n). Master Theorem gives recurrence time complexity.
Shortest Path Algorithms
BFS (Breadth-First Search): shortest path in unweighted graph, uses queue. Dijkstra: shortest path with weights, uses priority queue.
Shortest Path Algorithms
Finding the fastest route through a graph
BFS (Breadth-First Search): finds shortest path in unweighted graphs — explores level by level. Dijkstra's algorithm: shortest path in weighted graphs with non-negative weights — uses a min-priority queue, greedy approach. Bellman-Ford: handles negative weights, detects negative cycles — O(VE).
Memoization
Space-time tradeoff: memoization stores results to avoid recomputation — uses more memory, saves time
Memoization
Caching function results to avoid redundant computation
Memoization: store results of expensive function calls, return cached result when same inputs occur again. Top-down dynamic programming. Fibonacci: naive recursive = O(2ⁿ), memoized = O(n). Trade: O(n) extra space for O(n) time instead of O(2ⁿ). Key insight: avoid recomputing overlapping subproblems.
Sliding Window Technique
Sliding window: maintain a window of elements, slide it across array — O(n) instead of O(n²)
Sliding Window Technique
Efficiently solving subarray/substring problems
Fixed window: maintain window of size k, add one element, remove one element each step. Variable window: expand/contract window based on condition. Problems: maximum sum subarray of size k, longest substring without repeating characters. Avoids nested loops — O(n) instead of O(n²).
Recursion vs Iteration
Recursion vs iteration: recursion elegant but uses call stack. Deep recursion can cause stack overflow.
Recursion vs Iteration
When to recurse and when to loop
Recursion: elegant, mirrors mathematical definition, natural for tree/graph problems. Call stack has limited size — deep recursion → stack overflow. Tail recursion: recursive call is the last operation — some languages optimize this. Iteration: explicit stack management, more memory-efficient, sometimes harder to read.
P vs NP
NP-hard (Non-deterministic Polynomial-time hard) problems: no known polynomial solution. Traveling salesman, knapsack, graph coloring.
P vs NP
The most important unsolved problem in computer science
P: problems solvable in polynomial time. NP: solutions verifiable in polynomial time. NP-complete: hardest problems in NP. P=NP?: if any NP-complete problem has a polynomial solution, all do. Most believe P≠NP. Practical: use approximation algorithms or heuristics for NP-hard problems.
Amortized Analysis
Amortized analysis: occasional expensive operations averaged over many cheap ones — ArrayList doubling
Amortized Analysis
Why some data structures are efficient despite occasional slow operations
ArrayList/dynamic array: usually O(1) append, occasionally O(n) when resizing (copies all elements to new array). But doubling strategy means O(n) happens rarely — amortized O(1) per append. Stack push/pop: amortized O(1). Amortized analysis considers the average cost over a sequence of operations.
Mnemonic
What it means
✅ 0❌ 0📚 0 left
No saved cards yet — click ☆ Save on any memory trick.
🎓 Common Exam Questions
Q: Explain Big-O hierarchy from fastest to slowest with examples.
A: O(1) constant: array index, hash lookup. O(log n) logarithmic: binary search. O(n) linear: single loop. O(n log n): Merge Sort, Heap Sort — best possible for comparison sorting. O(n squared): nested loops, Bubble Sort. O(2 to the n): generating all subsets. O(n!): all permutations. Rule: O(log n) and O(n log n) are fast; O(n squared) and worse are slow for large n.
Q: Compare Merge Sort, Quick Sort, and Heap Sort.
A: Merge Sort: always O(n log n), stable, requires O(n) extra space. Best for linked lists. Quick Sort: average O(n log n), worst O(n squared) with bad pivot, in-place, fastest in practice due to cache efficiency — use randomized pivot. Heap Sort: always O(n log n), in-place O(1) space, not stable, poor cache performance. Comparison-based sorting cannot beat O(n log n). Counting Sort and Radix Sort achieve O(n) for specific input types.
Q: What is dynamic programming? Explain with Fibonacci.
A: DP requires: (1) Optimal substructure — optimal solution from optimal sub-solutions. (2) Overlapping subproblems — same subproblems solved repeatedly. Naive recursive Fibonacci: O(2 to the n). Memoized top-down: cache fib(n) results, O(n) time and space. Tabulated bottom-up: fill array iteratively, O(n) time. Classic DP: Longest Common Subsequence, 0/1 Knapsack, Coin Change, Edit Distance.
Q: What is NP-hard and why does P vs NP matter?
A: P = solvable in polynomial time. NP = verifiable in polynomial time. NP-hard = at least as hard as any NP problem. P vs NP: are fast-to-verify problems also fast-to-solve? Almost certainly not, but unproven. Cryptography relies on NP-hard problems being hard to solve. Examples: Traveling Salesman Problem, 0/1 Knapsack, Graph Coloring, SAT.
Q: Explain Dijkstra's algorithm — what does it solve and its limitations?
A: Dijkstra finds shortest path from a source to all other nodes in a weighted graph using a priority queue (min-heap). At each step: extract unvisited node with smallest distance, update neighbors. Time: O((V+E) log V). Limitation: does NOT work with negative edge weights — use Bellman-Ford O(VE) instead. BFS finds shortest path in unweighted graphs O(V+E). Floyd-Warshall finds all-pairs shortest paths O(V cubed).