Coding interviews hinge on recognizing patterns rather than inventing new algorithms. Research shows that a small set of techniques (two pointers, sliding windows, hash tables, DFS/BFS, DP, greedy, etc.) covers ≈90% of interview problems. The key is to start every problem with a brute‐force plan (to truly understand the problem) and then systematically optimize it by spotting and eliminating bottlenecks. For example, if the brute solution uses nested loops to check all pairs in a sorted array, we switch to a two-pointer approach and cut O(n²) down to O(n). Likewise, repeated subproblem work suggests dynamic programming (memoization/tabulation), and checking contiguous ranges hints at a sliding window or prefix-sum trick. This report synthesizes authoritative sources into a mechanical decision system:

• Recognition Cues: An explicit checklist of features in problem statements (e.g. “sorted array” or “pairs” → two pointers; “subarray”/“substring” → sliding window; “count/frequency” → hash maps; “tree/graph” → DFS/BFS; “combinations” → backtracking; “overlapping subproblems” → DP; “local greedy choice possible” → greedy, etc.).
• Decision Flowcharts: Flowcharts (below) map input characteristics to likely patterns (two-pointer vs sliding-window vs hashing vs tree/graph vs DP, etc.), yielding a step-by-step “pattern of thought” when reading a problem.
• Core Templates: 20–30 skeleton code templates (in pseudocode/C++) with annotations. For each, we include the clue that should immediately suggest using that template (e.g. sorted array + find pair → two-pointer loop).
• Brute→Optimal Procedure: A formalized, almost-algorithmic approach to improving brute solutions: identify and remove bottlenecks (BUD: Bottlenecks, Unnecessary work, Duplicated work), use additional data structures or precomputation (e.g. hash tables, prefix sums), and apply classic transforms (sort+two-pointer, recursion→DP). This covers ~99% of interview optimizations, as corroborated by sources on interview strategy.
• Worked Examples: We show 8 diverse problems (one per category) in detail, each with a brute-force solution annotated and then a step-by-step derivation of the optimized solution. These include array and string problems, sliding-window and two-pointer cases, hashing examples, tree (DFS/BFS) examples, a graph example, a DP problem, and a greedy problem. Each example’s solution path is mechanical: “Here’s the brute, we identify X in it as a bottleneck, so apply transformation Y (pattern Z) → new solution.”
• Cheat-Sheet Tables: We compile a one-page cheat sheet and tables: (a) Recognition Checklist mapping problem features (clues) to patterns, (b) Template Summary mapping pattern → code skeleton + clues, and (c) Example Comparisons showing sample problems, their brute vs optimal complexities, and the pattern used.
• Daily Practice Workflow: Finally, we propose a structured study plan: learn patterns in small blocks, solve a few representative problems per pattern, and review your cheat sheet daily (e.g. 15 min mental warmup before practice/tests). This keeps patterns fresh so that in an interview you “show up to fight” ready, not scrambling to recall fundamentals.

All claims are backed by authoritative interviews and algorithm guides. Key references include pattern cheat sheets, the well-known Cracking the Coding Interview strategy (BUD optimization), and educational blogs (Byte-by-Byte, Code & Debug, Interview Coder, Medium articles, etc.) that emphasize pattern-centric problem solving.

When reading a problem, first catalog its key features. Use the following checklist of clues to map to known patterns：

• Data Structure/Input Type:

  • Array or String: Look for sorted order, contiguous segments, or frequency/count clues.
  • Linked List: Linked-list-specific (e.g. pointers, “next”/“random” references).
  • Binary Tree/Tree: Parent-child language, subtrees, ancestors.
  • Graph or Grid: Mentions of nodes/edges, connectivity, grids, networks.

• Sorted Input / Pair/Triplet: “Sorted array” or “find two/three numbers that….” → Two Pointers. E.g. “sorted”, “two sum”, “3Sum”, “container with most water” hint two-pointer.

• Contiguous Subarray/Substring: Words like “subarray”, “substring”, “window”, “at most K distinct”, “max/min sum of subarray of size K” → Sliding Window. E.g. “Longest substring without repeating” or “min window substring” strongly imply sliding-window optimization (often from a naive O(n²) scan to O(n)).

• Fixed-Size Subarray: If the length K is fixed, use a Fixed-Window sliding-window (move by one each time). If the window size can vary (e.g. “at most K distinct chars”, “⇐ S sum condition”), use a variable-size sliding window, expanding/shrinking two pointers.

• Search / Monotonicity: If the problem space is sorted or monotonic (e.g. “search in a matrix”, “find minimum/maximum satisfying property”), consider Binary Search (or binary-search-on-answer for numeric search spaces).

• Counting / Existence Check: If you need fast membership tests, frequencies, or to de-duplicate, use a Hash Table / HashSet. E.g. “count pairs with sum=K” or “are two strings anagrams?” suggests hashing or counting arrays.

• Stack / Next Greater: If the problem involves matching or sequential structure (parentheses, evaluating expressions, or “next greater element” problems), consider a Stack (especially monotonic stack for next-greater patterns).

• Queues / BFS: If you see levels or layers or “shortest path in unweighted graph or grid,” use BFS. Common words: “levels”, “minimum number of steps”, “rotten oranges” (spread in minutes).

• DFS (Graph/Tree): If the task is about connectivity (“number of connected components”, “dfs traversal”), or exploring all branches (“max depth of tree”, “path existence”), use DFS recursively or with stack.

• Tree-Specific (Binary Tree): For binary trees, ask: “Is this about root-to-leaf paths, tree depth, or combining child results?” That suggests DFS recursion (preorder/inorder/postorder templates). If it’s level-by-level, use BFS (queue).

• Graph-Specific: If connections form a graph, apply BFS/DFS for connectivity (visited set), or use topological sort for ordering with prerequisites (e.g. course schedule). Cycle detection calls for DFS or Union-Find; shortest paths (unweighted) → BFS.

• All Combinations / Permutations: Words like “generate all subsets/permutations”, “find all combinations summing to X”, “N-Queens”, etc., indicate Backtracking (DFS with undo).

• Overlapping Subproblems: If the brute would recompute the same state many times (typical recursion with repeated subcalls), use Dynamic Programming (memoization or tabulation). Clues: “max sum/ways to reach N”, “count ways with constraints”, “largest common subsequence”, etc.

• Local Greedy Choice Possible: Problems that say “maximize/minimize by choosing local best” (e.g. Activity Selection, Fractional Knapsack) often allow a Greedy solution. Clues: tasks or intervals to schedule, and it’s known local-optimal→global-optimal.

• Kth/Largest/Top-K: Terms like “Kth largest element”, “top K frequent” → use a Heap/Priority Queue. For median, merging sorted lists → heap.

• Bitwise Tricks: If there’s a bit-level twist (“find single number with XOR”, “check if power of two”, “count set bits”), use bit manipulation (XOR, shifts).

• Range Sum Queries / Prefix Sums: When the problem repeatedly asks for sums over subarrays or submatrices, look for a Prefix Sum trick (precompute cumulative sums so ranges are O(1) queries). Eg. “subarray sum equals K” often becomes prefix-sum + hashmap.

Each of the above checks should trigger immediately as you read the problem. The decision flowchart below formalizes these checks (array/string vs tree vs graph, sorted vs contiguous, etc.) so you can narrow in on 1–2 likely patterns. The recognition checklist table at the end summarizes these cues in one place.

Example Cues (from sources): “Sorted array, find pairs” → two pointers. “Subarray/substring, contiguous” → sliding window. “Need O(1) lookup or frequency counts” → hashing. “Parent-child nodes” → DFS/BFS on trees. “All combinations” → backtracking. These cues are echoed in interview-prep guides as the top signals of which template to use.

Based on the checklist, we create flowcharts that start with the problem’s structure and lead to candidate patterns. The chart below (in Mermaid syntax) shows a top-down decision process. It first branches by input type, then by key clues. (In practice you’d do this reasoning mentally in seconds.)

graph TD
    A[START: Read Problem] 
    A --> B{Input Type?}
    B -->|Array / String| C{Sorted?}
    B -->|Linked List| LL[Linked-List Tricks (fast/slow, reverse)]
    B -->|Binary Tree / Tree| T{Tree Task?}
    B -->|Graph / Grid| G{Graph Task?}
    B -->|Other (Number, etc.)| O{Check Others}
    
    C -->|Yes, need pairs/triplets| TwoP[Two Pointers (e.g. sorted 2-sum)]
    C -->|Yes, other search| Bin[Binary Search (sorted/monotonic)]
    C -->|No| D{Contiguous?}
    D -->|Yes (subarray/substring)| Win[Sliding Window]
    D -->|No| H{Count/Lookup?}
    H -->|Yes (counts, existence)| Hash[Hash Table (map/set)]
    H -->|No| O
    
    T -->|Level/Shortest Path| TBFS[BFS on Tree (level-order)]
    T -->|Path/Subtree/Properties| TDFS[DFS on Tree (recursive)]
    
    G -->|Connected components| BFS[Graph BFS/DFS (visit)]
    G -->|Shortest path| BFS
    G -->|Cycle/Topo?| Topo[Topological Sort / Cycle detection]
    
    O -->|Generate combinations| BT[Backtracking/Recursion]
    O -->|Optimal substructure| DP[Dynamic Programming (recursion+memo)]
    O -->|Greedy condition| GR[Greedy (sort+select)]
    O -->|Need top K| HP[Heap/Priority Queue]
    O -->|Bit-level ops| BitX[Bit Manipulation]

Above, each diamond “Yes/No?” test checks a feature (sorted array? contiguous subrange?) and each box is a pattern/template with a key source citation. For example, if the input is an array and sorted and we need pairs/triples, we go to Two Pointers. If it’s not sorted, we ask “contiguous subarray?” to decide on sliding window, otherwise “need count?” for hashing. Trees lead to BFS/DFS templates, graphs to BFS/DFS or topological, and “Other” leads to backtracking/DP/greedy/heap/bit.

This “decision tree” aligns with interview guidance: first classify problem type, then pick from the 20–30 templates.

Below are core code templates (in C++/pseudocode form) for ~20 common patterns. Each template is annotated and paired with the key clue that should trigger its use. For brevity we show representative code; variants (e.g. DFS recursive vs iterative) follow the same logic.

• Two Pointers (Sorted Array):

  int l=0, r=n-1;
  while(l < r) {
      int s = nums[l] + nums[r];
      if(s == target) {  // found pair
          // process pair
          l++; r--;
      }
      else if(s < target) {
          l++;
      } else {
          r--;
      }
  }

  When to use: Sorted array + find pair/triplet (e.g. 2-sum, 3-sum). Key idea: move one pointer from start and one from end, narrowing range in O(n) instead of O(n²) nested loops.

• Sliding Window (Contiguous Subarray):

  int l=0, sum=0;
  for(int r=0; r<n; r++) {
      // add nums[r] into window
      sum += nums[r];
      // while window violates constraint, shrink from left:
      while(l <= r && /* condition broken, e.g. sum>k */) {
          sum -= nums[l++];
      }
      // now [l..r] is valid window: update answer (length, sum, etc.)
  }

  When to use: Tasks asking about subarrays/substrings (max/min sum, longest unique, etc.). Key idea: maintain a moving window [l..r], expanding r and contracting l as needed. Avoids recomputing sums by updating incrementally in O(n).

• Fixed-Size Window (special case):

  int sum=0;
  // first window [0..k-1]:
  for(int i=0; i<k; i++) sum += nums[i];
  ans = someFunc(sum);
  for(int i=k; i<n; i++) {
      sum += nums[i] - nums[i-k];  // slide by 1
      ans = max(ans, someFunc(sum));
  }

  Clue: Asked for subarray of exactly size k (e.g. “max sum of any k-length subarray”). Equivalent to sliding window with fixed width: add new element and subtract element leaving window (O(n)).

• Binary Search (Sorted/Monotonic):

  int lo = 0, hi = n-1;
  while(lo <= hi) {
      int mid = lo + (hi-lo)/2;
      if(nums[mid] == target) return mid;
      else if(nums[mid] < target) lo = mid+1;
      else hi = mid-1;
  }
  return -1;

  When to use: Input is sorted or search space is monotonic (e.g. find element in sorted array, or binary search on answer space). Complexity O(log n). Pattern reduces search space by half each step.

• Hash Table (Counting/Lookup):

  unordered_map<int,int> mp;
  for(int x: nums) {
      // Example: count occurrences or store index
      mp[x]++;
  }
  // Use mp[.] for O(1) lookup:
  if(mp.count(key)) { ... }

  When to use: Need O(1) lookups, count frequencies, check existence. Common for “two sum unsorted” (store indices), subarray-sum (prefix sums in map), or any grouping by value.

• Stack (Monotonic/Matching):

  stack<char> st;
  for(char c: s) {
      if(c=='(') st.push(c);
      else {
          if(st.empty()) return false;
          st.pop();
      }
  }
  // or for next-greater: pop while current > top

  When to use: Matching brackets, expression evaluation, or next-greater problems. Key: use LIFO property. Monotonic stack variant: while stack.top() ⇐ current, pop, etc.

• Queue (BFS):

  queue<Node*> q;
  q.push(root);
  while(!q.empty()) {
      Node* cur = q.front(); q.pop();
      // process cur
      if(cur->left) q.push(cur->left);
      if(cur->right) q.push(cur->right);
  }

  When to use: Level-order traversal of trees/grids; shortest-path in unweighted graph (BFS). Insert neighbors or children into queue to ensure FIFO order.

• DFS (Recursive/Stack):

  void dfs(Node* u) {
      visited[u] = true;
      for(Node* v: neighbors[u]) {
          if(!visited[v]) dfs(v);
      }
  }

  When to use: Explore all nodes in a component, compute subtree values, or search for a property. Recursion or manual stack for trees/graphs. Useful when structure is recursive (trees, backtracking).

• Linked List (Fast/Slow, Reversal):

  // Fast-slow pointer (cycle detect or find middle):
  ListNode *slow=head, *fast=head;
  while(fast && fast->next) {
      slow = slow->next;
      fast = fast->next->next;
      if(slow == fast) { /* cycle detected */ }
  }
   
  // Reverse list template:
  ListNode *prev=nullptr, *cur=head;
  while(cur) {
      ListNode* next = cur->next;
      cur->next = prev;
      prev = cur;
      cur = next;
  }
  head = prev;

  When to use: Any problem on linked lists (reordering, cycle detection, etc.). Fast/slow is key for middles and cycles; reversal trick for in-place reordering.

• Backtracking (Generate All Combinations):

  void backtrack(vector<int>& path, int start) {
      // maybe save path if needed
      for(int i=start; i<n; i++) {
          path.push_back(nums[i]);
          backtrack(path, i+1);
          path.pop_back();  // undo choice
      }
  }

  When to use: Generate subsets/permutations/combinations. The skeleton is: loop over choices, recurse, then undo (backtrack). Use pruning (stop early) if constraints break.

• Dynamic Programming (Recursion + Memo):

  unordered_map<State,Result> memo;
  Result dp(State s) {
      if(memo.count(s)) return memo[s];
      // base case(s)
      // combine results of smaller states
      memo[s] = /* computed result */;
      return memo[s];
  }

  When to use: Overlapping subproblems with optimal substructure. Start with a recursive solution (often naive exponential), then add memo to avoid recomputation. Alternatively, build a table bottom-up once states and transitions are clear.

• Greedy (Sort + Sweep):

  sort(intervals.begin(), intervals.end(), cmpEnd);
  int count=0, last_end = -INF;
  for(auto& iv: intervals) {
      if(iv.start >= last_end) {
          count++;
          last_end = iv.end;
      }
  }

  When to use: If a local choice (like earliest finish time) leads to a global optimum. Typical for interval scheduling, selecting min platforms, etc. Pattern: sort by key (end times, capacities) then linearly scan.

• Heap / Priority Queue:

  priority_queue<int, vector<int>, greater<int>> pq; // min-heap
  for(int x: nums) {
      if(pq.size() < k) pq.push(x);
      else if(x > pq.top()) {
          pq.pop(); pq.push(x);
      }
  }

  When to use: Find Kth largest/smallest, maintain top-K frequent, merge K sorted lists. Maintain a heap of size K. Complexity often O(n log K).

• Bit Manipulation:

  int xor_sum = 0;
  for(int x: nums) xor_sum ^= x;  // finds unique element if all others are paired
  if((n & (n-1)) == 0) { /* n is power of 2 */ }

  When to use: Problems involving XOR, parity, binary representations. Trick: XOR cancels pairs (a⊕a=0), and shifts/test bits for count or power-of-two checks.

• Prefix Sum (with Hash):

  int count=0, prefix=0;
  unordered_map<int,int> mp; mp[0]=1;
  for(int x: nums) {
      prefix += x;
      // see if (prefix - target) seen before
      if(mp.count(prefix - target)) count += mp[prefix - target];
      mp[prefix]++;
  }

  When to use: Subarray-sum problems (“count subarrays summing to K”) or any cumulative property queries. Precompute running sum and use a map to check ranges in O(1). Brute was O(n²); prefix+map is O(n).

Each template above is used mechanically: you should be able to glance at a problem, spot a clue word/structure, and recall the relevant snippet. For example, if the input is a string and the problem asks for “longest substring with X property,” immediately think of sliding-window code. If it says “binary tree maximum depth,” recall the DFS recursion skeleton. These templates, once internalized, turn problem-solving into almost plug-and-play.

Table: Templates Summary

(See the Recognition Checklist table below for exact clue words that hint each template.)

We formalize a step-by-step recipe for improving any brute-force solution. This approach appears in sources from Byte-by-Byte to Cracking the Coding Interview and works for ~99% of coding problems:

1. Brute-Force First: Write (or at least verbalize) the simplest correct solution without regard to efficiency. Often this is nested loops or complete recursion. Do not code yet; explain it out loud and note its complexity. This ensures you understand the problem fully.

2. Find Bottlenecks: Identify the slow parts of the brute solution. Common bottlenecks are double/triple loops (O(n²), O(n³) work), repeated work in recursion, or unnecessary recomputation. Ask: Why is this slow? What is it doing that repeats? For example, summing over all subarrays is O(n²) work; checking each pair is O(n²); DFS from each graph node is O(V²) etc.

3. BUD Optimization: Apply the “BUD” heuristic:

   • Bottlenecks: Locate the exact inner loop or recursion that dominates time.
   • Unnecessary Work: See if any computation can be skipped or done just once (e.g. precompute something rather than recompute each time).
   • Duplicated Work: If the same result is computed multiple times for different inputs, store and reuse it (memoize or use a table).

4. Use Data Structures / Precomputation: If the brute does repeated scans or checks, often adding an auxiliary data structure helps. Common moves:

   • Use a HashMap/Set to replace an inner loop with O(1) lookups (trade space for time). (E.g. replace checking “does any previous number = target-num” by storing seen numbers.)
   • Use prefix sums to answer range-sum queries in O(1) instead of summing in O(n).
   • Sort data if needed so that faster patterns apply (e.g. sort unsorted array to allow two-pointer or binary search).

5. Pattern Substitution: Recognize if the problem fits a known pattern from Step 2, and replace the brute part with the corresponding template. For example:

   • If brute had two nested loops over a sorted array, switch to two-pointer loops.
   • If brute was sliding a window with inner sums (O(n²)), switch to sliding-window (update sum in O(1) each step).
   • If brute was recursively exploring without storing, add memoization (or iterative DP).
   • If brute tried all orderings, switch to greedy or graph algorithms (e.g. topological sort) if applicable.

6. Analyze & Refine: After substitution, compute the new complexity. Check if all parts are optimal (usually O(n), O(n log n), or O(V+E) for BFS/DFS). If still too slow, go back to find any remaining bottleneck. In practice, one pass of pattern substitution solves nearly all interview problems.

7. Code & Test: Once the optimal approach is sketched (e.g. “use hash map to get O(n)”), code it cleanly. The structure is usually similar to the brute (same variables/loops) with a few insertions/changes. Then test on examples and edge cases.

This methodic approach (brute → optimize by pattern) is emphasized by experts. For example, for subarray-sum problems one “simple optimization” is often prefix sums+hashmap; for recursion with overlapping subcalls, the answer is memoization.

Common Optimizations (from sources):

• Memoization (DP): If brute recalculates the same subproblem, store results.
• Prefix Sum + Hash: Turn O(n²) range-sum check into O(n) by storing running sums.
• Sort + Two Pointers: Replace quadratic pair search with linear pointers.
• Sliding Window: Replace nested loops over subarrays with one-pass window.
• Hash Table for Fast Lookup: Replace “find if exists” inner loops with O(1) map checks.
• Time–Space Tradeoff: As one source notes, “Hash tables are especially useful! Make a time vs. space tradeoff”. Using extra memory (maps, arrays) can often cut time drastically.

Below is a one-page reference. On the left we list problem clues/features, in the middle the pattern/template to apply, and on the right the time complexity (optimal vs brute). Use this as a quick lookup during practice or a final mental review.

(This table consolidates the above clues and templates; it can be printed or kept handy as the “brain dump” before a quiz or interview.)

A disciplined daily routine cements the above system into reflex. The recommendation from experts and top-prepared candidates is: focus on patterns, not random problems. For example, Code & Debug suggests a phased approach:

• Phase 1 (Weeks 1–2): Master Arrays/Strings patterns – two pointers, sliding window, hashing. Solve ~5–8 problems each.
• Phase 2 (Weeks 3–4): Sorting, Stacks, Linked Lists, Binary Search – practice known questions under each template.
• Phase 3 (Weeks 5–6): Trees and Graphs – BFS/DFS, topological sort, union-find. Again, 5–8 problems per pattern.
• Phase 4 (Weeks 7–8): Recursion/Backtracking and DP – tackle subset/perm problems and classical DP (Fibonacci, knapsack, LCS).

Concurrently (ongoing), drill Greedy, Heap, Bit Manipulation tasks as they appear. Crucially, do not solve blind random problems. After each practice problem, ask yourself (as one cheat sheet advises) “What pattern was this? How would I recognize it next time?”.

Before every mock interview or whiteboard session, do a 15-minute “warmup” with your cheat sheet: quickly scan the list of patterns, any complexity notes, and glance at your template sketches. This primes your pattern-recognition “muscle memory” so that during the interview you react in seconds rather than scrambling. For example, interview coaches recommend reviewing a one-page summary of templates and common pitfalls (nulls, off-by-one) right before coding.

Practice Tips:

• Always start by verbalizing the brute approach, even if you optimize immediately. This prevents you from missing corner cases.
• Time each session, aim for clarity and structured answers (like the BUD optimization approach) rather than just racing to code.
• After solving, annotate your solution with pattern labels. E.g., label “Sliding Window” on a solved subarray problem. Repeatedly linking problems to patterns reinforces recognition.
• Use the tables above for quick quiz-style recall. For instance, randomly pick a clue (e.g. “prefix sum”) and recite which template to use.

By integrating pattern study, cheat-sheet review, and deliberate practice of a few problems per pattern, you transform problem-solving into a near-mechanical algorithm. Over time, reacting in 30 seconds from problem statement to pattern (as the “30-second rule” suggests) becomes achievable. In sum: practice smart, not just hard – focus on the 20% of concepts that yield 80% of interview problems.

Recognition Checklist: Features (left) → Likely Pattern(s) (right).

Template Summary: Pattern → Skeleton Code → Clue (see above).

Example Problem Comparisons: Brute vs Optimal, with pattern and complexities.

These tables condense the above detail. For each real interview problem, you should be able to quickly locate a row that matches its clues, then recall the template and complexity.

Sources: Key facts above are drawn from expert sources. For instance, pattern-covering advice comes from interview cheat-sheets; the brute→optimize approach is advocated by Byte-by-Byte and Gayle McDowell; each pattern’s use-cases and examples are confirmed in multiple blogs.