Phase 1
Programming & DSA
One problem list. Learn with related drills, refresh if it was not cold, or recall cores only.
New to DSA. Solve the core and both related problems.
Phase 1
Programming & DSA
One problem list. Learn with related drills, refresh if it was not cold, or recall cores only. · 8–12 weeks
Time & Space Complexity
Big-O, best/average/worst case. You must explain complexity of every solution.
Big-O describes how time or extra memory grow as the input size n grows — the dominant term, ignoring constants. Best/average/worst case are different functions of the same algorithm (quicksort’s worst is O(n²)). Interviewers expect you to state time and space after every solution, including extra arrays and recursion depth. O(1) extra space still uses the input; “in-place” means you did not allocate another O(n) structure.
More reading
When to use which structure
Array vs linked list vs hash map vs stack vs queue — pick by the operation.
Pick the structure by the operation you need. Array: index and scan. Linked list: O(1) insert/delete if you have the node, no index. Hash map: average O(1) get/put by key. Stack: LIFO (matching, undo, DFS). Queue: FIFO (BFS, scheduling). If you cannot say why you chose a map over a list, you will brute-force.
More reading
Recursion
Call stack, base case, tree recursion. Foundation for backtracking, trees, DP.
Recursion is a function calling itself on a smaller instance until a base case returns. Each call pushes a stack frame — depth is extra space, and too deep overflows. Tree recursion (Fibonacci-style) can be exponential until you memoize; that is the door to DP. Always state the base case and what one call assumes about smaller calls.
Sorting
Know merge sort and quick sort well enough to code and explain.
Sorting orders elements so later binary search, two pointers, and sweep-line work. Merge sort is stable, O(n log n) worst case, O(n) extra space. Quicksort is in-place on average O(n log n) but O(n²) worst case without care. You rarely implement sort in interviews — you call it — but you must know the complexities and when the problem is “sort then scan.”
Two Sum
The default hashmap warmup. Asked everywhere.
Takeaway
Store value → index while you scan. For each x, look up target − x in the map — that is O(n) instead of a nested loop. The map is “what have I already seen.” Do not sort unless the follow-up forbids extra space (then two pointers on a copy, but you lose original indices).
Related — check that you got it
0/2
- Contains DuplicateAmazonGoogleMicrosoftMetaAppleBloombergOracleNVIDIA
Same map/set idea: have I seen this value already?
- Majority ElementAmazonGoogleMicrosoftMetaBloombergAdobeGoldman SachsOracle
Still a frequency pass — Boyer–Moore if you drop the map.
Valid Anagram
Character counts. If this is slow, hashing will feel hard.
Takeaway
Two strings are anagrams if they have the same character frequencies. Count 26 letters (or a map) in O(n). Sorting both is O(n log n) and is a weaker answer. Unicode/case are follow-ups, not the interview.
Related — check that you got it
0/2
- Ransom NoteAmazonGoogleMicrosoftMetaAppleBloombergTCSCriteo
Can magazine counts cover note counts? Same frequency array.
- Isomorphic StringsAmazonGoogleMicrosoftMetaBloombergGoldman SachsOracleLinkedIn
Bijection between characters — two maps, not one count.
Group Anagrams
The key is the signature, not nested compares.
Takeaway
Bucket words by a signature: sorted characters, or a 26-count tuple. Then each bucket is an anagram group. O(n · k log k) if you sort each word, or O(n · k) with counts. Do not compare every pair.
Related — check that you got it
0/2
- Sort Characters By FrequencyAmazonGoogleMicrosoftMetaBloombergSalesforceFlipkartAccenture
Frequency map, then order — same counting muscle.
- Find All Anagrams in a StringAmazonGoogleMicrosoftMetaAppleUberBloombergTikTok
Anagram check on a sliding window, not on a list of words.
Top K Frequent Elements
Count, then pick k — heap or bucket sort.
Takeaway
Count frequencies, then take the k largest. A size-k heap is O(n log k). Bucket sort by frequency is O(n) and is the flex answer. Do not full-sort n entries if k is small.
Related — check that you got it
0/2
- Top K Frequent WordsAmazonGoogleMicrosoftMetaAppleUberBloombergAdobe
Same heap, plus tie-break on lexicographic order.
- Sort Array by Increasing FrequencyAmazonGoogleMicrosoftMetaBloombergAdobeOracleAccenture
Frequency map driving a custom sort.
Prefix/suffix products. No division.
Takeaway
answer[i] is product of everything except nums[i]. Build prefix products left-to-right, then multiply a running suffix from the right. O(n) time, O(1) extra if you write into the output. Division fails on zeros and is usually banned.
Related — check that you got it
0/2
- Running Sum of 1d ArrayAmazonGoogleMicrosoftMetaBloombergTCS
Prefix sums — the easier sibling of prefix products.
- Find Pivot IndexAmazonGoogleMicrosoftMetaAppleBloombergGoldman SachsSalesforce
Left sum equals right sum; prefix makes it O(n).
O(n) with a set, not sort.
Takeaway
Put numbers in a set. Only start a streak from n if n−1 is missing, then walk n, n+1, … The inner walk amortizes to O(n). Sorting is O(n log n) and is the fallback, not the intended answer.
Related — check that you got it
0/2
- Missing NumberAmazonGoogleMicrosoftMetaAppleBloombergAdobeGoldman Sachs
Find the hole in 0..n — xor or sum, still O(n) extra-space optional.
- Longest Continuous Increasing SubsequenceAmazonGoogleMetaBloombergYandex
Consecutive in index, not in value — a linear scan.
Valid Sudoku
Row, column, box sets. Do not solve the puzzle.
Takeaway
Check each filled cell against its row, column, and 3×3 box. Nine sets (or a encoded key in one set) is enough. You are validating, not backtracking a solution. Box index is (r/3)*3 + c/3.
Related — check that you got it
0/2
- Check if Every Row and Column Contains All NumbersZohoInstacartKaratIndeed
Same row/col set check, no boxes.
- Set Matrix ZeroesAmazonGoogleMicrosoftMetaAppleUberBloombergGoldman Sachs
Mark rows/cols from cells you have seen — still a matrix pass.
Subarray Sum Equals K
Prefix sum + map of how many times that prefix appeared.
Takeaway
If prefix[j] − prefix[i] = k then a subarray sums to k. Store counts of prefixes as you go; add map[prefix − k]. Zeros and negatives make sliding window wrong — that is the point of this problem.
Related — check that you got it
0/2
- Contiguous ArrayAmazonGoogleMicrosoftMetaBloombergAdobeOracleCisco
Treat 0 as −1; longest subarray with prefix 0. Same map.
- Find the Middle Index in ArrayAmazonGoogleBloombergCode Studio
Prefix vs suffix equality, no hashmap needed.
Takeaway
Two pointers from both ends. Skip non-alphanumeric, compare lowercase. O(n) time, O(1) extra. Building a filtered string is fine but uses space. Palindrome means the same sequence reversed — the pointers just avoid the extra copy.
Related — check that you got it
0/2
- Reverse StringAmazonGoogleMicrosoftMetaAppleBloombergGoldman SachsNVIDIA
Same two pointers, swap toward the middle.
- Valid Palindrome IIAmazonGoogleMicrosoftMetaAppleUberBloombergTikTok
You may delete one character — try skipping left or right once.
Sorted two-sum: move the pointer that can fix the sum.
Takeaway
Because the array is sorted, left+right too small → move left; too big → move right. O(n), O(1) extra. Hashmap still works but wastes the sort. Indices are 1-based on LeetCode — read the prompt.
Related — check that you got it
0/2
- Squares of a Sorted ArrayAmazonGoogleMicrosoftMetaUberBloombergAdobeInfosys
Fill from the back: larger square is at one of the ends.
- 3Sum ClosestAmazonGoogleMicrosoftMetaBloombergFlipkartByteDanceTCS
Fix one index, two-pointer the rest, track best delta.
3Sum
Sort, skip duplicates, two-sum the rest.
Takeaway
Sort, then for each i run two-sum on the suffix. Skip duplicate i and duplicate left/right so you do not emit the same triplet. O(n²). Hashset of triplets is messier. If you cannot skip duplicates cleanly, you do not have 3Sum yet.
Related — check that you got it
0/2
- 4SumAmazonGoogleMicrosoftMetaAppleBloombergLinkedInNVIDIA
Same idea with one more nested loop, still skip duplicates.
Area is min(height) × width. Move the shorter wall.
Takeaway
Start at both ends. Area = min(h[l], h[r]) * (r−l). The limiting height is the shorter side, so move that pointer. Moving the taller one cannot increase min height and always shrinks width. O(n), not O(n²) pairs.
Related — check that you got it
0/2
- Trapping Rain WaterAmazonGoogleMicrosoftMetaAppleUberBloombergAdobe
Water at i is min(leftMax, rightMax) − h[i]. Two pointers or prefix max.
- Trapping Rain Water IIAmazonGoogleMicrosoftMetaBloombergOracleFlipkartByteDance
2-D trapping: heap on the boundary, same min-max idea.
Sort Colors
Dutch national flag: three pointers, one pass.
Takeaway
low/mid/high partition 0s, 1s, 2s in one scan. Swap 0s to the front and 2s to the back; 1s sit in the middle. Counting sort (two passes) is acceptable; the interview often wants the one-pass invariant.
Related — check that you got it
0/2
- Move ZeroesAmazonGoogleMicrosoftMetaAppleUberBloombergAdobe
Partition zeros to the end, keep relative order of the rest.
- Remove Duplicates from Sorted ArrayAmazonGoogleMicrosoftMetaAppleUberBloombergGoldman Sachs
Slow pointer writes uniques, fast pointer scans.
One buy, one sell. Track min so far.
Takeaway
Scan left to right: minPrice is the best buy before today; profit is price − minPrice. You cannot sell before you buy, so a suffix max is the wrong direction. O(n). This is a window of “min on the left.”
Related — check that you got it
0/2
- Best Time to Buy and Sell Stock IIAmazonGoogleMicrosoftMetaAppleBloombergGoldman SachsAtlassian
As many trades as you want — sum every uptick.
- Maximum Average Subarray IAmazonGoogleMicrosoftMetaUberBloombergGoldman SachsJPMorgan
Fixed-size window sum / k.
Grow right, shrink left when a duplicate enters.
Takeaway
A window [l, r] holds unique chars (set or last-index map). When s[r] repeats, move l past the previous copy. Answer is max window length. O(n). Brute O(n²) checks every substring — you should mention it and discard it.
Related — check that you got it
0/2
- Longest Harmonious SubsequenceAmazonGoogleMicrosoftMetaBloombergLiverampZs Associates
Frequency map; subsequence, not substring.
- Number of Substrings Containing All Three CharactersAmazonGoogleMicrosoftMetaBloombergD. E. Shaw
Shrink until the window is invalid; count how many strings end at r.
Window is valid if size − maxFreq ≤ k.
Takeaway
You may replace k letters. The window works if the other letters (length − most frequent char) fit in k. Expand right, shrink left when invalid. You do not have to decrement maxFreq when shrinking (it only makes the check stricter). O(n).
Related — check that you got it
0/2
- Max Consecutive Ones IIIAmazonGoogleMicrosoftMetaBloombergAdobeGoldman SachsOracle
Flip at most k zeros — same “budget inside the window.”
- Max Consecutive OnesAmazonGoogleMicrosoftMetaAppleBloombergTCSAccenture
The k = 0 warmup: just count streaks.
Permutation in String
Fixed window the size of s1; compare counts.
Takeaway
s2 contains a permutation of s1 iff some window of length |s1| has the same counts. Slide a window, update counts in O(1), compare 26 buckets. This is “anagram in a window,” not backtracking permutations.
Related — check that you got it
0/2
- Maximum Number of Vowels in a Substring of Given LengthAmazonGoogleMicrosoftMetaBloombergTCS
Fixed window, maintain a running vowel count.
- Longest Substring with At Least K Repeating CharactersAmazonGoogleMicrosoftMetaBloombergTikTokBaiduHarness
Split on rare chars, then window/divide — same frequency thinking.
Need-counts, missing counter, shrink from the left.
Takeaway
Find the smallest window of s that covers all of t. Track how many required chars you still miss. Expand r until missing is 0, then shrink l while still valid, record min. O(|s| + |t|). If you cannot explain the missing counter, you will off-by-one the shrink.
Related — check that you got it
0/2
- Replace the Substring for Balanced StringAccolite
Minimum window to replace so all four chars are n/4.
- Smallest Range Covering Elements from K ListsAmazonGoogleMicrosoftMetaBloombergLinkedInFlipkartPhonePe
Cover k lists instead of a string — heap + sliding pointers.
Push openers, pop on a matching closer.
Takeaway
A stack holds unmatched open brackets. A closer must match the top. Empty stack at the end means valid. Wrong closer or leftover openers fail. This is the definition of LIFO — if you use a counter only, you cannot handle mixed types.
Related — check that you got it
0/2
- Remove Outermost ParenthesesAmazonGoogleMicrosoftMetaBloombergTCS
Depth counter / stack to know which parens are outer.
- Maximum Nesting Depth of the ParenthesesAmazonGoogleMicrosoftMetaBloombergTCSIntel
Track depth; no matching types, just nesting.
Min Stack
O(1) min with a second stack (or pairs).
Takeaway
Each push stores the value and the min so far (or a parallel min stack). Pop restores the previous min automatically. You cannot scan for min on getMin — that would be O(n). Interviewers want the invariant, not a heap.
Related — check that you got it
0/2
- Implement Stack using QueuesAmazonGoogleMicrosoftMetaAppleBloombergGoldman SachsQualcomm
Same ADT thinking: how do you fake LIFO with FIFO?
- Implement Queue using StacksAmazonGoogleMicrosoftMetaAppleBloombergTikTokInfosys
Two stacks: inbound and outbound.
Daily Temperatures
Monotonic decreasing stack of indices. Next warmer day.
Takeaway
Walk left to right. While today’s temp is warmer than the stack top, pop and fill answer[top] = i − top. Stack stays decreasing. O(n) because each index is pushed/popped once. Nested “scan right” is the brute force you replace.
Related — check that you got it
0/2
- Next Greater Element IAmazonGoogleMicrosoftMetaAppleUberBloombergGoldman Sachs
Monotonic stack on nums2, then map lookups for nums1.
- Next Greater Element IIAmazonGoogleMicrosoftMetaAppleBloombergGoldman SachsNVIDIA
Circular array — walk the array twice on the same stack.
Push numbers, pop two on an operator.
Takeaway
RPN has no parentheses: operators follow their operands. Stack of numbers; when you see +, pop a,b push b+a (order matters for − and /). Integer division toward zero. If the stack size is wrong, the expression was invalid.
Related — check that you got it
0/2
- Basic Calculator IIAmazonGoogleMicrosoftMetaAppleUberBloombergAdobe
Infix with +−*/ and precedence; still a stack of pending terms.
- Decode StringAmazonGoogleMicrosoftMetaAppleBloombergGoldman SachsOracle
Stack of strings and counts for nested k[pattern].
Monotonic increasing stack. Width is the gap between nearest smaller bars.
Takeaway
For each bar, the largest rectangle with that bar as the shortest is bounded by the previous and next smaller bars. A monotonic stack finds those in O(n). Sentinel 0 at the end flushes the stack. If you only know “stack,” this is the problem that proves you know why.
Related — check that you got it
0/2
- Maximal RectangleAmazonGoogleMicrosoftMetaBloombergGoldman SachsSalesforceIntuit
Treat each row as a histogram of consecutive 1s, then this problem.
- Asteroid CollisionAmazonGoogleMicrosoftMetaUberBloombergGoldman SachsOracle
Stack of survivors; collide while the new one can smash the top.
Binary Search
The template. Get lo/hi right once.
Takeaway
On a sorted array, compare mid, discard half. Loop while lo ≤ hi (or lo < hi with a clear invariant). Overflow-safe mid is lo + (hi−lo)//2. Off-by-one is the bug, not the idea. If the array is unsorted, this is the wrong tool.
Related — check that you got it
0/2
- Search Insert PositionAmazonGoogleMicrosoftMetaBloombergInfosysTCSAccenture
Same loop; return lo as the insertion index.
- First Bad VersionAmazonGoogleMicrosoftMetaAppleBloombergWhatnot
Binary search on the answer: first true in a boolean prefix.
Search a 2D Matrix
Treat the matrix as a sorted 1D array.
Takeaway
Rows are sorted and row[i][0] > row[i−1][last], so the whole matrix is sorted in row-major order. Binary search on n*m indices, map to (i/m, i%m). Do not binary-search each row unless the matrix is only sorted per row (that is Search a 2D Matrix II).
Related — check that you got it
0/2
- Search a 2D Matrix IIAmazonGoogleMicrosoftMetaAppleUberBloombergGoldman Sachs
Sorted rows and columns, not globally — start top-right, walk.
- Kth Smallest Element in a Sorted MatrixAmazonGoogleMicrosoftMetaAppleBloombergOracleTikTok
Binary search on value, or a heap of row heads.
Koko Eating Bananas
Binary search on the answer: minimum speed.
Takeaway
The search space is eating speed 1..max(piles). A speed is feasible if hours needed ≤ h. Feasibility is monotonic, so binary search the minimum true speed. This is the template for “minimum X such that predicate holds.”
Related — check that you got it
0/2
- Capacity To Ship Packages Within D DaysAmazonGoogleMicrosoftMetaAppleUberBloombergGoldman Sachs
Same binary search on capacity.
- Split Array Largest SumAmazonGoogleMicrosoftMetaUberBloombergGoldman SachsOracle
Minimize the max bucket sum — still search on the answer.
The min is the rotation pivot. Compare mid to the right end.
Takeaway
One of the two halves is sorted. If nums[mid] > nums[hi], min is to the right of mid; else min is at mid or left. No duplicates in this version. O(log n). Linear scan is correct and will get a follow-up.
Related — check that you got it
0/2
- Find Minimum in Rotated Sorted Array IIAmazonGoogleMicrosoftMetaGoldman Sachs
Duplicates: when nums[mid]==nums[hi], shrink hi by one.
- Find First and Last Position of Element in Sorted ArrayAmazonGoogleMicrosoftMetaAppleUberBloombergGoldman Sachs
Two binary searches: leftmost and rightmost index.
Decide which half is sorted, then whether target sits in it.
Takeaway
At mid, at least one side is strictly sorted. If the left is sorted and target is in that range, search left; otherwise search right (mirror for a sorted right). O(log n). Drawing the rotation once beats memorizing branches.
Related — check that you got it
0/2
- Search in Rotated Sorted Array IIAmazonGoogleMicrosoftMetaBloombergLinkedInCiscoTCS
Duplicates break the sorted test; shrink when equal.
- Time Based Key-Value StoreAmazonGoogleMicrosoftMetaAppleUberBloombergOracle
Binary search timestamps per key — search on a log.
Takeaway
prev = null, cur = head. Next = cur.next, cur.next = prev, then advance. Return prev. Recursion is the same idea on the stack. If you lose the next pointer you orphan the rest of the list. This is the linked-list handshake.
Related — check that you got it
0/2
- Reverse Linked List IIAmazonGoogleMicrosoftMetaAppleBloombergOracleNVIDIA
Reverse a sublist between left and right indices.
- Palindrome Linked ListAmazonGoogleMicrosoftMetaBloombergOracleNVIDIAServiceNow
Find mid, reverse the second half, compare.
Dummy head, always take the smaller node.
Takeaway
Same as merge in merge-sort. Dummy avoids a special first node. Walk both lists, splice the smaller, attach the remainder. O(n+m), O(1) extra if you reuse nodes. New nodes are wasted allocations.
Related — check that you got it
0/2
- Remove Duplicates from Sorted ListAmazonGoogleMicrosoftMetaBloombergOracleNVIDIATCS
Skip equal neighbors on an already sorted list.
- Merge k Sorted ListsAmazonGoogleMicrosoftMetaAppleUberBloombergGoldman Sachs
Heap of k heads, or pairwise merge — same compare, more lists.
Floyd: slow +1, fast +2. They meet iff there is a cycle.
Takeaway
If fast hits null, no cycle. If slow == fast, there is one. A set of seen nodes also works (O(n) space). Floyd is O(1) space. Do not mutate nodes (marking visited) unless the interviewer allows it.
Related — check that you got it
0/2
- Linked List Cycle IIAmazonGoogleMicrosoftMetaBloombergOracleByteDancePaytm
After they meet, restart one pointer at head; they meet at the entrance.
- Find the Duplicate NumberAmazonGoogleMicrosoftMetaBloombergGoldman SachsOracleSalesforce
Array as a linked list (index → nums[index]); same Floyd.
Reorder List
Mid, reverse second half, weave.
Takeaway
L0→L1→…→Ln becomes L0→Ln→L1→Ln−1→… Find mid (slow/fast), reverse the second half, merge by alternating. In-place. If you build an array of nodes it works but uses O(n) space — say so.
Related — check that you got it
0/2
- Odd Even Linked ListAmazonGoogleMicrosoftMetaAppleBloombergGoldman SachsInfosys
Stitch odd indices then even indices, one pass.
- Swap Nodes in PairsAmazonGoogleMicrosoftMetaUberBloombergGoldman SachsOracle
Dummy head; swap every two nodes by rewiring, not values.
Two pointers n apart, dummy head.
Takeaway
Dummy before head so deleting the first node is the same case. Advance fast by n, then move slow and fast until fast is at the end; slow.next is the node to drop. One pass. Two passes (count length) is the honest backup.
Related — check that you got it
0/2
- Remove Linked List ElementsAmazonGoogleMicrosoftMetaAppleBloombergOracleTCS
Dummy head; skip every node whose value equals val.
- Delete Node in a Linked ListAmazonGoogleMicrosoftMetaAppleBloombergAdobeOracle
You only have the node: copy next’s value and skip next.
LRU Cache
Hash map + doubly linked list. O(1) get and put.
Takeaway
Map key → node. List order is recency (head most recent). Get moves a node to the front; put inserts at front and evicts the tail when over capacity. A list/queue alone is O(n) to move. This is the design problem that shows you can combine two structures.
Related — check that you got it
0/2
- LFU CacheAmazonGoogleMicrosoftMetaAppleUberBloombergGoldman Sachs
Same idea plus frequency buckets — harder bookkeeping.
- Design HashMapAmazonGoogleMicrosoftMetaAppleGoldman SachsOracleLinkedIn
Buckets and chaining without the recency list.
Swap left and right, recurse.
Takeaway
The inverted tree has swapped children at every node. Recurse (or BFS) and swap. Base case null. This is a warm-up for “do something to both children and combine.” Interviewers use it to see if recursion on trees is automatic.
Related — check that you got it
0/2
- Same TreeAmazonGoogleMicrosoftMetaAppleBloombergLinkedInTCS
Both null, or values equal and left/right same.
- Symmetric TreeAmazonGoogleMicrosoftMetaAppleBloombergGoldman SachsLinkedIn
Is the tree a mirror? Compare left.left with right.right.
1 + max(left, right).
Takeaway
Depth of null is 0. Otherwise 1 plus the deeper child. BFS level count is the iterative version. This recurrence is the skeleton of diameter, balanced-tree, and path-sum problems.
Related — check that you got it
0/2
- Minimum Depth of Binary TreeAmazonGoogleMicrosoftMetaBloombergTCSLivspace
Min, but a missing child is not depth 0 — only leaves count.
- Balanced Binary TreeAmazonGoogleMicrosoftMetaAppleBloombergVisaViasat
Height difference ≤ 1 at every node; return height or −1 to prune.
BFS with a queue. One level = one inner loop.
Takeaway
Queue starts with root. For each level, take queue.size() nodes, push their children. That inner size snapshot is how you separate levels. DFS with a depth index also works. If you dump all nodes in visit order you do not have level order.
Related — check that you got it
0/2
- Binary Tree Zigzag Level Order TraversalAmazonGoogleMicrosoftMetaAppleBloombergAdobeGoldman Sachs
Same BFS; reverse every other level (or deque).
Each node must lie inside (low, high), not just vs its parent.
Takeaway
Pass down bounds: left child must be < node.val, right > node.val, and the bounds tighten. Checking only node.left.val < node.val misses a right descendant that is too small. Inorder should be strictly increasing — that is the other solution.
Related — check that you got it
0/2
- Kth Smallest Element in a BSTAmazonGoogleMicrosoftMetaUberBloombergOracleLinkedIn
Inorder yields sorted values; stop at k.
- Convert Sorted Array to Binary Search TreeAmazonGoogleMicrosoftMetaAppleBloombergTikTokAirbnb
Mid of the array is root — balanced BST from inorder.
If p and q are in different subtrees, node is the LCA.
Takeaway
Recurse. If the current node is p or q, return it. If both sides return non-null, this node is the LCA. If one side is null, the answer is on the other. BST LCA can walk by value; this version cannot. Do not use parent pointers unless given.
Related — check that you got it
0/2
- Lowest Common Ancestor of a Binary Search TreeAmazonGoogleMicrosoftMetaAppleBloombergLinkedInCapgemini
Walk from root: both smaller → left, both larger → right.
- Diameter of Binary TreeAmazonGoogleMicrosoftMetaAppleBloombergOracleNVIDIA
Longest path may not go through root; compute height and best path in one DFS.
A path can bend. Return a straight gain, record a bent best.
Takeaway
From a node, the value you return to the parent is node + max(0, left, right) — a path that continues upward cannot use both children. The global answer may use both (a bend). Negatives: drop a child with max(0, …). This is diameter with values.
Related — check that you got it
0/2
- Path SumAmazonGoogleMicrosoftMetaAppleBloombergGoldman SachsTikTok
Root-to-leaf equals target — simpler boolean DFS.
- Path Sum IIAmazonGoogleMicrosoftMetaBloombergOracleFlipkartTikTok
Record every root-to-leaf that hits target.
Preorder with null markers, or BFS with queue.
Takeaway
Encode structure, not just values: you need a placeholder for missing children or you cannot rebuild. Preorder string with “#” or BFS level order both work. Deserialize consumes the same format. This is a design problem: pick a format and stick to it.
Related — check that you got it
0/2
- Flatten Binary Tree to Linked ListAmazonGoogleMicrosoftMetaBloombergOracleJosh TechnologyAnduril
Preorder into a right spine; Morris or extra list.
- Construct Binary Tree from Preorder and Inorder TraversalAmazonGoogleMicrosoftMetaBloombergAdobeSalesforceTikTok
Preorder gives root; inorder splits left/right sizes.
At each node, is the tree identical to subRoot?
Takeaway
DFS on the big tree; at each node run same-tree against subRoot. O(n·m) is acceptable at this difficulty. Serialization of every subtree is an alternative. Do not confuse with “is subRoot a node value somewhere.”
Related — check that you got it
0/2
- Merge Two Binary TreesAmazonGoogleMicrosoftMetaBloombergLinkedInJosh TechnologyMongodb
Sum overlapping nodes; take the non-null child otherwise.
- Count Complete Tree NodesAmazonGoogleMicrosoftMetaBloombergAdobeDunzo
Use complete-tree height to count in better than O(n).
Size-k min-heap, or quickselect.
Takeaway
A min-heap of size k: if you see a larger number, pop the min. The heap min is the kth largest. Full sort is O(n log n); heap is O(n log k). Quickselect is average O(n) and is the follow-up. “Largest” means min-heap of k, not max-heap of n.
Related — check that you got it
0/2
- Kth Largest Element in a StreamAmazonGoogleMicrosoftMetaBloombergAdobeGoldman SachsSalesforce
Keep the heap alive across add() calls.
- Third Maximum NumberAmazonGoogleMicrosoftMetaBloombergGoldman SachsNVIDIATCS
Track three distinct maxes — tiny k, no heap required.
Always smash the two heaviest: max-heap.
Takeaway
Max-heap (or sort each time). Pop two, push the difference if nonzero. Last remaining (or 0) is the answer. This is “priority queue as the next event.” Last Stone II is DP, not a heap.
Related — check that you got it
0/2
- Furthest Building You Can ReachAmazonGoogleMetaUberBloombergTikTokPhonePeTwilio
Heap of climbs; ladders for the biggest jumps.
- The K Weakest Rows in a MatrixAmazonGoogleMicrosoftMetaBloomberg
Count soldiers, then a size-k heap of rows.
Two heaps: max-heap of the lower half, min-heap of the upper.
Takeaway
Balance so sizes differ by at most one. Median is the top of the larger heap, or the average of both tops. Every insert is O(log n). Sorting the whole stream on each insert is the thing you are replacing.
Related — check that you got it
0/2
- Sliding Window MedianAmazonGoogleMicrosoftMetaAppleBloombergSalesforceDoorDash
Same two heaps, plus lazy deletion as the window moves.
- Find Right IntervalAmazonGoogleMicrosoftBloomberg
Sort starts, binary search — heap optional; still “next best.”
Task Scheduler
Idle time is forced by the most frequent task.
Takeaway
If the hottest task appears f times, you need at least (f−1)*(n+1) + count_of_tasks_with_freq_f slots. A max-heap simulation (cycle of n+1) also works and is easier to remember. Greedy formula is O(26). Do not simulate a clock if you have the formula.
Related — check that you got it
0/2
- Reorganize StringAmazonGoogleMicrosoftMetaBloombergGoldman SachsOracleSalesforce
No two same letters adjacent — max-heap of counts.
- Least Number of Unique Integers after K RemovalsAmazonGoogleOracleSalesforceMorgan StanleyFivetranWayfair
Remove smallest buckets first — greedy on frequencies.
Subsets
At each index: include or skip. The template.
Takeaway
Decision tree: for nums[i], append it and recurse, then pop (backtrack), then recurse without it. Or loop “choose next from i..n.” 2^n subsets. Sorting is not required unless you have duplicates (Subsets II). If you mutate a shared list, copy it when you record a subset.
Related — check that you got it
0/2
- Subsets IIAmazonGoogleMicrosoftMetaAppleBloombergTCSUipath
Skip duplicate values at the same depth so you do not emit the same subset.
- Letter Case PermutationAmazonGoogleMicrosoftMetaBloombergTikTokYelp
Branch on upper/lower for letters; digits stay.
Combination Sum
Reuse the same number. Recurse with i, not i+1.
Takeaway
You may pick a candidate as many times as you want, so recurse with the same index after choosing. Prune when remaining < 0. Combination Sum II forbids reuse and needs duplicate-skipping. Order inside a combination does not matter — start index enforces that.
Related — check that you got it
0/2
- Combination Sum IIAmazonGoogleMicrosoftMetaBloombergAdobeOracleSalesforce
Each number once; skip duplicates after sorting.
Permutations
Swap or used[], generate n! orderings.
Takeaway
Unlike subsets, order matters and you use every element. Swap nums[start] with later indices, recurse start+1, swap back. Or a used boolean array. n! output — do not try to beat that. Permutations II adds duplicate skipping.
Related — check that you got it
0/2
- Permutations IIAmazonGoogleMicrosoftMetaAppleBloombergGoldman SachsLinkedIn
Sorted input; skip used duplicates at the same depth.
- Next PermutationAmazonGoogleMicrosoftMetaUberBloombergAdobeGoldman Sachs
In-place next lexicographic permutation — no search tree.
Word Search
DFS from each cell, mark visited, unmark.
Takeaway
From a cell matching word[0], try 4 directions for word[1:]. Mark the cell used (then restore) so you cannot reuse it in one path. This is backtracking on a grid, not a trie yet (that is Word Search II). Prune early when the letter mismatches.
Related — check that you got it
0/2
- Path with Maximum GoldAmazonGoogleMicrosoftGoldman SachsSalesforce
Same DFS + unmark; maximize gold instead of matching a word.
- Letter Combinations of a Phone NumberAmazonGoogleMicrosoftMetaAppleUberBloombergGoldman Sachs
Classic decision tree on digits → letters.
N-Queens
Place one queen per row. Attack columns and diagonals.
Takeaway
row r, try columns. Track used cols, diag (r−c), anti-diag (r+c). Record a board when r == n. N-Queens II only counts. The bit of design is the three sets, not drawing a chessboard in ASCII.
Related — check that you got it
0/2
- Sudoku SolverAmazonGoogleMicrosoftMetaAppleUberBloombergGoldman Sachs
Backtrack empty cells with row/col/box constraints.
Number of Islands
DFS/BFS flood fill. Each flood is one island.
Takeaway
A land cell starts a new island; DFS/BFS marks the whole connected component water (or visited). Count how many times you start. This is connected components on a grid. Union-find is optional. Do not count land cells — count components.
Related — check that you got it
0/2
- Max Area of IslandAmazonGoogleMicrosoftMetaAppleBloombergAdobeGoldman Sachs
Same flood fill; return the size of the largest component.
- Surrounded RegionsAmazonGoogleMicrosoftMetaUberBloombergAdobeOracle
Flood from the border Os first; remaining Os are captured.
Clone Graph
DFS/BFS plus a map of old node → new node.
Takeaway
You must copy nodes and edges without looping forever. Map original → clone; when you see a neighbor already in the map, connect to that clone. This is graph copy, same idea as copy-list-with-random-pointer.
Related — check that you got it
0/2
- Keys and RoomsAmazonGoogleMicrosoftMetaAppleOracleSnowflakeInfosys
Can you visit every room? DFS/BFS from 0 on an adjacency list.
- Find the Town JudgeAmazonGoogleMicrosoftMetaBloombergArista NetworksTuring
Indegree/outdegree, not a traversal.
Course Schedule
Cycle detection in a directed graph. Topological sort.
Takeaway
Prereq edges a→b mean “take a before b” (or the reverse — pick one and stick to it). A cycle means impossible. Kahn’s algorithm (indegree queue) or DFS colors (visiting vs done). Course Schedule II returns a valid order. If you only DFS without a visiting state, you will miss cycles.
Related — check that you got it
0/2
- Course Schedule IIAmazonGoogleMicrosoftMetaAppleUberBloombergGoldman Sachs
Same graph; emit the topological order.
- Find Eventual Safe StatesAmazonGoogleMicrosoftMetaUberBloombergCitadel
Nodes that cannot reach a cycle — coloring DFS.
Search inland from both oceans. Intersect.
Takeaway
Water flows to equal-or-lower neighbors. Reverse the edges: DFS/BFS from Pacific-touching cells and Atlantic-touching cells uphill. Cells in both sets are the answer. Searching from every cell to the ocean is the slow version.
Related — check that you got it
0/2
- Number of EnclavesAmazonGoogleMicrosoftMetaBloomberg
Flood from the border; leftover land cannot walk off.
- Count Sub IslandsAmazonGoogleDoorDashXZepto
An island in grid2 is a sub-island only if all its cells are land in grid1.
Rotting Oranges
Multi-source BFS. Minutes = levels.
Takeaway
All initially rotten oranges are the first BFS layer. Each minute, rot 4-neighbors. If fresh oranges remain, return −1. This is shortest time on an unweighted grid. DFS does not give minutes cleanly.
Related — check that you got it
0/2
- 01 MatrixAmazonGoogleMicrosoftMetaAppleUberBloombergAdobe
Multi-source BFS from every 0; distance to nearest 0.
- Shortest Path in Binary MatrixAmazonGoogleMicrosoftMetaAppleUberBloombergGoldman Sachs
BFS 8-direction from (0,0) to (n−1,n−1).
Word Ladder
BFS on words. Neighbors differ by one letter.
Takeaway
Each word is a node; an edge exists if they differ by one character. BFS from beginWord to endWord gives the shortest ladder length. Wildcard buckets (hit → *it, h*t, hi*) beat generating 26 letters naively if the dictionary is large. Bidirectional BFS is a bonus.
Related — check that you got it
0/2
- Open the LockAmazonGoogleMicrosoftMetaUberBloombergGoldman SachsOracle
BFS on 4-digit wheels; deadends are blocked nodes.
- Nearest Exit from Entrance in MazeAmazonGoogleMicrosoftMetaUberBloombergPayPalEbay
BFS to the nearest border empty cell.
Network Delay Time
Dijkstra from k. Answer is max dist, or −1.
Takeaway
Weighted directed graph, non-negative times → Dijkstra (min-heap of arrival time). The time for all nodes to receive the signal is the max distance. If some node is unreachable, −1. BFS is wrong because edges have weights. Bellman-Ford is the k-stops variant.
Related — check that you got it
0/2
- Cheapest Flights Within K StopsAmazonGoogleMicrosoftMetaAppleUberBloombergIntuit
At most k edges — Bellman-Ford / BFS-DP, not plain Dijkstra.
- Path With Minimum EffortAmazonGoogleMicrosoftMetaBloombergSnowflakeVisaWaymo
Dijkstra where the cost is max edge effort, not a sum.
Climbing Stairs
dp[i] = dp[i−1] + dp[i−2]. Fibonacci in disguise.
Takeaway
To reach step i you came from i−1 or i−2. Base: 1 way to stand on 0 or 1. This is the first DP recurrence you should be able to write without a template. O(n) time, O(1) space if you keep two variables.
Related — check that you got it
0/2
- Min Cost Climbing StairsAmazonGoogleMicrosoftMetaBloombergTCSSquarepoint Capital
Same recurrence, minimize cost instead of counting ways.
- Fibonacci NumberAmazonGoogleMicrosoftMetaAppleBloombergNVIDIAInfosys
The same two-term recurrence without the stair story.
House Robber
Cannot rob adjacent houses. dp[i] = max(dp[i−1], dp[i−2] + nums[i]).
Takeaway
At house i, skip it (take dp[i−1]) or rob it (dp[i−2] + value). Linear houses. House Robber II is a circle — run the linear version twice (skip first or skip last). If you take both neighbors you broke the rule.
Related — check that you got it
0/2
- House Robber IIAmazonGoogleMicrosoftMetaAppleUberBloombergSalesforce
Circular street — two linear passes.
- Delete and EarnAmazonGoogleMicrosoftMetaBloombergSalesforceTikTokInfosys
Turn values into House Robber on a frequency array.
Coin Change
Unbounded knapsack: fewest coins to make amount.
Takeaway
dp[x] = min over coins of 1 + dp[x − coin], if x ≥ coin. dp[0] = 0, else Inf. Unbounded because you may reuse a coin. Combination Sum counted ways with order rules; this minimizes count. If dp[amount] is Inf, return −1.
Related — check that you got it
0/2
- Coin Change IIAmazonGoogleMicrosoftMetaBloombergSalesforceTikTokMastercard
Count combinations (order does not matter) — loop coins outside the amount.
- Combination Sum IVAmazonGoogleMicrosoftMetaBloombergTikTokSnap
Count permutations (order matters) — loop amount outside the coins.
Word Break
dp[i] true if some word ends at i and dp[start] was true.
Takeaway
Can s[0..i) be segmented with the dictionary? Try each word (or each split). A set of words makes lookup O(1). Word Break II asks for all sentences. Recursion without memo is exponential on repeated prefixes.
Related — check that you got it
0/2
- Word Break IIAmazonGoogleMicrosoftMetaUberBloombergOracleTikTok
Same cuts, reconstruct every valid sentence.
dp[i] = 1 + max dp[j] for j < i and nums[j] < nums[i].
Takeaway
O(n²) DP is the expected first answer. Patience sorting / tails binary search is O(n log n) and is the follow-up. Subsequence is not subarray — elements need not be adjacent. If you sort, you destroy the order constraint.
Related — check that you got it
0/2
- Number of Longest Increasing SubsequenceAmazonGoogleMicrosoftMetaBloombergTikTok
Keep a count[] alongside length[].
- Russian Doll EnvelopesAmazonGoogleMicrosoftMetaBloombergGoldman SachsAtlassianIntuit
Sort width, LIS on height (with a width-desc trick).
Decode Ways
A digit and a pair 10–26. dp[i] from one and two-char tails.
Takeaway
Ways to decode s[0..i): if s[i−1] is 1–9, add dp[i−1]; if s[i−2..i) is 10–26, add dp[i−2]. Leading zeros are invalid. This is climbing stairs with extra validity checks. Decode Ways II adds stars.
Related — check that you got it
0/2
- Count Number of TextsAmazonMicrosoftGoldman Sachs
Phone keypad runs of the same digit — decode-ways family.
Maximum Subarray
Kadane: best ending here vs start fresh.
Takeaway
dp[i] = max(nums[i], dp[i−1] + nums[i]) — the best subarray that ends at i. Answer is max of those. Empty subarray is not allowed on LeetCode. Divide-and-conquer is the follow-up, not the first answer. Maximum product is a related trap (negatives flip).
Related — check that you got it
0/2
- Maximum Sum Circular SubarrayAmazonGoogleMicrosoftMetaAppleBloombergGoldman SachsTikTok
Max of Kadane vs total − min subarray (careful with all-negative).
- Maximum Product SubarrayAmazonGoogleMicrosoftMetaBloombergAdobeGoldman SachsSalesforce
Track min and max ending here because negatives swap them.
Unique Paths
Only right and down. dp[i][j] = dp[i−1][j] + dp[i][j−1].
Takeaway
A robot on an m×n grid. First row/col are 1s. Combinatorics C(m+n−2, m−1) is a bonus. Unique Paths II adds obstacles (those cells are 0). If you recurse without memo you recompute the same cell exponentially.
Related — check that you got it
0/2
- Unique Paths IIAmazonGoogleMicrosoftMetaBloombergNVIDIATikTokAgoda
Same grid DP; obstacle cells contribute 0.
- Minimum Path SumAmazonGoogleMicrosoftMetaUberBloombergGoldman SachsNVIDIA
Same structure, min of top/left plus the cell.
If letters match, 1 + diag; else max(skip one from either string).
Takeaway
dp[i][j] = LCS of prefixes. Match → dp[i−1][j−1]+1, else max(dp[i−1][j], dp[i][j−1]). Subsequence, not substring (substring would be a consecutive run). This table is also edit distance with different recurrences.
Related — check that you got it
0/2
- Shortest Common SupersequenceAmazonGoogleMicrosoftMetaBloomberg
len(a)+len(b)−LCS; reconstruct from the table.
Edit Distance
Insert, delete, replace. Min operations to turn word1 into word2.
Takeaway
dp[i][j] for prefixes. If chars equal, copy diag. Else 1 + min(insert, delete, replace). This is LCS’s cousin: LCS maximizes keeps, edit distance minimizes edits. O(nm) time. If you only know recursive Levenshtein, memoize it into this table.
Related — check that you got it
0/2
- Minimum ASCII Delete Sum for Two StringsAmazonGoogleMetaTriplebyte
Delete-only edit distance, costs are ASCII values.
0/1 knapsack: can you hit total/2?
Takeaway
If total is odd, false. Else subset-sum to total/2 with each number used at most once. Boolean DP over achievable sums (1D rolling array, iterate numbers backward). This is the 0/1 knapsack interview. Unbounded would be coin change.
Related — check that you got it
0/2
- Target SumAmazonGoogleMicrosoftMetaBloombergServiceNowPinterestZoho
Assign +/− to hit target — rewrite as subset sum.
DFS + memo on a DAG of increasing neighbors.
Takeaway
From each cell, the longest strictly increasing path is 1 + max of valid neighbors. Memoize by cell. No cycles because values strictly increase. Plain 2D DP left-to-right fails; the order is the values, not the indices. Topological DP is the same idea.
Related — check that you got it
0/2
- Maximal SquareAmazonGoogleMicrosoftMetaAppleBloombergGoldman SachsOracle
dp[i][j] = 1 + min of three neighbors if cell is 1.
- Count Square Submatrices with All OnesAmazonGoogleMicrosoftMetaBloombergGoldman Sachs
Same recurrence, sum the table.
Jump Game
Track the farthest index you can still reach.
Takeaway
Scan left to right. If i is beyond farthest, you are stuck. Otherwise farthest = max(farthest, i + nums[i]). Greedy reach, not DP. Jump Game II asks for the minimum number of jumps (another greedy, layers).
Related — check that you got it
0/2
- Jump Game IIAmazonGoogleMicrosoftMetaAppleBloombergAdobeGoldman Sachs
Minimum jumps: BFS layers / greedy farthest per jump.
Gas Station
If total gas ≥ total cost, a start exists. Find where the tank never went negative.
Takeaway
One pass: tank += gas[i]−cost[i]. If tank drops below 0, the start cannot be anything so far — set start to i+1 and reset tank. Total sum < 0 → −1. This is the “unique circuit” greedy. Simulating n starts is O(n²).
Related — check that you got it
0/2
- CandyAmazonGoogleMicrosoftMetaUberBloombergGoldman SachsOracle
Two greedy passes for ratings — local peaks need more candy.
Merge Intervals
Sort by start. Merge if the next start ≤ current end.
Takeaway
After sorting, overlapping intervals glue into one. Current end = max of ends while they overlap. If you do not sort, you miss overlaps. Touching intervals (end == next start) merge on LeetCode. This is the interval primitive.
Related — check that you got it
0/2
- Interval List IntersectionsAmazonGoogleMicrosoftMetaAppleUberBloombergDoorDash
Two sorted lists; advance the one that ends first.
- Teemo AttackingAmazonGoogleTCSRiot GamesJane Street
Merge poison durations — same overlap math on a timeline.
Insert Interval
Add the new interval, then merge — or splice in one pass.
Takeaway
Walk the sorted list: emit intervals that end before the new one, merge all that overlap the new one, emit the rest. You can concat-and-merge, but the linear splice is the intended skill. Do not binary-search unless you still merge after.
Related — check that you got it
0/2
- Summary RangesAmazonGoogleMicrosoftMetaBloombergNetflixYandexTinkoff
Sorted unique nums collapsed into interval strings.
- My Calendar IAmazonGoogleMicrosoftMetaAppleUberBloombergOracle
Book a slot only if it overlaps none — interval invariant.
Minimum removals = n − max non-overlapping. Sort by end.
Takeaway
To keep the most intervals, always take the one that finishes first (sort by end). Removals are the rest. This is interval scheduling, the same greedy as “meeting rooms you can attend.” Sorting by start is the usual bug.
Related — check that you got it
0/2
- Minimum Number of Arrows to Burst BalloonsAmazonGoogleMicrosoftBloombergGoldman SachsTikTokZohoLivspace
Arrows = groups of overlapping balloons; still sort by end.
Partition Labels
Each letter’s last index bounds a partition.
Takeaway
For each letter, record its last occurrence. Scan left to right, extend the current end to the farthest last-index you have seen. When i == end, cut a partition. Greedy “must include this letter’s last copy.”
Related — check that you got it
0/2
- Partition Array into Disjoint IntervalsGoogleMicrosoft
Left max ≤ right min — prefix max vs suffix min.
Hand of Straights
Greedy: always fill a group from the current minimum.
Takeaway
Count frequencies. Repeatedly take the smallest remaining number and consume W consecutive values. If any count goes negative, fail. TreeMap / sorted keys make “current min” easy. This is greedy on a multiset, not DP.
Related — check that you got it
0/2
- Find Original Array From Doubled ArrayAmazonGoogleMetaBloombergGoldman SachsVerily
Greedy match x with 2x from the smallest remaining.
Children map + end-of-word flag. The structure, not a library.
Takeaway
Each node has up to 26 children and a boolean “word ends here.” insert/search/startsWith walk the letters. Hashing whole strings does not give prefix queries in O(length). This is the data structure for autocomplete and Word Search II.
Related — check that you got it
0/2
- Design Add and Search Words Data StructureAmazonGoogleMicrosoftMetaAppleBloombergOracleAtlassian
Trie plus DFS when the query has ‘.’ wildcards.
- Replace WordsGoogleMicrosoftUberTikTok
Replace a word with the shortest dictionary prefix — trie or a set of roots.
Word Search II
Trie of the dictionary, DFS on the board, prune dead prefixes.
Takeaway
Build a trie of words, DFS from each cell, follow trie edges, unmark the cell. Chop a word off the trie when found to avoid duplicates. Without a trie you restart the dictionary at every path. This is Word Search scaled up.
Related — check that you got it
0/2
- Search Suggestions SystemAmazonGoogleMicrosoftMetaUberBloombergAdobeOracle
Trie or sort + binary search for prefixes as the user types.
- Implement Magic DictionaryGoogleBloomberg
Search with exactly one mismatch — trie or a length bucket.
Single Number
XOR cancels pairs. O(1) extra space.
Takeaway
a xor a = 0, a xor 0 = a, xor is associative. XOR the whole array; pairs vanish, the unique remains. A set/map is O(n) space and misses the point. Single Number II (threes) needs bits or a different trick.
Related — check that you got it
0/2
- Single Number IIAmazonGoogleMicrosoftMetaBloomberg
Every number appears three times except one — count bits mod 3.
- Single Number IIIAmazonGoogleMicrosoftBloombergOracleZomatoSiemens
Two uniques: XOR all, then split by a distinguishing bit.
Rotate Image
Transpose, then reverse each row (clockwise).
Takeaway
In-place 90° clockwise: transpose the matrix, then reverse every row. Layer-by-layer four-way swap is the other solution. Extra matrix is correct but not the interview. Draw a 3×3 once. Spiral Matrix is a walk, not a rotate.
Related — check that you got it
0/2
- Spiral MatrixAmazonGoogleMicrosoftMetaAppleUberBloombergAdobe
Walk the boundary, shrink the box, four directions.
- Spiral Matrix IIAmazonGoogleMicrosoftMetaBloombergAdobeGoldman SachsTikTok
Fill 1..n² in spiral order — same boundary walk.
More reading
Books and platforms for this phase. Read the topics above first.
LeetCode Problemset
Primary coding-interview practice platform.
Striver A2Z DSA Sheet
A long structured sheet if you want more volume after the list on this site.
Love Babbar DSA Sheet
450-problem sheet used widely in Indian campus prep. Extra volume, not a second curriculum.