Company Problems — Master Recap and FAANG Interview Cheatsheet

Problem Statement#

This is a master reference covering all FAANG company-specific DSA problems from this series, organized by company and pattern for fast interview review.

Coverage:

• Meta top problems: iterator design, graph cloning, tree views, backtracking, prefix sums
• Amazon top problems: heap design, Union-Find, merge sort, scheduling, binary search
• Google top problems: sliding window, divide and conquer, 3D BFS, word DP

Why This Problem Matters#

Company-specific patterns are real. Meta, Amazon, and Google each have signature problem families they return to repeatedly. Knowing which patterns each company favors — and which data structures they test — dramatically improves your interview performance. This recap consolidates every problem in the series into a single reference.

The patterns cluster by company: Meta favors iterator design, tree traversal, and graph problems that test clean code under ambiguity. Amazon leans toward heap manipulation, Union-Find, and scheduling problems that model their warehouse and cloud systems. Google prefers sliding window, divide-and-conquer, and hard binary search problems that require mathematical reasoning.

Use this cheatsheet for the last 48 hours before your interview. Every row is a standalone fact you can use to quickly identify the right approach during your interview.

The Core Insight#

Every FAANG interview problem maps to one of 12 core patterns. Once you identify the pattern, the solution approach follows directly. The table below maps each problem to its pattern, company, and the key decision to make.

Visual Dry Run#

Decision tree for company-specific problems:

Solution (Optimal)#

Meta problem patterns and their key insights:

# Meta pattern cheatsheet
 
# Flatten Nested List Iterator — Stack + lazy eval
# Push reversed; hasNext() flattens top until integer found
 
# Serialize/Deserialize Tree — DFS preorder + null markers
# Null marks subtree end; use iterator for clean deserialize
 
# Read N Characters (read4) — Buffer state machine
# Store buf4_idx and buf4_count between calls for Version 2
 
# Generate Parentheses — Backtracking
# Prune: add '(' if open < n, add ')' if close < open
 
# Subarray Sum Equals K — Prefix sum + hashmap
# freq[prefix-k] gives count of valid subarrays ending here
 
# Accounts Merge — Union-Find on emails
# Union all emails in same account; group by root
 
# Clone Graph — DFS + visited hashmap
# Insert clone BEFORE recursing; breaks cycles

// Amazon pattern cheatsheet
 
// Number of Islands II: +1 for new land, -1 per merge
// Kth Largest Stream: min-heap size k; heap[0] is answer
// Task Scheduler: max(total_tasks, (max_freq-1)*(n+1)+count_max)
// Merge K Sorted: min-heap; push node.next after popping node
// Top K Frequent: bucket[freq].append(num); scan from len(nums) down
// Two Sum: seen map; complement = target - current
// Median Two Sorted: binary search partition on smaller array
 
// Google pattern cheatsheet
// Longest Substring K Distinct: sliding window + freq map delete when count=0
// Count Inversions: merge sort; cross-inversions = len(left)-i when right[j] < left[i]
// Word Break II: dp(start) with @lru_cache; base case dp(len(s)) = [""]
// Trapping Rain Water II: min-heap BFS; water += max(0, wall-h); push max(wall,h)

Time: Varies by problem — see individual posts for analysis Space: Varies by problem — see individual posts for analysis

Common Mistakes#

• Applying sliding window to arrays with negative numbers (use prefix sum + hashmap instead)
• Using naive BFS/DFS instead of Union-Find for dynamic connectivity (Number of Islands II)
• Forgetting the +1 in Task Scheduler formula: cycle length is n+1, not n
• Not pre-initializing freq[0] = 1 in Subarray Sum Equals K
• Using node value instead of node reference as hashmap key in Clone Graph
• Not skipping duplicates in 3Sum — produces duplicate results
• In Word Break II, not returning [""] as base case — breaks sentence construction

Interview Tips#

• Open every problem by identifying the pattern before writing code
• For Meta: expect clean OOP, iterator protocols, and DFS/BFS on trees and graphs
• For Amazon: expect heap problems, Union-Find for connectivity, and O(N log k) solutions
• For Google: expect mathematical insight, sliding window, and rigorous complexity analysis
• Practice the one-sentence solution statement: "I will use X because Y" before coding
• Always verify edge cases: empty input, k=0, single element, all duplicates

Follow-up Questions#

• What if the data is a stream? — Heap and Union-Find solutions handle streaming naturally
• What if memory is limited? — Two-pointer or in-place algorithms; external sort for merge problems
• What design handles 1 billion records? — Distributed MapReduce, sharded Union-Find, approximate counting
• Can you parallelize? — CAS-based Union-Find, parallel merge sort, lock-free heaps
• How do you test graph problems? — Generate random DAGs; verify output equals BFS/DFS reference

Key Takeaways#

• Meta favors iterator design, graph cloning, tree traversal, and prefix sum — focus on recursive code clarity
• Amazon favors heap manipulation, Union-Find dynamic connectivity, and scheduling math — focus on O(N log k)
• Google favors sliding window, divide-and-conquer, hard binary search, and NLP-style DP — focus on mathematical insight
• Every company problem maps to one of 12 patterns: hashmap, heap, Union-Find, sliding window, backtracking, BFS, DFS, merge sort, binary search, DP, prefix sum, or monotonic stack
• The 60-second pattern identification step before coding separates strong candidates from weak ones
• Union-Find with path compression handles all "dynamic connectivity after each addition" problems
• Memoized backtracking (DFS + cache) is the universal solution for "enumerate all valid paths or sentences" problems