Master common problem-solving patterns to recognize and apply them in interviews.
Level-by-level traversal using a queue, exploring all neighbors at the current depth before moving deeper. This guarantees the shortest path in unweighted graphs and is ideal for problems requiring layer-by-layer processing.
Build solutions incrementally, exploring choices one at a time and abandoning paths that fail to satisfy constraints. Backtracking systematically explores all possibilities by making a choice, recursing, then undoing the choice.
Efficiently search sorted data by repeatedly dividing the search space in half. This transforms O(n) linear search into O(log n) by eliminating half the remaining possibilities with each comparison.
Visit all nodes in a binary tree in specific orders: preorder (root-left-right), inorder (left-root-right), postorder (left-right-root), or level-order (BFS). Each order reveals different structural information about the tree.
Techniques using binary operations (AND, OR, XOR, NOT, shifts) to solve problems efficiently, often achieving O(1) space where other approaches need O(n).
Exploit bounded value ranges to achieve linear time sorting or selection by using values as array indices.
Place each number at its "correct" index when dealing with arrays containing numbers in the range [1, n] or [0, n-1].
Explore as deep as possible along each branch before backtracking, using recursion or an explicit stack. DFS is memory-efficient and naturally suited for problems involving paths, connectivity, and exhaustive exploration.
Break a problem into smaller subproblems, solve them independently, and combine results. Unlike DP, subproblems don't overlap.
Break problems into overlapping subproblems, storing results to avoid recomputation. This transforms exponential time complexity into polynomial by trading space for time.
Use two pointers moving at different speeds to detect cycles, find midpoints, or identify patterns in sequences. The fast pointer advances twice as quickly, allowing detection of structural properties without extra space.
Make locally optimal choices at each step, hoping to find a global optimum. Greedy algorithms are simple and efficient but only work when the problem has the greedy choice property—local optima lead to global optimum.
Use hash tables for O(1) average lookup, insertion, and deletion.
A data structure that efficiently maintains the minimum or maximum element, supporting O(log n) insertion and extraction. Heaps are essential when you repeatedly need to access the smallest or largest element from a changing set.
Reverse linked list nodes in-place by manipulating pointers without allocating extra space. This technique uses three pointers to track the previous, current, and next nodes while systematically reversing the direction of links.
Transform or process 2D matrices using rotation, transposition, or in-place modifications.
Navigate 2D grids systematically using DFS, BFS, or directional iteration. Matrix traversal combines graph traversal concepts with coordinate-based movement, treating each cell as a node connected to its neighbors.
Maintain a stack where elements are always in sorted order (either increasing or decreasing). This enables efficient solutions for "next greater element" problems by leveraging the stack's ability to track candidates that might be the answer for future elements.
Process and manipulate intervals (ranges) that may share common regions. The key insight is that sorting intervals by start time allows efficient detection and handling of overlaps through a single linear pass.
Precompute cumulative sums to answer range sum queries in O(1) time. This transforms repeated O(n) range calculations into O(n) preprocessing plus O(1) per query, making it essential for problems involving subarray sums.
Maintain a window of elements that slides through the data, tracking a constraint or computing aggregates. This transforms O(n*k) brute force into O(n) by incrementally updating the window instead of recalculating from scratch.
Coordinate multiple threads or processes using locks, semaphores, or barriers.
Order vertices in a directed acyclic graph (DAG) such that for every edge u -> v, vertex u comes before v in the ordering.
A tree-like data structure for efficient string prefix operations. Each node represents a character, and paths from root to nodes spell out prefixes. Tries enable O(m) search, insert, and prefix queries where m is the word length.
Use two pointers to traverse data from different positions, often moving toward or away from each other. This technique transforms O(n²) brute force into O(n) by eliminating redundant comparisons.
Track disjoint sets with efficient union and find operations. Union-Find (also called Disjoint Set Union) excels at dynamically grouping elements and answering "are these two elements in the same group?" queries.