Algorithms and Problem Solving
What this domain tests
Algorithms and problem solving covers sorting, searching, recursion, greedy methods, dynamic programming, graph traversal, and complexity analysis. Questions often ask you to trace an algorithm, pick the best approach, or identify the runtime.
Core rules
- Binary search requires a sorted array and runs in O(log n); each step halves the search space.
- Merge sort is O(n log n) worst case and stable; quicksort averages O(n log n) but can degrade to O(n²) with bad pivots.
- BFS uses a queue and finds shortest paths in unweighted graphs; DFS uses a stack or recursion and is useful for connectivity and cycle detection.
- Greedy algorithms make locally optimal choices; they are correct only when the problem has the greedy-choice property and optimal substructure.
- Dynamic programming stores overlapping subproblem results; define the state and transition before coding.
- Big-O describes growth, not exact time; drop constants and lower-order terms.
Worked example
Search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Set low = 0, high = 9. Mid = (0+9)/2 = 4, value 16 < 23, so low = 5. Mid = (5+9)/2 = 7, value 56 > 23, so high = 6. Mid = (5+6)/2 = 5, value 23, found. Three comparisons. Use low + (high - low)/2 to avoid integer overflow in fixed-width languages.
Traps
Applying binary search to unsorted data. Forgetting the base case in recursion. Assuming greedy is always optimal. Miscounting loop iterations as O(n) when each iteration halves the range. In DP, using a state that omits a needed dimension. In graph questions, marking a node visited too late, causing repeated enqueues.