Coding Interview Patterns

1. Master the structured interview framework over raw coding speed

Interviewers aren't just looking for the correct solution, they're interested in understanding how you approach the problem, think through different solutions, and communicate your reasoning clearly.

Structured problem-solving. Diving straight into code without clarifying requirements is a major red flag for interviewers. A successful candidate uses a systematic six-step framework: clarifying the problem, designing the algorithm, estimating initial complexity, writing clean code, restating final complexity, and testing edge cases.

Communication as code. The coding interview is a collaborative conversation rather than a silent exam. Thinking out loud allows the interviewer to guide you when stuck and understand your architectural trade-offs. Key communication strategies include:

• Restating the problem in your own words to align expectations.
• Discussing brute-force solutions before optimizing.
• Explaining trade-offs between different data structures.

Proactive testing. Writing code is only half the battle; you must prove its correctness. Walk through your code with simple, boundary, and extreme test cases to catch off-by-one errors. This demonstrates high-quality engineering discipline and debugging skills.

2. Leverage Two Pointers to eliminate nested loops in linear structures

Often, this approach does not take advantage of predictable dynamics that might exist in a data structure.

Predictable dynamics. When dealing with sorted arrays or symmetrical structures, nested loops often perform redundant comparisons, resulting in $O(n^2)$ time complexity. By introducing a second pointer, we can exploit sorted properties to make logical decisions and reduce the runtime to $O(n)$.

Three core strategies. Depending on the problem's nature, pointers can traverse the data structure in different directions. The primary pointer configurations are:

• Inward traversal: Pointers start at opposite ends and move toward the center (e.g., Pair Sum - Sorted, Palindromes).
• Unidirectional traversal: Both pointers move in the same direction at different paces to track and find information.
• Staged traversal: One pointer searches for a condition, triggering the second pointer to gather additional context.

Logical pointer movement. In problems like "Largest Container," we maximize width initially by placing pointers at the boundaries. We then greedily move the pointer pointing to the shorter line inward, as only a taller line can offset the loss in width.

3. Use Hash Maps and Sets to trade space for constant-time lookups

For each number x in nums, we need to find another number y such that x + y = target, or in other words, y = target - x.

Trading space for time. When searching for elements or checking for duplicates, linear scans degrade performance. By utilizing hash maps or sets, we can store previously visited elements and perform lookups in $O(1)$ average time.

Complement tracking. In the "Pair Sum - Unsorted" problem, we can find the target pair in a single pass. As we iterate, we check if the current number's complement already exists in our hash map; if not, we store the current number and its index.

Multi-dimensional indexing. Hash sets can also validate complex structures like Sudoku boards. By mapping rows, columns, and $3 \times 3$ subgrids to distinct hash sets, we can detect duplicates in a single pass. We index the subgrids by dividing row and column coordinates by 3.

4. Deploy Fast and Slow Pointers for cycle detection and midpoint identification

The fast pointer moves 2 steps at a time, and the slow pointer moves 1 step at a time, so the fast pointer will gain a distance of 1 node over the slow pointer at each iteration.

Floyd's cycle detection. Detecting cycles in a linked list or numerical sequence without extra space seems impossible. However, by moving a fast pointer at twice the speed of a slow pointer, the fast pointer will inevitably catch up to the slow pointer if a cycle exists.

Midpoint identification. Fast and slow pointers also find fractional points in a single pass. When the fast pointer reaches the end of a linked list, the slow pointer is guaranteed to be at the exact midpoint. This is highly useful for:

• Splitting a linked list in half for merge sort.
• Checking if a linked list is a palindrome.
• Finding the $k$-th node from the end.

Mathematical cycle mapping. This pattern extends beyond linked lists to abstract state spaces, such as determining "Happy Numbers." By treating the digit-square-sum operation as a transition to the next node, we can detect infinite loops using the same pointer mechanics.

5. Optimize contiguous subarrays using Fixed and Dynamic Sliding Windows

If a fixed window of length k traverses a data structure from start to finish, it's guaranteed to see every subcomponent of length k in that data structure.

Subarray optimization. Many string and array problems ask for the longest, shortest, or target subcomponents. Instead of recalculating the properties of every possible subarray, a sliding window maintains a running state as it slides across the data structure.

Window mechanics. The window's boundaries are controlled by two pointers that expand or shrink the window dynamically. The two main types of windows are:

• Fixed sliding windows: Maintain a constant size $k$ to evaluate fixed-length substrings (e.g., Substring Anagrams).
• Dynamic sliding windows: Expand the right pointer to find valid states, and shrink or slide the left pointer when constraints are violated.

State tracking. To make the window efficient, we must update its internal state (like character frequencies) in $O(1)$ time during pointer shifts. In "Longest Uniform Substring After Replacements," we track the highest frequency character to determine if the remaining characters can be replaced within our budget $k$.

6. Reframe Binary Search around search spaces rather than sorted arrays

This is an example of a common application of binary search, where the search space does not encompass the input array.

Beyond sorted arrays. While binary search is traditionally taught as a tool to find an element in a sorted array, its true power lies in searching over any monotonic search space. If a decision function yields a sequence of "True" followed by "False" values, we can use binary search to find the boundary.

Boundary targeting. Implementing binary search correctly requires precise control over pointer updates and midpoint calculations. We must distinguish between:

• Lower-bound search: Finding the first element that satisfies a condition (using right = mid).
• Upper-bound search: Finding the last element that satisfies a condition (using left = mid and biasing the midpoint to the right with + 1 to avoid infinite loops).

Non-intuitive search spaces. In "Cutting Wood," the search space is the range of possible woodcutter heights $[0, \text{max_height}]$. We binary search this range, using a helper function to check if a given height yields enough wood, reducing the runtime to $O(n \log m)$.

7. Utilize Monotonic Stacks and Priority Heaps to track dynamic order

A heap is a data structure that organizes elements based on priority, ensuring the highest-priority element is always at the top of the heap.

Monotonic stacks. Stacks are excellent for parsing nested structures, but they can also maintain a sorted order of elements. A monotonic stack stores elements in a strictly increasing or decreasing order by popping elements that violate the order before pushing a new one.

Priority queues. Heaps provide $O(1)$ access to the minimum or maximum element while allowing insertions and deletions in $O(\log n)$ time. They are ideal for:

• Finding the $k$ most frequent elements in a stream.
• Merging $k$ sorted linked lists by tracking the head of each list.
• Dynamically calculating the median of an incoming stream of integers.

Dual-heap median tracking. To find the median of a data stream in real-time, we split the data into two halves. We use a max-heap to store the smaller half and a min-heap to store the larger half, keeping their sizes balanced within one element of each other.

8. Simplify range queries and cumulative products with Prefix Sums

The key observation here is that the sum of the range [2, 4] can be obtained by subtracting the sum of the range [0, 1] from the sum above.

Precomputing cumulative states. Calculating the sum of arbitrary subarrays repeatedly leads to inefficient $O(n)$ queries. By precomputing a prefix sum array where each index stores the cumulative sum from the start, we can resolve any range query in $O(1)$ time.

Subarray sum formula. The sum of any subarray between indexes $i$ and $j$ is calculated as prefix_sum[j] - prefix_sum[i - 1]. This mathematical relationship allows us to:

• Perform constant-time range sum queries.
• Find the number of subarrays that sum to a target $k$ in $O(n)$ time using a hash map.
• Track cumulative products from both directions to solve product-array problems without division.

Space-optimized prefix products. In "Product Array Without Current Element," we can avoid division and extra space. We perform one pass to store left-side prefix products in the output array, and a second reverse pass to multiply them by right-side suffix products on the fly.

9. Navigate hierarchical data and prefix matches using Trees and Tries

This is, in essence, how a trie works: by allowing words to reuse existing nodes based on shared prefixes, it efficiently stores strings in a way that minimizes redundancy.

Hierarchical traversals. Trees are hierarchical structures traversed using Depth-First Search (DFS) or Breadth-First Search (BFS). DFS is typically implemented recursively to evaluate subtrees, while BFS uses a queue to process nodes level by level.

Prefix trees. A Trie is a specialized tree where each node represents a character, allowing words with shared prefixes to share nodes. This structure is highly efficient for:

• Searching for words or prefixes in $O(k)$ time, where $k$ is the word length.
• Implementing autocomplete systems.
• Matching words with wildcards using recursive backtracking.

Board word search. In "Find All Words on a Board," we combine a Trie with backtracking. By traversing the board and the Trie simultaneously, we can search for multiple words efficiently, pruning paths as soon as they deviate from the Trie's branches.

10. Solve complex combinatorial and optimization problems with Backtracking and Dynamic Programming

DP is the antidote to this. It's a technique that stores solutions to each subproblem, so they can be reused when they're needed again.

Combinatorial search. Backtracking is a systematic brute-force method that explores all possible decisions in a state space tree. When a path violates constraints, the algorithm backtracks by undoing the last decision and trying alternative branches.

Dynamic programming. When subproblems overlap, backtracking becomes highly inefficient. Dynamic Programming optimizes this by storing subproblem solutions, either top-down using memoization or bottom-up using a DP table. Key DP concepts include:

• Optimal substructure: Building the global optimal solution from optimal subproblems.
• Overlapping subproblems: Solving the same subproblems repeatedly.
• State reduction: Minimizing space by only keeping track of the previous states needed for the current calculation.

Decision-making frameworks. In "0/1 Knapsack," we make a binary decision for each item: include it or exclude it. By defining our state based on the current item and remaining capacity, we can build a bottom-up DP table to find the maximum value in $O(n \cdot \text{capacity})$ time.