161 articles
Master reversing nodes in groups of k in a linked list — the classic hard interview problem asked at Amazon, Google, Facebook, and Microsoft. Learn both the elegant recursive solution and the iterative approach with clear pointer diagrams.
Master two optimal approaches to merge k sorted linked lists: min-heap for O(n log k) time and divide-and-conquer for O(n log k) with lower constant factors. A top-tier interview problem at Amazon, Google, Facebook, Microsoft, and Uber that tests your mastery of heaps and recursive merging.
Master bottom-up merge sort on a linked list for O(n log n) time and O(1) space — eliminating the O(log n) recursive stack. A hard interview problem at Amazon, Google, and Facebook that demonstrates deep understanding of merge sort and linked list mechanics.
Learn the optimal O(n) approach to convert a sorted linked list to a height-balanced BST using in-order construction — consuming list nodes sequentially without finding the midpoint each time. A clever interview technique at Amazon, Google, and Microsoft that demonstrates advanced recursion thinking.
Build an LRU Cache from scratch using a doubly linked list with sentinel nodes and a HashMap for O(1) get and put operations. The most frequently asked hard design problem at Amazon, Microsoft, Google, and Facebook — explained step by step with diagrams.
Master Tarjan's SCC algorithm: a single DFS pass with discovery times, low-link values, and an explicit stack to identify all strongly connected components in O(V + E). The interview gold standard for directed graph decomposition, asked at Google, Meta, and Uber.
Use Tarjan's low-link technique to find every bridge (critical edge) and articulation point (cut vertex) in an undirected graph in O(V + E). The interview pattern behind LeetCode 1192 Critical Connections, asked at Google, Meta, and Amazon.
Master advanced Dijkstra: state augmentation, K-stop limits, two-cost optimisation, k-th shortest paths, and modified relaxation. The interview pattern behind LeetCode 787, 1928, and 1976, asked at Google, Amazon, and Meta.
Master LeetCode 1192 Critical Connections in a Network: a textbook Tarjan bridge-finding algorithm using DFS with discovery times and low-link values to detect every edge whose removal disconnects the graph. A FAANG hard graph interview classic at Google, Amazon, and Meta.
Master LeetCode 332 Reconstruct Itinerary using Hierholzer's algorithm: a single DFS that traverses every edge exactly once and assembles an Eulerian path via post-order insertion. A FAANG hard interview classic asked at Google, Meta, and Amazon, and the foundational pattern for de Bruijn sequences and DNA fragment assembly.
Master LeetCode 778 Swim in Rising Water by reducing a grid puzzle to a minimax shortest-path problem. Solve it three ways — Dijkstra with max-relax, binary search plus BFS, and Kruskal-style union-find — and learn when each approach wins. A FAANG hard interview classic at Google, Amazon, and Meta.
A complete walkthrough of network flow for FAANG interviews: the max-flow min-cut theorem, Ford-Fulkerson, Edmonds-Karp BFS-augmenting paths, residual graphs, and practical applications including bipartite matching and project selection. Asked at Google, Amazon, and Meta as a senior-level systems-design-meets-algorithms screen.
LeetCode 135 — asked at Amazon, Google, and Microsoft. Give each child the minimum candies so higher-rated neighbors get more. Two greedy passes: left-to-right for left-neighbor constraint, right-to-left for right-neighbor constraint. O(n) time, O(n) space.
LeetCode 42 — one of the most asked hard problems at Amazon, Google, Microsoft, and Meta. Compute trapped rainwater using two pointers in O(n) time and O(1) space. The key: water at any position is min(left_max, right_max) minus the height. Move the pointer with the smaller max inward.
LeetCode 239 — asked at Amazon, Google, and Microsoft. Find the maximum in each sliding window of size k in O(n) using a monotonic decreasing deque. The deque stores indices in decreasing order of value — pop from front when out of window, pop from back when current element is larger.
LeetCode 41 — asked at Amazon, Google, and Microsoft. Find the smallest missing positive integer in O(n) time and O(1) space. Use the array itself as a hash map: place each number i at index i-1, then scan for the first mismatch. The answer must be in [1, n+1].
LeetCode 84 — asked at Amazon, Google, and Microsoft. Find the largest rectangle in a histogram using a monotonic increasing stack. For each bar, find the nearest shorter bars on both sides to compute the maximum width. O(n) time, O(n) space.
Master LeetCode 76 — the gold-standard Hard sliding window problem asked at Google, Meta, and Amazon. Learn the "formed" counter trick that reduces window validity checks from O(|t|) to O(1), trace through a full dry run, and avoid the five bugs that most often break this one.
Master LeetCode 315 — one of the most common FAANG hard problems. Learn why a naive O(n²) scan fails at scale, how merge sort secretly counts inversions as a side effect, and how to trace through every swap on paper. Includes both brute-force and optimal solutions in Python and JavaScript, a full complexity table, and the three follow-up problems that frequently appear in the next interview round.
LeetCode 4 is one of the most feared Hard problems in FAANG interviews. Learn exactly why the partition insight works, trace through a full binary search dry run, understand the five common bugs that cause silent wrong answers, and walk away with production-quality Python and JavaScript solutions.
Master LeetCode 85 — Maximal Rectangle by building on LC 84 Largest Rectangle in Histogram. Learn the row-as-histogram insight, a visual row-by-row dry run, common pitfalls, and clean Python + JavaScript solutions that interviewers love.
LeetCode 493 trips up even strong candidates because the count step must happen before the merge step — not during it. Learn exactly why that ordering matters, trace through a full dry run on [1,3,2,3,1], understand the five most common bugs, and walk away with clean Python and JavaScript solutions you can reproduce under pressure.
Master LeetCode 410: learn why binary searching on the answer (not the array) is the key insight, walk through a full greedy feasibility check, and see both the DP and binary search solutions with line-by-line commentary.
Negative numbers completely break the classic sliding window for minimum-length subarray problems. Learn exactly why, then master the only correct approach — a monotonic deque on prefix sums — with a step-by-step visual trace, the three mistakes every candidate makes, and every real interview follow-up with approach hints.
Master LeetCode 327 — Count of Range Sum — with deep intuition, a visual dry run, brute-force to O(n log n) merge sort progression, and real interview follow-ups covering BIT, LC 315, and LC 493.
Master LeetCode 689 with a full visual dry run, left/right DP insight, Python and JavaScript solutions, and real interview follow-ups on generalizing to k windows.
Master LC 871 with two complementary strategies: a greedy max-heap that asks "which station gives me the most fuel when I am stuck?" in O(n log n), and a DP table that asks "what is the farthest I can reach with exactly k stops?" in O(n²). Both are asked at Amazon and Google. Learn the intuition, see a full dry run, and understand when each approach fits.
LeetCode 149 asks you to find the maximum number of collinear points on a 2D plane. The trick is representing slope as a GCD-reduced integer fraction — no floats, no precision bugs — and using a HashMap to count how many points share the same slope relative to each anchor. This post covers the full intuition, a step-by-step visual dry run, every edge case (vertical lines, duplicates, sign normalization), well-commented Python and JavaScript solutions, and the real FAANG follow-up questions that separate good candidates from great ones.
LeetCode 32 is one of the most deceptive Hard problems on the platform — the brute-force is obvious, but all three optimal solutions require genuinely different mental models. Master the index-sentinel stack, the DP recurrence, and the two-pass counter sweep, and you will be able to answer any follow-up a FAANG interviewer throws at you.
LC 992 is one of the cleanest examples of a non-obvious reduction in competitive programming. Learn the "exactly K = atMost(K) minus atMost(K-1)" insight, trace through a full visual dry run, and understand how this single pattern unlocks five related hard problems in one shot.
Master LC 936 Stamping the Sequence with reverse greedy simulation. Learn the core insight that working backwards transforms an impossible forward search into a tractable greedy problem. Python and JavaScript solutions with full commentary.
Find the longest substring that appears at least twice using binary search on the answer length combined with a Rabin-Karp rolling hash. A FAANG-level Hard problem solved in O(n log n) average time with full pseudocode in Python and JavaScript.
Design FreqStack to push values and pop the most frequent element with recency tie-breaking in O(1). Master the freq-map plus group-of-stacks pattern with a full visual dry run, common pitfalls, and Python and JavaScript solutions.
LC 410 asks you to split an array into k non-empty subarrays to minimize the largest subarray sum. Binary search on the answer range [max(nums), sum(nums)] and greedily count splits to check feasibility. O(n log(sum - max)) total time.
LC 154 extends the rotated minimum search to arrays with duplicates. When nums[mid] == nums[hi], neither half can be ruled out — safely shrink by decrementing hi. Worst case degrades to O(n). A hard variant that tests invariant reasoning.
LeetCode 4 is the most famous FAANG hard problem. Solve the median of two sorted arrays in O(log(min(m,n))) by binary searching for the correct partition position.
LeetCode 315 is a Google and Amazon classic. Count how many elements to the right are smaller than each element using merge sort with index tracking or a Fenwick Tree, both running in O(n log n).
LeetCode 354 reduces a 2D nesting problem to 1D Longest Increasing Subsequence with patience sorting, giving an O(n log n) FAANG-friendly solution.
LeetCode 1891 finds the maximum ribbon length such that we can cut at least k pieces. A clean O(n log max) binary-search-on-answer template every interviewer expects.
Place C cows in N stalls to maximise the minimum distance between any two cows. Learn the canonical binary-search-on-answer pattern — the template behind Magnetic Force Between Two Balls, Split Array, and dozens of other hard problems.
Count subarrays whose sum lies in [lower, upper] using merge sort on prefix sums in O(n log n). Understand the divide-and-conquer counting trick that makes an O(n^2) brute-force drop to linearithmic time.
LC 786 asks for the kth smallest fraction a[i]/a[j] from a sorted prime array. Binary search on the fraction value [0.0, 1.0] and count fractions below mid using two pointers. O(n log(1/epsilon)) total. A hard binary search on value problem.
Find the kth smallest element from two sorted arrays in O(log(m+n)) without merging. Binary elimination: compare the k/2-th element of each array; the smaller one cannot contain the kth element, so eliminate k/2 candidates. Builds directly to LC 4 (Median of Two Sorted Arrays).
LeetCode 1879 Minimum XOR Sum of Two Arrays — pair every element of nums1 with a unique element of nums2 to minimize total XOR. Bitmask DP turns assignment into a 2^n state space. Step-by-step bit manipulation walkthrough for FAANG interviews.
LeetCode 1178 Number of Valid Words for Each Puzzle — count words containing the puzzle’s first letter using only puzzle letters. The 26-bit bitmask plus the (sub - 1) AND parent submask trick crushes a brute-force quadratic solution.
LeetCode 269 Alien Dictionary is a Google premium classic that derives a character ordering from a sorted word list. We model it as a directed graph and run Kahn topological sort BFS to detect cycles and emit a valid order in O(C) time.
LeetCode 239 Sliding Window Maximum is a Google classic that returns the max of every length-k window. The optimal answer maintains a monotonic decreasing deque of indices for amortised O(n) time.
LeetCode 76 Minimum Window Substring is a Google staple solved with a two-pointer sliding window plus a need-and-have frequency counter. Optimal solution runs in O(n + m) time and O(m) space.
Encode a binary tree to a string and reconstruct it. Meta ranks this as their number-one tree interview question, testing BFS level-order traversal and string parsing under pressure.
Implement a read() function using a read4() primitive that reads exactly 4 characters at a time. Meta uses this to test buffer management, pointer arithmetic, and state machine design for file I/O.
Count the number of islands after each addLand operation using incremental Union-Find with path compression. Amazon tests this to evaluate dynamic graph connectivity and disjoint set data structures.
Merge k sorted linked lists into one sorted list using a min-heap for O(N log k) efficiency. Amazon uses this to test heap-based k-way merge, a critical pattern in distributed data systems.
Count the number of inversions in an array using a modified merge sort that counts cross-inversions during the merge step. Google tests this to evaluate divide-and-conquer mastery and algorithmic optimization under O(N log N) constraints.
Return all possible sentence segmentations of a string using valid dictionary words via DP memoization and backtracking. Google tests this to evaluate recursive search pruning and memoization applied to NLP-style segmentation.
Compute trapped rain water in a 3D height map using a min-heap BFS that processes cells from the boundary inward. Google asks this as a hard follow-up to 1D trapping rain water, testing 3D spatial reasoning and heap-driven BFS.
Find the median of two sorted arrays in O(log(min(m,n))) using binary search on partition points. Amazon and Google use this hard problem to test binary search on abstract criteria and numerical reasoning under pressure.
LeetCode 354 Russian Doll Envelopes is a sneaky 2D Longest Increasing Subsequence problem. Sort by width ascending and height descending so equal widths cannot stack, then run patience-sort LIS on heights for an O(n log n) DP solution beloved by FAANG interviewers.
The complete 2D Dynamic Programming roadmap for FAANG interviews — LCS, Edit Distance, grid path counting, interval DP, stock state machines, and 2D knapsack with Python and JavaScript templates.
LC 72 Edit Distance (Levenshtein Distance) is the hard-level sequence DP benchmark at Google, Amazon, and Meta. Master the 3-operation recurrence, space-optimize to O(n), and understand how this algorithm powers spell-checkers, DNA alignment, and autocomplete systems.
LC 1092 Shortest Common Supersequence combines LCS computation with DP table reconstruction to produce the actual shortest string containing both inputs as subsequences. A hard-level 2D DP problem asked at Google and Amazon that demands both algorithm depth and reconstruction skill.
LC 312 Burst Balloons is the classic hard-level interval DP problem asked at Google, Amazon, and Meta. The key insight is thinking in reverse — instead of choosing which balloon to burst first, choose which one to burst last in each interval. This transforms an impossible ordering problem into clean O(n^3) DP.
LC 123 Best Time to Buy and Sell Stock III limits transactions to at most 2. The state machine tracks 4 explicit states — buy1, sell1, buy2, sell2 — evolving each day through clean transitions. This is the hardest single-interview stock variant and the direct precursor to the k-transactions generalization in LC 188.
LC 188 Best Time to Buy and Sell Stock IV generalizes the stock problem to at most k transactions using a 2D DP table where dp[t][i] tracks the maximum profit using t transactions through day i. This is the hardest stock variant in FAANG interviews and requires combining the k-transaction state machine with the unlimited-transaction shortcut for large k.
LC 10 Regular Expression Matching implements "." (any char) and "*" (zero or more of preceding) using 2D DP. It is a Hard-level problem and the most complex string DP asked at Google and Meta — the star (*) handling requires 3 separate cases that trip up even experienced candidates.
LeetCode 44 Wildcard Matching is the classic 2D string DP question Meta and Google ask to test recurrence design under tricky base cases. We derive the dp[i][j] transitions for ? and *, dry-run a full table, and finish with a two-pointer optimization that drops memory to O(1).
LeetCode 174 Dungeon Game is the textbook example of why DP direction matters. We derive why forward DP fails, build the backward dp[i][j] = max(1, ...) recurrence, dry-run the grid, and finish with a space-optimized 1D solution loved at FAANG.
LeetCode 664 Strange Printer is the canonical O(n^3) interval DP every senior FAANG interviewer expects you to handle. We derive the dp[i][j] recurrence, walk through the merge-on-match optimization, dry-run a full table, and discuss where Strange Printer sits in the Burst Balloons / MCM family.
The full 2D Dynamic Programming cheatsheet for FAANG interviews — seven pattern transitions, stock state machine, interval DP template, LCS reconstruction, and the complete problem index.
Flip at most one 0 to 1 to maximize island area. The "color the islands, then try every flip" trick avoids quadratic re-DFS — a top Google interview problem.
Find the minimum number of 0s to flip to connect two islands. Use DFS to color the first island, then multi-source BFS to expand outward until hitting the second island.
Process land additions one at a time and report the island count after each. Union-Find makes each query nearly O(1) amortized — the canonical online connectivity interview problem.
LC 127 Word Ladder asks for the shortest sequence of one-letter transformations from beginWord to endWord, where every intermediate word must be in the dictionary. BFS on the implicit word-state graph finds the minimum in O(M^2 * N) using wildcard pattern grouping.
LeetCode 126 Word Ladder II asks for every shortest transformation path between two words. Master the layered BFS plus parent-map DFS pattern that survives the brutal time limits at Amazon, Google, and Facebook interviews.
LeetCode 815 Bus Routes is deceptively hard. The trick is that BFS levels count buses, not stops, so the graph you traverse is a route graph. Master the stop-to-routes inversion that beats the time limit at FAANG interviews.
LeetCode 882 Reachable Nodes in Subdivided Graph blends Dijkstra with an edge-budget counting trick. Master the optimal pattern that interviewers at Google and Amazon use to filter senior candidates.
LeetCode 135 Candy is an Amazon, Google, and Apple Hard that turns into a 10-line problem when you spot the two-pass greedy. Sweep left then right and take the max to satisfy both rating constraints.
LC 84 Largest Rectangle in Histogram is the canonical hard monotonic stack problem. The key insight — use an increasing stack and compute maximum rectangle area when a shorter bar causes a pop — unlocks both this problem and Maximal Rectangle.
LC 42 Trapping Rain Water is one of the most famous hard problems in FAANG interviews. The optimal two-pointer approach uses O(1) space. Knowing all three approaches and their trade-offs separates senior candidates from junior ones.
LC 85 Maximal Rectangle is a hard problem that reduces to running Largest Rectangle in Histogram on each row. Build cumulative height histograms row by row and apply the O(n) monotonic stack solution — the reduction is the key insight.
LC 460 LFU Cache implements O(1) get and put using three hash maps and ordered per-frequency buckets — one of the most complex design problems in FAANG interview prep, seen at Google and Amazon for senior roles.
LC 432 All O'one Data Structure supports inc, dec, getMaxKey, and getMinKey all in O(1) using a doubly linked list of frequency buckets — one of the most elegant O(1) designs in FAANG interview prep.
Find all index pairs (i, j) such that words[i] + words[j] forms a palindrome, using a reverse-word hashmap and systematic prefix/suffix palindrome splits in O(N * K^2) time. A FAANG hard problem that fuses string algorithms with hash table mastery.
LeetCode 295 (Hard) — a FAANG favorite. Maintain a dynamic median from a live data stream using two heaps: a max-heap for the lower half and a min-heap for the upper half, achieving O(log n) per insert.
LeetCode 480 (Hard) — a Google and Bloomberg favorite. Compute the median of every k-sized window using two heaps with a lazy deletion hash map.
LeetCode 23 (Hard) — the most-asked heap problem at FAANG. Merge k sorted linked lists in O(N log k) using a min-heap that always tracks the smallest active head.
LeetCode 630 (Hard) — a Google scheduling classic. Maximize courses you can finish before deadlines using a greedy max-heap that swaps out the longest course when budget overflows.
Maximize capital after k IPO investments by unlocking affordable projects into a max-profit heap — a sophisticated two-heap greedy problem asked at Google, Amazon, and Facebook that models real-world portfolio optimization.
LeetCode 407 Trapping Rain Water II is a Google and Meta hard interview problem. Solve it with min-heap BFS that processes the elevation map inward from the border in O(mn log(mn)).
LeetCode 778 Swim in Rising Water is a Google and Amazon hard problem disguised as Dijkstra. Solve it with a min-heap that minimizes the maximum elevation along any path in O(N^2 log N).
LeetCode 632 Smallest Range Covering Elements from K Lists is a Google and Meta hard interview problem. Solve it with a K-way merge min-heap that maintains a sliding range across K sorted lists in O(N log K).
LeetCode 871 Minimum Number of Refueling Stops is an Amazon and Google hard interview problem. Use a max-heap to greedily pick the richest station retroactively in O(N log N).
LeetCode 1383 Maximum Performance of a Team is a Google and Amazon hard interview classic. Use a sorted sweep over efficiency with a size-k min-heap of speeds to compute the answer in O(N log N).
LeetCode 895 Maximum Frequency Stack is an Amazon, Google, and Meta hard design interview problem. Achieve O(1) push and pop using frequency-bucket stacks — beating the naive max-heap approach.
LeetCode 1675 Minimize Deviation in Array is a Google and Amazon hard interview problem. Reduce it to a one-directional max-heap by doubling odds upfront, then halve the max iteratively in O(N log N log M).
Compute the median for each sliding window using two heaps with lazy deletion — the definitive template for dynamic order statistics in interview problems.
Answer range-coverage queries offline by sorting both intervals and queries, sweeping through with a min-heap ordered by interval size — a canonical offline query pattern.
Matrix exponentiation collapses any linear recurrence into O(log n) by raising a transition matrix to the n-th power. Master Fibonacci, k-th order recurrences, and DP optimization tricks that let you answer queries with n up to 10^18 in milliseconds.
LC 51 N-Queens is the gold standard for testing backtracking, constraint propagation, and bit-mask elegance. Master row-by-row placement, three diagonal-tracking sets, and the bitmask trick that runs N=15 in milliseconds.
LC 37 Sudoku Solver is the most-asked constraint-satisfaction problem in tech interviews. Master row, column, and box bitsets, MRV heuristic ordering, and the cell-by-cell decision tree that solves any 9x9 grid in milliseconds.
LC 79 Word Search and LC 212 Word Search II ship in nearly every FAANG onsite. Master DFS with in-place visited marking, four-directional exploration, and the trie trick that turns multi-word search into a single traversal.
LeetCode 282 Expression Add Operators with full backtracking decision tree, multiplication precedence trick, leading-zero pruning, and FAANG interview prep.
Solve the Knight's Tour with backtracking and Warnsdorff's heuristic. Visit every square exactly once on an n by n board with O(8^(n^2)) brute force tamed by smart move ordering.
LeetCode 301 Remove Invalid Parentheses with BFS for minimum removals and DFS backtracking with precomputed quotas. FAANG hard-tier interview prep.
Count smaller elements to the right of every index using a Binary Indexed Tree (Fenwick Tree) with coordinate compression. The cleanest O(n log n) solution every interviewer expects.
Count pairs (i, j) with i less than j and nums[i] greater than twice nums[j]. The classic Hard problem for modified merge sort and BIT counting — the two techniques every senior interviewer expects.
Track range coverage with addRange, removeRange, and queryRange. Maintain disjoint intervals in a sorted map for amortized O(log n) — the canonical interview problem for interval merging logic.
Track the tallest stack height as squares fall onto a number line. The textbook problem for segment trees with lazy propagation, range max queries, and range-assign updates.
Count subarray sums in [lower, upper] using merge sort or Fenwick tree on prefix sums. The flagship Hard problem connecting prefix sums, divide-and-conquer counting, and BIT range queries.
Solve LeetCode 732 My Calendar III using a sweep-line difference array in O(n) per booking, then upgrade to a dynamic lazy segment tree with coordinate compression for O(log n) range updates and max queries.
Crack LeetCode 363 Max Sum of Rectangle No Larger Than K by fixing two row boundaries to collapse 2D into 1D, then using prefix sums plus a sorted set (or BIT/segment tree) to find the best subarray sum bounded above by K.
Find the maximum in every sliding window of size k using a monotonic decreasing deque that maintains candidate indices in O(n) total time. The hardest and most elegant deque problem — mastering this unlocks Shortest Subarray with Sum At Least K and Jump Game VI.
Solve LeetCode 127 Word Ladder using BFS with a queue and a wildcard pattern map for O(1) neighbor lookups. A FAANG hard at Amazon, Google, Meta, and Microsoft that tests BFS on implicit graphs.
Solve LeetCode 1944 Number of Visible People in a Queue in O(n) using a monotonic decreasing stack. A FAANG hard interview problem at Amazon, Google, and Meta that uses LIFO stack semantics for visibility queries.
Solve LeetCode 862 Shortest Subarray with Sum At Least K in O(n) using a monotonic increasing deque on prefix sums. A FAANG hard interview classic.
Solve LeetCode 84 Largest Rectangle in Histogram in O(n) using a monotonic increasing stack. The single most important monotonic stack interview problem at FAANG.
Solve LeetCode 85 Maximal Rectangle in O(m times n) by reducing each row to a histogram and applying the monotonic stack. A FAANG hard interview classic.
Solve LeetCode 224 Basic Calculator with a single-pass stack approach handling +, -, parentheses, and arbitrary whitespace in O(n). A FAANG hard parsing classic.
Solve LeetCode 895 Maximum Frequency Stack with a layered "stack of stacks" data structure giving O(1) push and pop. A FAANG hard design favorite.
Solve LeetCode 295 Find Median from Data Stream with two heaps (max-heap for low half, min-heap for high half) giving O(log n) addNum and O(1) findMedian. A FAANG streaming classic.
Solve LeetCode 297 Serialize and Deserialize Binary Tree with a BFS queue producing a level-order encoding parsed in O(n). A FAANG hard tree design favorite.
Solve LeetCode 42 Trapping Rain Water in O(n) using a monotonic decreasing stack to fill water layer by layer. The signature FAANG monotonic stack hard problem.
Manacher finds the longest palindromic substring in O(n) by exploiting palindrome symmetry to skip redundant character comparisons. The same mirror trick that powers the Z algorithm, applied to the palindrome radius array.
A suffix array sorts all suffixes of a string lexicographically. Built in O(n log n) with prefix doubling and paired with the Kasai LCP array, it answers substring search, distinct substring count, and longest repeated substring queries in optimal time.
Longest Palindromic Substring, Palindrome Partitioning, and Palindromic Substrings form a tight family of FAANG questions. Master expand-around-center, 2D DP, and the link to Manacher and you can adapt to any variant on the spot.
Word Search II (LC 212) is the canonical FAANG hard combining trie data structures with grid backtracking. Build a trie from the dictionary, DFS each cell, and prune aggressively to convert an exponential brute force into a fast practical algorithm.
Shortest Palindrome (LC 214) is a hard FAANG problem that hides a classic KMP application. Concatenate s with reversed(s) and the failure function reveals the longest palindromic prefix in linear time. Master this trick and you unlock half a dozen related KMP applications.
Counting distinct substrings of a string is the gateway problem to suffix arrays and suffix automata. Three classical solutions — n^2 hash set, suffix array plus LCP, and suffix automaton — span the full toolbox of competitive programming and FAANG hard interviews.
Beyond the basic trie there is a rich landscape of advanced applications — XOR tries for maximum-XOR queries, prefix-and-suffix tries, ternary tries, compressed tries (PATRICIA), and persistent tries. Master these and you have the toolkit for half a dozen FAANG hards.
A curated and battle-tested set of the string problems that show up most often in Meta and Google onsite loops, with the canonical pattern for each. Cover this list and you cover roughly 80 percent of string-heavy FAANG screens.
Aho-Corasick matches all patterns simultaneously in O(n+m+z) where z is the number of matches. It builds failure links on a trie exactly like KMP does on a single pattern. Master multi-pattern search for FAANG string algorithm interviews.
LeetCode 460 LFU Cache asked at Google and Apple for staff-level roles. Achieve O(1) get and put using frequency buckets with doubly linked lists.
Design a search autocomplete that returns top 3 historical queries for the current prefix, ranked by frequency. Combines a Trie with per-node frequency maps, a pattern used in Google Search and Bing.
Implement a skip list from scratch with O(log n) expected search, add, and erase. The probabilistic sorted linked list used in Redis sorted sets and LevelDB—a must-know data structure for senior FAANG interviews.
Design an in-memory key-value database with field-level get, set, delete, and sorted scan operations. Uses nested hashmaps and sorted structures—the foundation of Redis hashes and LeetCode contest scoring.
Maintain a running median from a data stream using two heaps: a max-heap for the lower half and a min-heap for the upper half. A classic FAANG hard problem used in analytics engines and streaming data pipelines.
Solve LeetCode 987 Vertical Order Traversal using DFS coordinates plus tie-breaking sort. A Hard FAANG question asked at Meta, Amazon, and Google.
LC 968 Binary Tree Cameras asks for the minimum number of cameras to monitor all nodes. The O(n) greedy solution assigns three states per node in a bottom-up DFS — delay camera placement as high as possible, a pattern tested at Amazon and Google.
LC 124 Binary Tree Maximum Path Sum finds the highest-value path in a binary tree where the path can start and end at any node. The O(n) solution uses a post-order DFS that tracks the global max while returning only one branch to the parent — a critical FAANG interview problem at Amazon, Google, and Facebook.
LC 297 Serialize and Deserialize Binary Tree is a top FAANG hard problem asked at Facebook, Amazon, and Google. The DFS preorder approach with null markers gives a compact O(n) codec; BFS level-order is more intuitive. Both are valid interview answers.
LC 1373 Maximum Sum BST in Binary Tree finds the highest sum among all BST subtrees of a binary tree. The O(n) solution uses post-order DFS returning a 4-tuple of (is_bst, min, max, sum) metadata — a hard FAANG problem tested at Amazon and Google.
LeetCode 834 Sum of Distances in Tree is a Google and Meta favorite hard problem solved in O(n) using two-pass DFS with the rerooting technique on an undirected tree.
LeetCode 272 (Hard) frequently asked at Google and Meta. Use BST inorder traversal to get a sorted list, then a two-pointer shrink window selects the k closest values to a target in O(n) time.
LeetCode 212 — find every dictionary word hidden in a board. The optimal solution builds a trie over the words and DFS-traverses the grid once, pruning entire branches the moment the path leaves the trie. A textbook FAANG hard problem.
LeetCode 336 — find every pair (i,j) such that words[i] + words[j] is a palindrome. The trie solution stores reversed words and tags palindrome-suffix indices, enabling O((N times K^2)) lookup.
LeetCode 1032 — design a class that returns true whenever the suffix of a streamed character sequence matches any dictionary word. Solved with a reverse trie and a bounded sliding buffer in O(W) per query.
LeetCode 745 — design a structure that returns the highest-indexed word matching a given prefix and suffix. The combined-key trie inserts every (suffix#word) variant, turning a 2D query into a 1D trie walk.
LeetCode 2416 — for each word, sum the scores of all its non-empty prefixes where score = number of words sharing that prefix. The counted trie pattern aggregates O(N times L) work into O(N times L) trie nodes with a count counter.
LeetCode 472 — find every word that can be formed by concatenating two or more shorter words from the same list. Trie accelerates the prefix-membership test inside a Word Break DP, turning O(2^L) brute force into O(N times L^2).
LeetCode 1707 — for each query (xi, mi), find max xi XOR nums[j] where nums[j] does not exceed mi. Sort queries by mi, sort nums, insert lazily into a binary trie, answer each query in O(32). The offline-trie pattern unlocks bounded XOR queries.
LeetCode 992 Subarrays with K Different Integers is a Google, Amazon, and Meta hard. Solve in O(n) using the atMost(K) minus atMost(K-1) decomposition.
LeetCode 2444 asked at Google and Amazon. Track last-bad, last-minK, and last-maxK indices to count valid subarrays in a single O(n) pass.
LeetCode 727 asked at Google and Amazon. A forward scan finds a valid right boundary, then a backward scan tightens the left boundary in O(|s|*|t|) time.
LeetCode 2488 asked at Google and Amazon. Map elements to +1/-1 relative to k and count prefix balances of 0 or 1 around k in O(n) time.
LeetCode 480 asked at Google, Amazon, and Bloomberg. Maintain a max-heap and a min-heap with lazy deletion to compute the median in O(n log k) time.
LeetCode 30 asked at Google, Amazon, and Meta. Run a word-aligned sliding window for each of the wlen possible offsets to find every concatenation start in O(n*wlen) time.
Count subarrays where score = sum × length is less than k using a shrinkable sliding window with a running sum. Counting all valid subarrays ending at each right pointer is the key trick that avoids an inner loop.
Find the smallest window in s containing all characters of t using have/need counters and a frequency map. The canonical hard sliding-window problem asked at every top tech company.
Find the maximum in every sliding window of size k in O(n) using a monotonic decreasing deque of indices — the classic hard problem that separates senior engineers from the rest.
Find the shortest subarray whose sum is at least k, even with negative numbers, using a monotone increasing deque on prefix sums — the canonical hard problem where a simple sliding window fails.
Find the longest substring containing at most 2 distinct characters using a variable sliding window backed by a character frequency map — a premium LinkedIn and Google problem with a clean generalization to k distinct.
Solve LeetCode 42 Trapping Rain Water in O(n) time and O(1) space using the canonical two-pointer technique. Includes intuition, dry run, Python and JavaScript code, and follow-up variants.