25 articles
Strategic playbook for FAANG-specific DSA preparation. Covers Google graph and DP focus, Meta tree and string emphasis, and Amazon Leadership Principles alignment with BFS, heap and design problems.
LeetCode 240 Search a 2D Matrix II is a Google favourite that tests staircase elimination. We solve it in O(m + n) by walking from the top-right corner — beating the naive O(m * n) scan and the O(m * log n) per-row binary search.
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.
Implement a lazy iterator over a nested integer list using a stack. Meta frequently tests this to evaluate iterator design, lazy evaluation, and stack-based tree traversal.
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.
Design a class to find the kth largest element in a stream using a min-heap of size k. Amazon tests this to evaluate heap design, streaming data patterns, and online algorithm thinking.
Find the minimum CPU intervals to finish all tasks with a cooldown constraint. Amazon tests this greedy heap problem to evaluate CPU scheduling knowledge and frequency-based optimization.
Find the longest substring containing at most k distinct characters using a sliding window with a frequency map. Google asks this to test sliding window mastery and hashmap-based window shrinking.
Generate all valid combinations of n pairs of parentheses using backtracking with open and close counters. Meta asks this to test recursive thinking, pruning, and combinatorial generation under time pressure.
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.
Count contiguous subarrays whose elements sum to k using prefix sums and a frequency hashmap. Meta asks this to test prefix sum mastery and O(N) optimization over brute-force O(N^2) solutions.
Find the k most frequent elements in an array using a min-heap or bucket sort. Amazon asks this to test frequency counting, heap manipulation, and O(N) bucket sort optimization for bounded frequency ranges.
Return the rightmost visible node at each level of a binary tree using BFS level order traversal. Meta uses this to test BFS confidence, level tracking, and tree traversal variants applied to visual rendering problems.
Master Two Sum and its variants — 3Sum, 4Sum, Two Sum II — using hashmap for O(N) and two pointers for sorted arrays. Amazon relies on this problem family to assess foundational array skills and generalization ability.
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.
Merge accounts that share any email address using Union-Find on email nodes. Meta uses this to test graph connectivity thinking and identity resolution — directly applicable to Facebook account deduplication systems.
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.
Deep copy an undirected graph using DFS or BFS with a HashMap to track already-cloned nodes. Meta tests this to evaluate graph traversal, deep copy semantics, and cycle detection in recursive graph structures.
A complete cheatsheet of FAANG company-specific DSA problems, patterns, and optimal approaches. Use this as your final review before any Meta, Amazon, or Google coding interview.