You need to find a pair of elements in a sorted array that sum to a target. What pattern?
Two Pointers - use one pointer at start, one at end, move them based on whether current sum is too small or too large. O(n) time, O(1) space.
You need to find the longest substring without repeating characters. What pattern?
Sliding Window - expand window by moving right pointer, shrink by moving left pointer when you see a duplicate. Track characters in a Set or Map.
You need to detect if a linked list has a cycle. What pattern and algorithm?
Fast and Slow Pointers (Floyd’s Cycle Detection) - slow moves 1 step, fast moves 2 steps. If they meet, there’s a cycle. O(n) time, O(1) space.
You need to find the middle of a linked list in one pass. What pattern?
Fast and Slow Pointers - when fast reaches the end, slow is at the middle. Fast moves 2 steps, slow moves 1 step.
You need to merge overlapping intervals. What pattern?
Merge Intervals - sort by start time, then iterate and merge if current interval overlaps with previous. O(n log n) due to sorting.
You need to find if an array contains duplicates within k indices of each other. What pattern?
Sliding Window with a Set - maintain a window of size k, check if new element exists in window before adding.
You need to find all permutations of a string or array. What pattern?
Backtracking - build solutions incrementally, abandon partial solutions that can’t lead to valid results. Make a choice, recurse, undo the choice.
You need to find all subsets of a set. What pattern?
Backtracking or iterative bit manipulation. For each element, choose to include or exclude it. 2^n subsets total.
You need to find the shortest path in an unweighted graph. What algorithm?
BFS (Breadth-First Search) - explores all neighbors at current depth before moving deeper. Guarantees shortest path in unweighted graphs.
You need to find the shortest path in a weighted graph with non-negative weights. What algorithm?
Dijkstra’s Algorithm - use a priority queue, always process the vertex with smallest known distance. O((V + E) log V) with binary heap.
You need to find the shortest path in a weighted graph that may have negative weights. What algorithm?
Bellman-Ford Algorithm - relax all edges V-1 times. Can detect negative cycles. O(V * E) time.
You need to find if a path exists between two nodes in a graph. What algorithms can you use?
BFS or DFS. BFS finds shortest path in unweighted graphs; DFS uses less memory (O(depth) vs O(width)).
You need to determine order of tasks given dependencies. What algorithm?
Topological Sort - only works on DAGs. Use Kahn’s algorithm (BFS with in-degree tracking) or DFS with post-order processing.
How do you detect a cycle in a directed graph?
During DFS, track nodes in current recursion stack. If you visit a node already in the stack, there’s a cycle. Or use topological sort - if not all nodes are processed, cycle exists.
You need to find the kth largest element in an array. What are two approaches?
1) Min-heap of size k: O(n log k). 2) QuickSelect: O(n) average, O(n²) worst case. Heap is better when k «_space;n or for streaming data.
You need to merge k sorted lists. What pattern?
K-way Merge with a min-heap - add first element of each list to heap, extract min, add next element from that list. O(n log k).
You need to find an element in a sorted array. What algorithm?
Binary Search - O(log n). Compare target to middle element, eliminate half of remaining elements each iteration.
You need to find the first occurrence of an element in a sorted array with duplicates. What modification to binary search?
When you find target, don’t return immediately. Instead, continue searching in left half (set right = mid - 1). Return the leftmost found index.
You need to find the minimum in a rotated sorted array. What approach?
Modified Binary Search - compare mid to right. If mid > right, minimum is in right half. If mid <= right, minimum is in left half (including mid).
You need to solve a problem optimally where the solution depends on solutions to subproblems. What pattern?
Dynamic Programming - identify overlapping subproblems and optimal substructure. Memoize or tabulate results.
What are the two approaches to implementing dynamic programming?
Top-down (memoization): recursive with caching. Bottom-up (tabulation): iterative, fill table from base cases up.
You need to count the number of ways to climb n stairs taking 1 or 2 steps at a time. What pattern?
Dynamic Programming (Fibonacci-style). dp[i] = dp[i-1] + dp[i-2]. Can optimize to O(1) space by keeping only last two values.
You need to find the longest common subsequence of two strings. What pattern?
Dynamic Programming with 2D table. dp[i][j] = longest common subsequence of first i chars of s1 and first j chars of s2.
You have items with weights and values, and a capacity limit. How do you maximize value? What pattern?
0/1 Knapsack - Dynamic Programming. dp[i][w] = max value using first i items with capacity w. For each item: include it or don’t.
