DSA Pattern Recognition - FAANG Interviews Prep Tips

This pattern focuses on finding pairs or groups of numbers in an array summing to a target. It's a cornerstone for FAANG interviews due to its versatility.

• Core Concept: Identify pairs (2-sum), triplets (3-sum), or k-elements summing to a target. Start with brute force O(n²) for pairs, optimize to O(n) using hash maps (store complements: target - num) or O(n log n) with sorting + two pointers.
• Extensions: k-sum reduces to (k-1)-sum recursively. Handle duplicates via sorting and skipping identical elements or using sets for unique results.
• FAANG Focus: Variations like closest sum, count occurrences, or handling negatives. Tests ability to optimize and manage edge cases (duplicates, zeros).

• Cues: Look for phrases like "find pairs/triplets summing to target," "unique combinations," or "closest sum to target."
• Interviewer Hints:
  • "Can you do better than O(n²)?" → Suggests hash map or sort + pointers.
  • "How do you handle duplicates?" → Skip identical values after sorting.
  • "Is the array sorted?" → If yes, use pointers; if no, hash or sort first.
• Break the Problem: Ask clarifying questions like:
  • Are negative numbers allowed?
  • Return indices or values?
  • Handle duplicates or ensure unique results?

• Compare time/space trade-offs (hash vs. pointers).
• Handle large inputs (avoid O(n^k) for k>2).
• Prove correctness of duplicate handling.
• Modify for counting solutions or finding closest sum.

• Start with brute force O(n²) nested loops.
• Optimize to hash map or sort + two pointers.
• Dry-run: [2,7,11,15] target=9 → [(2,7)].
• Analyze: O(n) time (hash), O(n) space or O(n log n) time (sort), O(1) space.
• Edges: All zeros, negatives, no solution, duplicates.

Optimizes subarray or substring problems by maintaining a window, avoiding redundant scans. Critical for FAANG due to O(n) efficiency.

• Fixed Window: Constant size k, slide right, update by subtracting left, adding right (e.g., max sum of k elements).
• Variable Window: Expand right, shrink left when condition fails (e.g., duplicates, sum > target). Use hashmap for counts, deque for monotonic order.
• FAANG Focus: Combines with prefix sums or monotonic queues. Tests ability to adapt to min/max windows, handle constraints like character sets.

• Cues: "Longest/shortest subarray with property," "max sum of k elements," "substring with no repeats."
• Interviewer Hints:
  • "Can you solve in one pass?" → Single-pass window.
  • "What if k is given?" → Fixed window.
  • "Handle dynamic size?" → Variable window with hash/deque.
• Break the Problem: Ask:
  • Fixed or variable window?
  • Constraints on elements (chars, numbers)?
  • Return length or substring?

• Prove O(n) (each element added/removed once).
• Handle invalid windows or edge cases.
• Adapt to min/max or 2D windows.
• Space trade-offs for hash/deque.

• Brute: O(n²) check all substrings.
• Optimize: Window single pass O(n).
• Dry-run: "abcabcbb" no repeat → "abc" (len=3).
• Analyze: O(n) time, O(1) space (fixed alphabet).
• Edges: All same chars, empty input, single char.

Optimizes range-based or window-based array problems. Frequently used in FAANG for subarray sums or window extrema.

• Prefix Sum: Precompute cumulative sums for O(1) range queries (sum[i..j] = prefix[j] - prefix[i-1]).
• Monotonic Queue: Deque maintaining increasing/decreasing order for window max/min, pop invalid or smaller elements.
• FAANG Focus: Combines with hash for sum = k, or with sliding windows for dynamic ranges. Tests optimization and edge handling.

• Cues: "Count subarrays with sum = k," "range sum queries," "max in sliding window."
• Interviewer Hints:
  • "Can you precompute?" → Prefix sum.
  • "Efficient window max?" → Monotonic deque.
  • "Handle multiple queries?" → Prefix or segment tree.
• Break the Problem: Ask:
  • Multiple range queries?
  • Negative numbers or modulo?
  • Window size fixed or variable?

• Prove O(n) for deque (each element pushed/popped once).
• Handle negatives/zero in prefix sums.
• Extend to 2D prefix sums for matrices.
• Space trade-offs for hash or deque.

• Brute: O(n²) nested sums.
• Optimize: Prefix O(n) build, O(1) query; deque O(n).
• Dry-run: [1,2,3] range 1-2 → 5.
• Analyze: O(n) time, O(n) space (prefix/deque).
• Edges: Negatives, k=0, empty array.

Uses two pointers converging on sorted data (or same start for unsorted). Key for FAANG due to O(n) or O(n²) efficiency.

• Two Pointers: Start at ends (sorted) or same (unsorted), move based on sum/condition (e.g., sum < target → move left).
• k-Sum: Sort, fix k-2 elements, solve 2-sum with pointers. Skip duplicates for unique results.
• FAANG Focus: Often requires sorting unsorted inputs. Tests ability to handle duplicates, closest sums, or extensions to k>2.

• Cues: "Find pairs in sorted array," "unique triplets," "closest sum."
• Interviewer Hints:
  • "Use sorted property?" → Pointers.
  • "Handle duplicates?" → Skip identical values.
  • "Unsorted input?" → Sort first, discuss O(n log n).
• Break the Problem: Ask:
  • Is input sorted?
  • Return count, values, or indices?
  • Handle large k?

• Why sort first? (Enables pointers).
• Handle duplicates/overflow.
• Extend to k-sum for k>4 (recursive).
• Time complexity for large n.

• Brute: O(n^k) combinations.
• Optimize: Sort+Pointers O(n^{k-1}).
• Dry-run: [1,3,4,6] sum=7 → [(1,6)].
• Analyze: O(n²) for 3-sum, O(1) space.
• Edges: All same, negatives, no solution.

Explores all possible solutions via recursive DFS, backtracking on invalid branches. Common in FAANG for combinatorial problems.

• Core Concept: Build solutions incrementally, revert on failure. Perms: Swap elements or use used flags. Subsets: Include/exclude choices.
• Optimization: Prune branches early (constraints, duplicates). Sort for unique results.
• FAANG Focus: Tests recursion depth, pruning, and sometimes DP overlap for memoization.

• Cues: "Generate all perms/combinations," "solve without libraries," small n (10-20).
• Interviewer Hints:
  • "Explore all branches?" → Backtracking.
  • "Avoid duplicates?" → Sort or use set.
  • "Can you prune?" → Early constraint checks.
• Break the Problem: Ask:
  • Unique or all solutions?
  • Constraints on n?
  • Duplicates in input?

• Pruning techniques to reduce branches.
• Handle duplicates for unique results.
• Stack overflow for large n.
• Convert to iterative approach.

• Brute: Recursive build all solutions.
• Optimize: Prune dups, early checks.
• Dry-run: [1,2] perms → [[1,2],[2,1]].
• Analyze: O(n!) time, O(n) space.
• Edges: Duplicates, large n, empty input.

Binary search efficiently finds a target or boundary in sorted data or a monotonic search space. Critical for FAANG due to O(log n) efficiency.

• Core Concept: Divide search space in half, leveraging sorted property or monotonicity. For search-on-answer, apply binary search to a range of possible answers (e.g., min capacity, max distance).
• Variations: Standard (find target), boundary (find first/last occurrence), or answer search (test feasibility of mid value).
• FAANG Focus: Tests ability to identify monotonicity in abstract problems (e.g., min days, max profit) and handle edge cases like duplicates or no solution.

• Cues: "Find target in sorted array," "minimum value satisfying condition," "first/last occurrence."
• Interviewer Hints:
  • "Can you use the sorted property?" → Standard binary search.
  • "What if you guess the answer?" → Search-on-answer.
  • "Handle duplicates?" → Find first/last position.
• Break the Problem: Ask:
  • Is input sorted?
  • Find exact target or boundary?
  • Monotonic condition in problem?

• Prove O(log n) time (halving search space).
• Handle edge cases (no target, duplicates).
• Define monotonic function for search-on-answer.
• Adapt to unsorted data (sort first or other approach).

• Brute: Linear scan O(n).
• Optimize: Binary search O(log n).
• Dry-run: [1,3,5,6] target=5 → index 2.
• Analyze: O(log n) time, O(1) space.
• Edges: Target not found, duplicates, single element.

Dynamic Programming (DP) solves problems by breaking them into overlapping subproblems, storing results to avoid recomputation. Essential for FAANG optimization problems.

• 1D DP: Single state variable (e.g., index or sum). Build bottom-up or top-down (memoized recursion).
• 2D DP: Two variables (e.g., row+col, index+state). Common for strings, matrices, or knapsack variants.
• FAANG Focus: Tests state definition, transition logic, and space optimization (e.g., rolling arrays).

• Cues: "Optimal value," "count ways," "longest/shortest sequence," "matrix path."
• Interviewer Hints:
  • "Break into smaller problems?" → DP subproblems.
  • "Store intermediate results?" → Memoization or bottom-up.
  • "Reduce space?" → Optimize to 1D array or variables.
• Break the Problem: Ask:
  • Optimal or count all solutions?
  • Single or multiple states?
  • Constraints allow memoization?

• Define state and transition formula.
• Prove correctness of recurrence.
• Optimize space (e.g., 1D instead of 2D).
• Handle edge cases (empty, single element).

• Brute: Recursive O(2^n).
• Optimize: DP table or memo O(n).
• Dry-run: Climb stairs n=3 → 3 ways.
• Analyze: O(n) time, O(n) or O(1) space.
• Edges: Large n, constraints, base cases.

Graph traversal algorithms explore nodes and edges, critical for FAANG connectivity and path problems.

• BFS: Level-order traversal using queue, ideal for shortest paths in unweighted graphs.
• DFS: Deep exploration using recursion or stack, suited for detecting cycles, components, or paths.
• FAANG Focus: Tests graph representation (adj list/matrix), traversal efficiency, and modifications (e.g., bipartite, shortest path).

• Cues: "Find shortest path," "detect cycle," "connected components," "flood fill."
• Interviewer Hints:
  • "Need shortest path?" → BFS.
  • "Explore all paths?" → DFS.
  • "Graph representation?" → List vs. matrix trade-offs.
• Break the Problem: Ask:
  • Weighted or unweighted graph?
  • Directed or undirected?
  • Sparse or dense graph?

• Choose BFS vs. DFS based on problem.
• Handle cycles or disconnected graphs.
• Space/time trade-offs for adj list vs. matrix.
• Modify for weighted graphs or constraints.

• Brute: Explore all paths O(V^V).
• Optimize: BFS/DFS O(V+E).
• Dry-run: 3-node cycle, detect cycle → true.
• Analyze: O(V+E) time, O(V) space.
• Edges: Disconnected, single node, cycles.

Greedy algorithms make locally optimal choices to achieve a global optimum, common in FAANG for optimization problems.

• Core Concept: At each step, choose the best option (e.g., max profit, min cost) without reconsidering past choices.
• Key Insight: Works when local optimum leads to global (e.g., interval scheduling, fractional knapsack).
• FAANG Focus: Tests ability to prove greedy choice is optimal and handle edge cases where greedy fails.

• Cues: "Maximize/minimize value," "schedule tasks," "select non-overlapping intervals."
• Interviewer Hints:
  • "Best choice at each step?" → Greedy.
  • "Prove it’s optimal?" → Justify greedy property.
  • "When does greedy fail?" → Compare with DP.
• Break the Problem: Ask:
  • Is local optimum globally optimal?
  • Sort input by what criterion?
  • Handle overlapping cases?

• Prove greedy choice leads to global optimum.
• Compare with DP for correctness.
• Handle edge cases (e.g., equal intervals).
• Optimize sorting or selection logic.

• Brute: Try all combinations O(2^n).
• Optimize: Greedy O(n log n) with sorting.
• Dry-run: Intervals [[1,2],[2,3]] → select 2.
• Analyze: O(n log n) time, O(1) space.
• Edges: Overlapping intervals, empty input.

Heap maintains max/min elements efficiently, ideal for problems requiring dynamic ordering. Common in FAANG for top-k or scheduling problems.

• Core Concept: Min/max heap for O(log n) insert/delete, O(1) peek. Priority queue abstracts heap for custom ordering.
• Applications: Top-k elements, merge sorted lists, scheduling tasks by priority.
• FAANG Focus: Tests heap operations, custom comparators, and combining with other patterns (e.g., sliding window).

• Cues: "Top k elements," "merge sorted lists," "schedule tasks by priority."
• Interviewer Hints:
  • "Need smallest/largest k?" → Heap.
  • "Dynamic updates?" → Priority queue.
  • "Custom ordering?" → Define comparator.
• Break the Problem: Ask:
  • Min or max heap?
  • Size of k relative to n?
  • Dynamic insertions?

• Why heap over sorting?
• Handle custom priorities or ties.
• Optimize for small k (e.g., selection).
• Combine with other patterns (e.g., sliding window).

• Brute: Sort O(n log n).
• Optimize: Heap O(n + k log n).
• Dry-run: Top k=[4,5,6] k=2 → [5,6].
• Analyze: O(n + k log n) time, O(n) space.
• Edges: k=n, duplicates, empty input.

Trie (prefix tree) is a tree structure for efficient string operations, critical for FAANG problems involving prefixes or word searches.

• Core Concept: Each node represents a character, paths form strings. Supports O(m) insert/search/delete, where m is string length.
• Applications: Autocomplete, spell checker, prefix matching, word search in grids.
• FAANG Focus: Tests ability to implement trie node structure, optimize space (e.g., bitmaps), and combine with DFS/BFS.

• Cues: "Search words with prefix," "autocomplete suggestions," "word search in grid."
• Interviewer Hints:
  • "Efficient prefix search?" → Trie.
  • "Handle large dictionary?" → Optimize node structure.
  • "Combine with grid?" → Trie + DFS.
• Break the Problem: Ask:
  • Prefix-based or full word?
  • Case-sensitive strings?
  • Space constraints?

• Implement trie node and operations.
• Optimize space (e.g., array vs. hash for children).
• Handle edge cases (empty strings, no prefix).
• Combine with other patterns (e.g., DFS for word search).

• Brute: Linear search O(n*m).
• Optimize: Trie O(m) per operation.
• Dry-run: Insert "cat", search "ca" → true.
• Analyze: O(m) time, O(ALPHABET*m*N) space.
• Edges: Empty strings, no matches, large alphabet.

Union-Find (Disjoint Set Union) efficiently manages group connectivity, vital for FAANG graph and clustering problems.

• Core Concept: Maintains sets with union (merge) and find (root) operations. Optimizes with path compression and rank union for near O(1) operations.
• Applications: Detect cycles, connected components, Kruskal’s MST, or grid percolation.
• FAANG Focus: Tests implementation (array-based), optimization (path compression), and application to dynamic connectivity.

• Cues: "Detect cycle in graph," "group connected components," "merge regions."
• Interviewer Hints:
  • "Track group membership?" → Union-Find.
  • "Optimize operations?" → Path compression, rank.
  • "Dynamic connectivity?" → Union-Find over DFS.
• Break the Problem: Ask:
  • Number of merge operations?
  • Directed or undirected graph?
  • Need component sizes?

• Implement Union-Find with optimizations.
• Prove near O(1) with path compression.
• Handle edge cases (single node, no merges).
• Extend to weighted unions or component size.

• Brute: DFS per query O(V+E).
• Optimize: Union-Find O(α(V)) amortized.
• Dry-run: Merge 1-2, 2-3, check 1-3 → connected.
• Analyze: O(α(V)) time, O(V) space.
• Edges: Single node, all disconnected, large V.

Stack operates on LIFO (Last In, First Out), ideal for FAANG problems involving reversal, matching, or monotonic properties.

• Core Concept: Push/pop in O(1). Used for parentheses matching, monotonic stacks (next greater/smaller), or backtracking.
• Applications: Expression evaluation, validating sequences, finding next elements.
• FAANG Focus: Tests stack implementation, monotonic stack optimization, and combining with other patterns (e.g., histograms).

• Cues: "Validate parentheses," "next greater element," "evaluate expression."
• Interviewer Hints:
  • "Track last elements?" → Stack.
  • "Monotonic property?" → Monotonic stack.
  • "Reverse order processing?" → Stack.
• Break the Problem: Ask:
  • Order of processing (LIFO)?
  • Monotonic requirement?
  • Combine with other structures?

• Why stack over queue?
• Optimize for monotonic stacks.
• Handle edge cases (empty stack, invalid input).
• Combine with other patterns (e.g., sliding window).

• Brute: O(n²) scan for each element.
• Optimize: Stack O(n).
• Dry-run: [2,1,5] next greater → [5,5,-1].
• Analyze: O(n) time, O(n) space.
• Edges: Empty stack, all equal elements.

Divide and Conquer splits problems into smaller subproblems, solves them, and combines results, common in FAANG for recursive algorithms.

• Core Concept: Divide into subproblems, conquer recursively, merge solutions. Often used in sorting, tree, or array problems.
• Applications: Merge sort, quicksort, binary tree processing, matrix multiplication.
• FAANG Focus: Tests recursion design, merge logic, and optimization (e.g., in-place quicksort).

• Cues: "Sort array," "process tree recursively," "divide array into halves."
• Interviewer Hints:
  • "Split into smaller problems?" → Divide and Conquer.
  • "How to merge results?" → Define merge step.
  • "Optimize recursion?" → Tail recursion or iterative.
• Break the Problem: Ask:
  • How to split data?
  • Merge complexity?
  • Recursive depth constraints?

• Define divide and merge steps.
• Prove correctness of recursion.
• Optimize space (e.g., in-place).
• Handle edge cases (single element, unbalanced splits).

• Brute: O(n²) naive solution.
• Optimize: Divide and Conquer O(n log n).
• Dry-run: Merge sort [3,1,4] → [1,3,4].
• Analyze: O(n log n) time, O(n) space.
• Edges: Single element, sorted input, duplicates.

Bit manipulation uses bitwise operations (AND, OR, XOR, shifts) for efficient computation, common in FAANG for low-level optimization.

• Core Concept: Manipulate bits for arithmetic, set operations, or state encoding. XOR is key for finding unique elements, toggling bits.
• Applications: Find missing numbers, count bits, subset generation, or power set.
• FAANG Focus: Tests understanding of bitwise operators, optimization (e.g., O(1) space), and edge cases (e.g., negative numbers).

• Cues: "Find unique number," "count 1s," "generate subsets," "bitwise operations."
• Interviewer Hints:
  • "Use bitwise operations?" → Bit manipulation.
  • "Avoid extra space?" → XOR or bit shifts.
  • "Handle large numbers?" → Consider sign bits.
• Break the Problem: Ask:
  • Signed or unsigned numbers?
  • Single or multiple passes?
  • Bitwise constraints?

• Explain bitwise operations (e.g., XOR properties).
• Optimize space (e.g., O(1) with XOR).
• Handle negative numbers or edge cases.
• Combine with other patterns (e.g., DP).

• Brute: O(n) scan or hash.
• Optimize: Bitwise O(n) or O(1).
• Dry-run: [1,1,2] single number → 2 (XOR).
• Analyze: O(n) time, O(1) space.
• Edges: Negative numbers, zeros, single element.