Roadmap
Learn in this order. Filter if you are catching up.
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.
Phase 2
CS Fundamentals
OS, DBMS + SQL, Networks, OOP — enough to clear theory rounds. · 4–6 weeks
Process vs Thread
Address space, cost of creation, shared memory. Asked in almost every OS round.
A process is an isolated running program with its own address space, file descriptors, and resources. A thread is a unit of execution inside a process; threads share that process’s memory and open files. Creating a process is expensive (new address space); creating a thread is cheap. Shared memory is why threads need locks — two threads writing the same variable without synchronization is a race.
More reading
Learn
Interview questions
Process states
New, ready, running, waiting, terminated — and what causes each transition.
A process moves through a small set of states: new (created), ready (waiting for CPU), running (on a core), waiting/blocked (I/O or a lock), and terminated. The scheduler picks from ready; a blocking syscall moves running → waiting; I/O completion moves waiting → ready. Interviewers want the transitions, not a memorized diagram.
Context switching
What is saved/restored, why it is expensive, when it happens.
A context switch is the OS saving one thread/process’s CPU state (registers, program counter, stack pointer) and loading another’s so it can run. It happens on timer interrupts, blocking syscalls, and preemption. It is expensive because of register save/restore, cache/TLB disruption, and (for processes) address-space switches. Threads in the same process are cheaper to switch than processes.
CPU scheduling
FCFS, SJF, SRTF, Round Robin, Priority. Convoy effect, starvation.
The CPU scheduler decides which ready process runs next. FCFS is fair but can convoy (a long job blocks short ones). SJF/SRTF minimize average wait but need burst estimates and can starve long jobs. Round Robin gives each a time slice — good for interactive work. Priority scheduling can starve unless you age waiting jobs. Know when each fails, not just the names.
Mutex
Mutual exclusion for a critical section. Lock/unlock, who can unlock.
A mutex is a lock that only one thread can hold at a time, protecting a critical section. The thread that locks it must unlock it — unlike a semaphore, you cannot “unlock” on behalf of someone else. If you forget to unlock (or throw before unlock), other threads wait forever. Use it when the invariant is “only one thread may touch this data.”
Semaphore
Counting vs binary. Producer-consumer. Difference from mutex.
A semaphore is a counter with wait (P/down) and signal (V/up). A binary semaphore is 0/1 and looks like a lock, but any thread may signal — so it is not a mutex. A counting semaphore tracks N resources (buffer slots, connections). Classic use: producer-consumer, where empty/full counts wake the other side. Interview distinction: mutex has an owner; semaphore does not.
Race conditions
Shared data, lost updates, why locks exist.
A race condition is when the result depends on which thread wins the timing — typically two threads read-modify-write the same variable without a lock, and one update is lost. Races are bugs you cannot reliably reproduce. Locks, atomics, and not sharing data are the fixes. If two threads can see the same memory, assume you need a story for how it stays consistent.
Deadlocks
Four Coffman conditions, prevention vs avoidance vs detection, Banker's algorithm at a high level.
Deadlock is when threads wait forever because each holds a lock the other needs. Four Coffman conditions must all hold: mutual exclusion, hold-and-wait, no preemption, circular wait. Break any one (lock ordering is the usual fix) and deadlock cannot happen. Prevention designs the system so a condition cannot hold; avoidance (Banker’s) is rarely used in apps; detection finds cycles and aborts. Interviewers want an example, the four conditions, and lock ordering.
More reading
Interview questions
Virtual memory
Why every process thinks it has the whole address space.
Virtual memory gives each process its own address space: pointers in your program are virtual addresses that the MMU translates to physical RAM (or disk). The OS can overcommit, isolate processes, and map the same library into many processes. A process cannot read another’s memory by guessing addresses. Page tables and the TLB are how translation stays fast.
Paging
Pages vs frames, page table, TLB.
Paging splits virtual memory into fixed-size pages and physical RAM into frames of the same size. A page table maps page → frame (or “not in RAM”). The TLB caches recent translations so you do not walk the page table on every load/store. Internal fragmentation is at most almost one page per mapping. Demand paging loads a page only when you first touch it.
Page faults
Minor vs major, what the OS does on a fault.
A page fault is a trap when the CPU accesses a virtual page that is not currently mapped the way the process needs. A minor fault is cheap (page is already in RAM — maybe shared or not yet mapped). A major fault must read from disk (or the swap file) — that is why “thrashing” kills performance. The OS finds a free frame, loads the page, updates the page table, and restarts the instruction.
Stack vs Heap
Function frames vs dynamic allocation. What lives where in Java/C++.
The stack holds function frames: locals, arguments, return addresses. It grows and shrinks with calls; allocation is a pointer bump, and it is per-thread. The heap is for data whose lifetime is not a single call — malloc/new, objects in Java. Heap allocation is slower and can fragment; forgetting to free (C++) or holding references (Java) leaks. Recursion depth is limited by stack size; large objects belong on the heap.
User mode vs Kernel mode
Privilege rings, why apps cannot talk to hardware directly.
CPUs run in privilege levels. User mode is where your app runs: it cannot change page tables, talk to devices, or halt the machine. Kernel mode is where the OS runs those privileged operations. A syscall or interrupt is the controlled switch into kernel mode. This split is why a crashing app should not take down the whole system.
System calls
How user code asks the kernel to do privileged work.
A system call is the API from user space to the kernel: open a file, read, fork, mmap, send a packet. The process traps (syscall instruction), the kernel validates arguments, does the work, and returns. Library functions like printf often wrap syscalls (write). You cannot implement true isolation or I/O in pure user code — that is the point of the boundary.
Primary key
Uniqueness + not null. One primary key per table.
A primary key uniquely identifies every row and cannot be NULL. A table has at most one. It is the default target for foreign keys and the clustered index in many engines (MySQL InnoDB). Prefer a stable key (often a surrogate id) so updates do not cascade through the schema. Uniqueness without “the” primary key is a unique constraint or candidate key.
More reading
Foreign key
Referential integrity. ON DELETE CASCADE vs RESTRICT.
A foreign key is a column (or set) that must match a candidate/primary key in another table — or be NULL if allowed. That is referential integrity: you cannot orphan a child row pointing at a missing parent. ON DELETE RESTRICT/NO ACTION refuses to delete a parent with children; CASCADE deletes children too; SET NULL clears the pointer. Pick CASCADE only when the child has no meaning without the parent.
More reading
Candidate key
Minimal unique identifier. Primary key is one chosen candidate.
A candidate key is a minimal set of columns that uniquely identifies a row — drop any column and uniqueness breaks. A table can have several (email and user_id). You pick one as the primary key; the others stay as unique constraints. Superkeys include extra columns and are not minimal.
More reading
Normalization
1NF, 2NF, 3NF, BCNF. Anomalies you are trying to prevent.
Normalization is splitting tables so each fact is stored once, which prevents update/insert/delete anomalies. 1NF: atomic cells, no repeating groups. 2NF: no partial dependency on a composite key. 3NF: no transitive dependency (non-key → non-key). BCNF is a stricter 3NF. You denormalize later for read performance — know why you are doing it, not as a default.
More reading
Interview questions
Transactions
BEGIN / COMMIT / ROLLBACK. Atomic unit of work.
A transaction is a group of reads/writes that must succeed or fail together. BEGIN starts it, COMMIT makes it durable and visible (per isolation), ROLLBACK undoes it. If the process crashes mid-transaction, the database restores the previous committed state. Use a transaction whenever “half of this update” would leave the data wrong (transfer money, place an order and decrement stock).
ACID
Atomicity, Consistency, Isolation, Durability — with one example each.
ACID is the contract for transactions. Atomicity: all statements commit or none do (transfer both accounts). Consistency: constraints and invariants hold after commit (FK, checks). Isolation: concurrent transactions do not see each other’s dirty work (level-dependent). Durability: after COMMIT, a crash does not lose the write (WAL). Interviewers want a one-line example for each letter, not the acronym only.
More reading
Interview questions
Isolation levels
Read uncommitted → serializable. What each allows.
Isolation levels trade consistency for concurrency. Read uncommitted can dirty-read. Read committed (Postgres default) sees only committed data but non-repeatable reads and phantoms are possible. Repeatable read freezes the snapshot of rows you already read (Postgres also prevents phantoms via snapshots). Serializable behaves as if transactions ran one after another — may abort with serialization failures you must retry. Name the anomalies each level still allows.
Dirty reads
Reading uncommitted data from another transaction.
A dirty read is seeing another transaction’s uncommitted write. If that transaction rolls back, you acted on data that never existed. Read uncommitted allows this; higher levels do not. This is why production databases almost never use read uncommitted.
Non-repeatable reads
Same row, two reads, different values inside one transaction.
A non-repeatable read is when you SELECT the same row twice in one transaction and get different committed values because another transaction committed an UPDATE in between. Read committed allows this; repeatable read and serializable do not (you keep your snapshot of that row). Distinct from dirty reads (uncommitted) and phantoms (new rows).
Phantom reads
New rows appear in a range you already queried.
A phantom is when a second query in the same transaction sees new rows that match your WHERE clause because another transaction committed an INSERT. You did not re-read a changed row — the set of rows grew. Range locks or snapshot isolation are how engines prevent this. Interviewers pair this with non-repeatable reads to see if you know the difference.
Locks
Shared vs exclusive. Deadlocks in databases.
Databases lock rows (or keys/pages) so concurrent transactions do not corrupt data. Shared (read) locks can coexist; exclusive (write) locks do not. Deadlocks happen when A waits for B’s lock and B waits for A’s — the engine aborts one victim. Keep transactions short, lock in a consistent order, and do not hold locks while calling slow external APIs.
More reading
Indexes
Speed up reads, slow down writes. When not to index.
An index is extra structure (usually a B+ tree) that lets the engine find rows without scanning the table. Reads and ORDER BY/JOIN can get much faster; every INSERT/UPDATE/DELETE must maintain the index, so writes get slower. Index columns you filter and join on; skip low-selectivity columns (boolean flags) and tables that are tiny. Too many indexes is a real production problem.
More reading
B-Tree / B+ Tree
Why databases use B+ trees for indexes.
A B-tree keeps keys in a wide, balanced tree so lookups are O(log n) disk I/Os, which matters because disks are slow. A B+ tree stores all row pointers in the leaf level and links leaves, so range scans (WHERE x BETWEEN) walk sequentially. That is why default indexes are B+ trees, not binary trees in RAM. Hash indexes only help equality, not ranges.
More reading
Clustered vs Non-clustered indexes
Table order vs separate structure. Postgres vs MySQL mental model.
A clustered index is the table itself sorted by the key (InnoDB primary key): one clustered index per table. A secondary/non-clustered index is a separate tree that points to rows (by PK in InnoDB, by heap tid in Postgres). Postgres tables are heaps; all indexes are secondary. The interview point: clustered defines physical order; you cannot have two clustered indexes.
More reading
Joins
INNER, LEFT, RIGHT, FULL, CROSS. Nested loop vs hash join at a high level.
A join combines rows from two tables using a condition. INNER keeps matches only. LEFT keeps all left rows (NULL-padded if no match). RIGHT is the mirror. FULL keeps both sides. CROSS is every combination. Engines pick nested loop (good if one side is tiny or indexed) or hash join (build a hash of the smaller side). Write the join you mean; do not filter a LEFT JOIN in WHERE so it accidentally becomes INNER.
Views
Saved query. Updatable vs read-only.
A view is a named SELECT stored in the catalog. Querying it runs that SQL (or a rewritten plan). Views simplify APIs and hide columns; they are not a copy of the data unless you materialize them. Simple views can be updatable; joins and aggregates usually are not. Use views for a stable interface, not as a substitute for indexes.
More reading
SELECT
Projection. DISTINCT. Column aliases.
SELECT lists the columns (or expressions) you want — projection. FROM is the source; without WHERE you get every row. DISTINCT removes duplicate result rows after projection. Aliases (AS) name expressions for the client and for ORDER BY. SELECT * is fine while exploring; in production, name columns so schema changes do not surprise you.
WHERE
Filtering rows. AND/OR, IN, LIKE, NULL.
WHERE filters rows before grouping. AND/OR combine predicates; IN tests a set; LIKE is pattern match. NULL is not equal to anything — use IS NULL / IS NOT NULL, never = NULL. WHERE cannot see aliases defined in the same SELECT list in most engines. Put row filters here; put aggregate filters in HAVING.
GROUP BY
Collapse rows. Must appear in SELECT or aggregate.
GROUP BY collapses rows that share the same key into one output row. Every selected column must be in the GROUP BY or inside an aggregate (COUNT, SUM, …). That rule is the usual interview gotcha. Grouping happens after WHERE. Use it to answer “per customer / per day / per category” questions.
HAVING
Filter after aggregation. WHERE vs HAVING.
HAVING filters groups after aggregation. WHERE cannot use COUNT(*) because rows are not grouped yet. Example: customers with more than 5 orders — GROUP BY customer_id HAVING COUNT(*) > 5. You can still use WHERE to drop rows before they enter a group. Interview line: WHERE filters rows, HAVING filters groups.
ORDER BY
Sort result. NULLS LAST. Multiple columns.
ORDER BY sorts the result set; without it, row order is undefined. You can sort by multiple columns (priority, then name) and choose ASC/DESC. NULLs sort first or last depending on the engine — Postgres lets you say NULLS LAST. Sorting large results is expensive; indexes that match the ORDER BY can avoid a filesort.
JOIN (SQL practice)
Write joins until they are muscle memory.
In SQL, JOIN is how you combine related tables in one query instead of looping in application code. Start from the table that defines the grain of the answer, then INNER/LEFT join lookup tables on keys. Draw the tables and the key first; then write the ON clause. Most interview SQL is “join these tables, then group.” Practice until you do not freeze on LEFT vs INNER.
Subqueries
Scalar, IN, EXISTS, correlated.
A subquery is a SELECT nested in another statement. Scalar subqueries return one value; IN / EXISTS test a set. A correlated subquery references the outer row and runs logically per row — powerful and easy to make slow. EXISTS stops at the first match; prefer it over IN when you only care about existence. Many subqueries rewrite as joins; pick the form you can still explain.
CTEs
WITH clauses for readable queries.
A CTE (WITH name AS (SELECT …)) names a subquery so the main query stays readable and you can reference it more than once. It is the same result as nesting, not a magic performance boost (Postgres can inline it). Use CTEs to break “top customers last month who also …” into steps. Recursive CTEs walk trees/graphs — know they exist; you rarely need them in a fresher round.
Window functions
ROW_NUMBER, RANK, SUM() OVER. Interview favourite.
A window function computes over related rows without collapsing them like GROUP BY. OVER (PARTITION BY … ORDER BY …) defines the window. ROW_NUMBER() unique-ranks; RANK() ties leave gaps; SUM() OVER running totals. Classic use: “latest row per user” (ROW_NUMBER = 1) and running totals. You keep every input row, with extra columns — that is the difference from GROUP BY.
Aggregations
COUNT, SUM, AVG, MIN, MAX. COUNT(*) vs COUNT(col).
Aggregates collapse many rows into one value: COUNT, SUM, AVG, MIN, MAX. COUNT(*) counts rows; COUNT(col) skips NULLs in that column — a frequent trick question. Aggregates ignore NULLs except COUNT(*). Combine with GROUP BY for per-group stats. AVG of integers may truncate depending on the engine; CAST if you need a decimal.
OSI model
Seven layers. What lives at each. Don't memorize blindly — map to real protocols.
OSI is a seven-layer teaching model: Physical, Data Link, Network, Transport, Session, Presentation, Application. Real networks run TCP/IP, so map OSI to what you actually use: IP is network, TCP/UDP transport, HTTP application. Interviewers want “which layer is IP / TCP / HTTP / Ethernet,” not a recitation of all seven names with nothing attached.
More reading
Interview questions
TCP/IP model
Four layers vs OSI. What you actually use on the internet.
TCP/IP (the Internet model) is four layers: Link, Internet (IP), Transport (TCP/UDP), Application (HTTP, DNS, …). It is what packets on the public internet actually follow. OSI Session/Presentation are folded into the application layer here. When someone says “layer 4 vs layer 7 load balancer,” they are mixing OSI numbering with this stack — L4 is TCP/UDP, L7 is HTTP.
TCP vs UDP
Reliable vs fire-and-forget. When you'd pick UDP (video, DNS).
TCP is a connection-oriented byte stream: handshake, ordered delivery, retransmission, congestion control. UDP is datagrams with no connection and no delivery guarantee — just send. Use TCP for files, HTTP, databases. Use UDP when latency matters more than a lost packet (video, games) or when the app implements retry (DNS). “Reliable” means TCP’s contract, not that the network never fails.
More reading
TCP 3-way handshake
SYN, SYN-ACK, ACK. Why three, not two.
To open a TCP connection both sides must agree on initial sequence numbers. Client sends SYN, server replies SYN-ACK, client sends ACK — three segments. Two is not enough: the last ACK proves the client received the server’s sequence number. After this, data can flow both ways. Interviewers often ask why not two-way and what a SYN flood is (half-open connections).
More reading
Interview questions
TCP connection termination
FIN/ACK four-way close. TIME_WAIT.
TCP close is four-way because each direction of the byte stream is shut down separately: FIN, ACK, FIN, ACK. TIME_WAIT keeps the closer’s port reserved so delayed packets from the old connection are not applied to a new one with the same 4-tuple. That is why you sometimes see many sockets in TIME_WAIT after a busy client. Half-close (FIN one way, still sending the other) is allowed.
More reading
HTTP
Request/response, headers, statelessness.
HTTP is a request/response protocol: method, path, headers, optional body in; status, headers, body out. The server does not remember you between requests unless you send cookies or tokens — that is “stateless.” HTTP/1.1 runs on TCP; browsers reuse connections. Know that headers are metadata (Content-Type, Authorization) and that caching/proxies reason about methods and headers.
More reading
HTTPS
HTTP over TLS. Why HTTP is not enough.
HTTPS is HTTP inside a TLS tunnel: the bytes on the wire are encrypted and authenticated, and the client checks the server’s certificate. Plain HTTP can be read or altered by anyone on the path (Wi-Fi, ISP). HTTPS does not hide that you talked to a host (SNI/DNS still leak) but it hides paths, cookies, and bodies. Port 443 vs 80 is the usual split.
More reading
HTTP methods
GET, POST, PUT, PATCH, DELETE. Idempotency.
Methods declare intent. GET reads and should be safe (no side effects) and idempotent. POST creates or triggers work and is not idempotent by default. PUT replaces a resource at a URL (idempotent). PATCH partial-updates. DELETE removes (idempotent). Idempotent means repeating the same request leaves the same server state. Interviewers use this to see if you will retry GET vs POST blindly.
More reading
HTTP status codes
2xx success, 3xx redirect, 4xx client, 5xx server. Know 200, 201, 204, 301, 400, 401, 403, 404, 409, 429, 500.
Status codes tell the client what happened. 2xx success (200 OK, 201 created, 204 no body). 3xx redirect (301 permanent). 4xx the client was wrong (400 bad request, 401 unauthenticated, 403 authenticated but forbidden, 404 missing, 409 conflict, 429 rate limit). 5xx the server failed (500). Do not return 200 with an error JSON if you can use the right class — load balancers and clients branch on the code.
More reading
DNS
Recursive vs iterative, records (A, AAAA, CNAME, MX), TTL.
DNS maps names to data: A/AAAA to IPs, CNAME to another name, MX to mail hosts. Your stub resolver asks a recursive resolver, which walks the hierarchy (root → TLD → authoritative) if the answer is not cached. TTL is how long a record may be cached — low TTL means faster updates, more queries. Without DNS, browsers would need raw IPs. Interview story: type a URL → DNS lookup before any TCP.
More reading
IP
IPv4 vs IPv6, public vs private, NAT at a high level.
IP is the internet’s addressing and routing layer. IPv4 is 32-bit addresses; IPv6 is 128-bit. Private ranges (10/8, 192.168/16, …) are not routed on the public internet; NAT lets many devices share one public IPv4 address by rewriting ports. Packets are routed hop-by-hop toward the destination IP. TCP/UDP sit on top and add ports so many apps share one host.
Ports
Well-known: 80, 443, 22, 5432. Ephemeral ports.
A port is a 16-bit number that multiplexes connections on one IP. Servers listen on well-known ports (80 HTTP, 443 HTTPS, 22 SSH, 5432 Postgres). Clients use ephemeral ports allocated by the OS for the source side of a connection. A TCP connection is a 4-tuple: src IP, src port, dst IP, dst port. Firewalls and security groups allow or deny by port.
More reading
Cookies
Set-Cookie, HttpOnly, Secure, SameSite.
Cookies are small key-value data the server sends with Set-Cookie and the browser returns on later requests to that site. HttpOnly blocks JavaScript access (helps against XSS stealing sessions). Secure sends only over HTTPS. SameSite (Lax/Strict/None) controls cross-site sending and is the main CSRF lever today. Cookies are how classic server sessions remember you on a stateless protocol.
More reading
Sessions
Server-side session vs JWT. How login actually works.
After login, the server must recognize you on the next request. A server-side session stores user id in Redis/DB and gives the browser an opaque cookie. A JWT puts claims in a signed token the client sends (often Authorization header) — the server verifies the signature and may not look up a session. Sessions are easy to revoke; JWTs need short expiry or a blocklist. “How does login work?” is cookie or token plus a secret the client cannot forge.
More reading
REST APIs
Resources, verbs, status codes, stateless servers.
REST is a style: URLs name resources (nouns), HTTP methods are the verbs, status codes report outcome, and the server stays stateless between requests. /users/42 plus GET/PATCH/DELETE is the usual shape. You do not store client conversation in server memory; you send enough in the request (auth, ids). Real APIs bend the rules; interviewers still want resource-oriented design vs one RPC dump at /api.
More reading
TLS/SSL
Certificates, handshake, why you see the padlock.
TLS (successor of SSL) encrypts a TCP connection and authenticates the server with a certificate issued by a CA the client trusts. The handshake agrees on keys; then HTTP (or other) runs inside. The padlock means “this TLS session looks valid,” not “the site is honest.” Certificate expiry and hostname mismatch are why browsers scream. HTTPS is HTTP + TLS.
More reading
What happens when you type google.com?
DNS → TCP → TLS → HTTP → render. The classic interview question.
The browser parses the URL, checks cache, then DNS-resolves google.com to an IP. It opens a TCP connection to 443, completes a TLS handshake, and sends an HTTP GET. The server responds with HTML; the browser parses it, fetches CSS/JS/images (more DNS/TCP/TLS as needed), runs JS, and paints. Mention HSTS, HTTP/2 multiplexing, and CDN anycast if you have time — the spine is DNS, TCP, TLS, HTTP, render.
More reading
Interview questions
Classes & Objects
Blueprint vs instance. Fields and methods.
A class is the blueprint: fields (state) and methods (behavior). An object is a live instance with its own field values. new Car() creates an object of type Car. Interviewers want this split before inheritance and SOLID. In Java, a class also defines a type; in JS, prototypes play a similar role.
Encapsulation
Private fields, public methods. Invariants.
Encapsulation hides internal state and exposes a small API so invariants stay true. Private fields plus public methods (getters that do not leak mutability, operations that keep balances non-negative) are the usual form. It is not “make everything private for the sake of it” — it is so callers cannot break the object’s rules. LLD interviews fail when every field is public.
Abstraction
Hide how, show what. Interfaces as contracts.
Abstraction means showing what something does, not how. A List add() contract does not mention arrays vs linked nodes. Interfaces and abstract classes are the language tools. Good abstraction lets you swap implementations (file logger vs network logger) without rewriting callers. Too much abstraction too early is also a smell — start from the real types in the problem.
Inheritance
IS-A. When it helps, when it hurts.
Inheritance is IS-A: a subclass reuses and specializes a superclass. It helps when the subtype truly is that type and you want polymorphism. It hurts when you inherit just to reuse code (fragile base class, wrong taxonomy). Prefer a shallow hierarchy. Interview contrast: inheritance vs composition — if it is HAS-A, do not extend.
Polymorphism
Same call, different behaviour. Overriding vs overloading.
Polymorphism means the same message can run different code. Runtime polymorphism is overriding: a Vehicle reference calling start() hits Car or Bike. Compile-time polymorphism is overloading: same name, different parameter types, resolved at compile time. LLD uses runtime polymorphism so you can add a new subtype without rewriting the loop that calls the interface.
Composition vs Inheritance
HAS-A is usually the better default. Favour composition.
Composition is HAS-A: a Car has an Engine. You reuse by delegating, not by extending. Inheritance couples you to the parent’s internals and lifecycle. Default to composition; inherit only for true IS-A with a stable parent. “Favour composition over inheritance” is the line interviewers want, with one example of each.
Interfaces
Multiple contracts. Default methods in Java.
An interface is a contract of methods a type must implement. A class can implement many interfaces (multiple inheritance of type, not of state). Callers depend on the interface so you can swap implementations. Java default methods add shared behavior without a class hierarchy. Use interfaces at boundaries (PaymentProvider, FeeStrategy); do not make an interface for every class.
Abstract classes
Partial implementation. When abstract class vs interface.
An abstract class can hold fields and some implemented methods, and cannot be instantiated. Subclasses fill in the abstract parts. Use it when implementations share state or a template of steps (template method). Use an interface when you only need a contract and may mix several. Java: one superclass, many interfaces — that often decides the design.
Method overloading
Compile-time polymorphism. Same name, different signature.
Overloading is several methods with the same name and different parameter lists in one class. The compiler picks which one based on the argument types. Return type alone cannot distinguish overloads. It is convenience (print(int) vs print(String)), not runtime dispatch. Do not confuse it with overriding.
More reading
Method overriding
Runtime polymorphism. @Override, super.
Overriding replaces a parent method in a subclass with the same signature. Calls on a parent-typed reference run the subclass version (virtual dispatch). @Override catches signature mistakes. super.method() calls the parent version. Access cannot be more restrictive; in Java, you cannot override static or private methods in the polymorphic sense.
SOLID principles
SRP, OCP, LSP, ISP, DIP — with one example each. Required for LLD.
SOLID is five design checks. SRP: one reason to change. OCP: add behavior by extension, not by editing a switch forever. LSP: subtypes must honor the parent contract (no Square that breaks Rectangle). ISP: small interfaces, not one fat one. DIP: depend on abstractions (FeeStrategy), not on a concrete UPI class. Quote one sentence and one example per letter in LLD rounds.
More reading
Interview questions
Exception handling
Checked vs unchecked. try/catch/finally. Don't swallow errors.
Exceptions are a control path for failures. try/catch handles them; finally (or try-with-resources) always cleans up. Java checked exceptions must be declared or caught; unchecked (RuntimeException) are for programming bugs. Do not catch and ignore — log, translate, or retry with a policy. Catch the specific type you can handle; let the rest bubble to a boundary.
Generics
Type parameters, why List<String> not raw List.
Generics parameterize types: List<String> is a list the compiler knows holds String, so you avoid casts and ClassCastException. The type parameter is erased at runtime on the JVM, which is why you cannot new T() easily. Wildcards (? extends / super) appear in APIs. Raw List is the pre-generics hole — do not use it in new code.
More reading
Collections
List, Set, Map. ArrayList vs LinkedList vs HashMap vs TreeMap.
The collections library is the default data structures: List (ordered, duplicates), Set (unique), Map (key → value). ArrayList is a resizable array — random access O(1), insert in the middle O(n). LinkedList is rarely the right default. HashMap is average O(1) get/put, unordered; TreeMap is sorted keys, O(log n). Pick by access pattern. This is asked in every Java interview and shows up in LLD as “what does this class store?”
Phase 3
Development & Projects
Two strong projects beat six CRUD clones. · 4–8 weeks
REST API
A small JSON API with CRUD for one resource (notes or todos), validation, and clear status codes.
Authentication system
Register, login, logout, protected routes. Prefer sessions or a well-understood JWT flow — and be able to explain the tradeoff.
More reading
Blog backend
Posts, authors, comments. Relational schema with foreign keys. Pagination.
More reading
Expense tracker
Categories, monthly totals, simple charts. Good first full-stack project if you also add a tiny UI.
More reading
E-commerce backend
Catalog, cart, orders, inventory decrement. Think about what happens if two people buy the last item.
More reading
Chat application
1:1 messages over WebSockets. Delivery status if you have time.
More reading
URL shortener
Create short links, redirect, click counts. Unique codes. This also prepares you for the HLD version.
More reading
Job portal
Job listings, apply, search/filter. Roles: candidate vs recruiter.
More reading
Notification system
Queue an event, send email or in-app notification. Retry on failure.
More reading
Scalable URL shortener
Same product as the intermediate shortener, plus caching, unique ID generation, and a write-up of how it would scale.
More reading
Real-time chat system
Rooms, presence, reconnect. Document how you'd shard connections later.
More reading
Distributed notification system
Multiple channels (email, push, in-app), a worker pool, dead-letter queue.
More reading
Social media backend
Follow graph, feed of posts. Start with pull-based feed. Write the fan-out vs pull tradeoff.
Video streaming platform
Upload metadata + playback URL. You do not need to build a real CDN. Explain chunking and CDN in the README.
More reading
Phase 4
Low Level Design
Class design and patterns. Practice before you read solutions. · 3–4 weeks
Parking Lot
Multi-floor lot, vehicle types, nearest slot, ticket + fee.
A parking-lot LLD is an object model for floors, slots, vehicles, tickets, and fees — not a database schema. You assign a free slot (often nearest), issue a ticket on entry, and compute a fee on exit by vehicle type. Strategy fits pricing; do not bury vehicle rules in a giant switch on the lot. The interview is class boundaries and relationships, then a simple assign/exit flow.
Requirements
- Multiple floors and slot sizes
- Bike / Car / Truck
- Issue ticket on entry, fee on exit
Classes to identify
- ParkingLot
- Floor
- Slot
- Vehicle
- Ticket
- FeeStrategy
Relationships. Lot has Floors; Floor has Slots; Ticket references Vehicle and Slot.
Patterns
- Strategy (pricing)
- Singleton (lot, optional)
Practice prompt. Design a parking lot that assigns the nearest free slot and computes fees by vehicle type. Do not look at a full solution until you have a class diagram.
More reading
Elevator
Requests from halls and cabins, direction, multiple elevators.
An elevator system takes hall and cabin requests and moves cars without randomly reversing mid-trip. State (idle, moving up/down, maintenance) plus a dispatch strategy for multiple cars is the usual design. Start with one car and SCAN-like direction, then add a controller that assigns requests. The hard part is request queues and direction, not drawing cables.
Requirements
- Up/down requests
- Do not reverse mid-trip without a reason
- Optional: multiple cars
Classes to identify
- Elevator
- ElevatorController
- Request
- Direction
- Door
Relationships. Controller assigns Request to an Elevator.
Patterns
- State (moving/idle/maintenance)
- Strategy (dispatch)
Practice prompt. Design an elevator controller. Start with one car, then extend to a bank of elevators.
More reading
Tic Tac Toe
Board, players, win/draw detection, optional undo.
Tic-tac-toe is a Game that owns a Board and Players and applies Moves. Win detection should run from the last move (row/col/diag), not a full scan every time if you can avoid it. Design the board so N×N / K-in-a-row is a parameter, not a rewrite. Optional undo is a stack of moves. Keep UI out of the domain objects.
Requirements
- 3x3 then NxN
- Detect win on last move
- Two players
Classes to identify
- Board
- Player
- Game
- Move
Relationships. Game has Board and Players; Move updates Board.
Patterns
- Strategy (if you add bots)
Practice prompt. Implement a tic-tac-toe game that can later become N-in-a-row without rewriting everything.
More reading
Snake & Ladder
Board with snakes/ladders, dice, multiple players, win condition.
Snake and ladder is a turn-based Game: roll dice, move a Player along a Board, then jump if the cell is a snake or ladder. The board is data (start → end map), not if (position == 14). Decide exact-win vs bounce at the end. Multiple players are a list and a turn index. No design pattern is required — clear OOP is the bar.
Requirements
- Configurable snakes and ladders
- Turn-based players
- Exact win or bounce
Classes to identify
- Board
- Cell
- Dice
- Player
- Game
Relationships. Board maps start→end for snakes/ladders; Game moves Player.
Patterns
- None required — clean OOP first
Practice prompt. Model the board as data, not a giant if-else of snake positions.
Library Management
Search, borrow, return, fines, librarian vs member.
A library LLD separates Book (ISBN, title) from BookItem (physical copy with barcode). Members borrow items via Loans with due dates and fines; a Catalog searches by title/author/ISBN. Librarian vs member is a role, not a second copy of the whole model. The trap is treating every copy as the same Book object so you cannot track who has which copy.
Requirements
- Search by title/author/ISBN
- Borrow limits
- Due dates and fines
Classes to identify
- Library
- Book
- BookItem
- Member
- Loan
- Catalog
Relationships. Book has many BookItems; Loan ties Member to BookItem.
Patterns
- Singleton (catalog, optional)
Practice prompt. Separate Book (ISBN) from BookItem (physical copy).
More reading
Splitwise
Equal/exact/percent splits, balances, simplify debts.
Splitwise records an Expense paid by someone and Split among users (equal, exact, percent — Strategy). A BalanceSheet stores how much A owes B after many expenses. Get pairwise balances right before “simplify debts” (min cash-flow). Do not start from the graph algorithm; start from User, Expense, Split, and an invariant that splits sum to the total.
Requirements
- Equal, exact, percent splits
- Show balances
- Optional: simplify debts
Classes to identify
- User
- Expense
- Split
- BalanceSheet
Relationships. Expense has Splits; BalanceSheet aggregates User pairs.
Patterns
- Strategy (split types)
Practice prompt. Do not start with the simplify-debts algorithm. Get balances right first.
Vending Machine
Select item, insert money, dispense, return change. Invalid states.
A vending machine is a State machine: idle, has money, dispensing, sold out, cancelled. Each action (insert coin, select, refund) is valid in some states only — that is the State pattern. Inventory holds items and prices; change is computed on success. The interview is “you cannot dispense with no money” encoded in types/states, not a pile of booleans.
Requirements
- Idle → has money → dispense
- Cancel and refund
- Sold out
Classes to identify
- VendingMachine
- Inventory
- Item
- Money
- State
Relationships. Machine has Inventory and current State.
Patterns
- State
Practice prompt. Use the State pattern so each action is valid only in some states.
More reading
ATM
Card, PIN, withdraw, balance, cash dispenser.
An ATM session authenticates a card (PIN via a BankService you mock), then withdraws or shows balance. CashDispenser hands out notes (often chain of denomination handlers). Treat the bank as an interface — the machine should not own accounts. State covers idle → card in → authenticated → eject. Cancel and errors must eject the card; that is part of the model.
Requirements
- Authenticate
- Withdraw with denomination mix
- Eject card on cancel/error
Classes to identify
- ATM
- CardReader
- CashDispenser
- BankService
- Session
Relationships. ATM talks to BankService; Session holds authenticated Card.
Patterns
- State
- Chain of Responsibility (dispenser)
Practice prompt. Treat the bank as an interface. You should be able to mock it in tests.
More reading
Car Rental
Search cars, reserve, pickup/return, pricing, overlapping bookings.
Car rental is inventory of Vehicles at a Store plus Reservations that block a vehicle for a date range. The hard invariant is no overlapping bookings for the same car. Pricing is a Strategy by vehicle type or duration. User, Reservation, Bill are separate from the vehicle catalog. Model the interval explicitly; do not hope two bookings “probably” do not clash.
Requirements
- Inventory by location
- No double booking
- Pricing by vehicle type
Classes to identify
- Store
- Vehicle
- Reservation
- User
- Bill
Relationships. Store has Vehicles; Reservation blocks a Vehicle for a date range.
Patterns
- Strategy (pricing)
Practice prompt. The hard part is overlapping date ranges. Model that explicitly.
More reading
Movie Ticket Booking
Shows, seats, hold/lock, payment, concurrency.
Movie booking is Theatre → Screen → Show → Seats, plus a Booking that holds seats until payment or timeout. Two users must not confirm the same seat — that is the interview (lock/hold with expiry, then confirm). Pricing and payment are supporting pieces. Design the seat lock before UI. Concurrency is the problem; a class diagram without locks is incomplete.
Requirements
- Browse shows
- Hold seats for a few minutes
- Confirm after payment
Classes to identify
- Theatre
- Screen
- Show
- Seat
- Booking
- Payment
Relationships. Show has Seats; Booking holds Seats until paid or expired.
Patterns
- Strategy (pricing)
- State (seat)
Practice prompt. Design the seat lock before you design the UI. Concurrency is the interview.
Chess
Pieces with different moves, turn taking, check/checkmate (keep scope honest).
Chess LLD is a Board of Pieces where each piece type implements its own legal moves (polymorphism/Strategy), plus turn taking. Do not build an engine or full checkmate search unless asked. Optional check detection is “does this move leave the king in attack.” Scope honestly: object model and move API, not Stockfish.
Requirements
- Legal moves per piece
- Turn order
- Optional: check detection
Classes to identify
- Board
- Piece
- Move
- Game
- Player
Relationships. Board holds Pieces; each Piece implements move rules.
Patterns
- Strategy / polymorphism for piece moves
Practice prompt. Do not implement a chess engine. Get the object model and legal-move API right.
More reading
Logger
Levels, multiple appenders, formatters. Chain of handlers.
A logger accepts a LogRecord (level + message), formats it, and fans out to Appenders (console, file). Levels filter; you add an appender without editing Logger (OCP). Chain of Responsibility or a list of appenders both work; Observer is the same idea. Singleton is optional and often overused. The test is: new destination, no rewrite of the log() method.
Requirements
- DEBUG/INFO/WARN/ERROR
- Console and file appenders
- Configurable format
Classes to identify
- Logger
- LogRecord
- Appender
- Formatter
Relationships. Logger fans out LogRecords to Appenders.
Patterns
- Chain of Responsibility
- Singleton (optional)
- Observer
Practice prompt. You should be able to add a new appender without changing Logger.
More reading
Phase 5
High Level Design
Fresher-level system design. Concepts first, then five classic systems. · 2–3 weeks
Client-server architecture
Browser/app talks to an API. Stateless servers. Why this is the default.
Client-server means the client (browser, app) sends requests to a server that owns data and business rules. Stateless servers do not remember you between HTTP requests — session lives in a cookie, token, or store. That is the default because you can add identical instances behind a load balancer. The alternative is sticky in-memory session, which makes scaling and failover harder.
Requirements
- One-sentence definition
- Where state lives
More reading
Load balancing
Spread traffic across instances. L4 vs L7 at a high level.
A load balancer sits in front of many app instances and spreads requests so no single box is the bottleneck and you can take instances down. L4 (TCP) balances connections; L7 (HTTP) can route on path or host. Health checks drop dead backends. Round-robin, least-connections, and consistent hashing are the usual policies. Without an LB, “add another server” has nowhere to send traffic.
More reading
Horizontal vs vertical scaling
Bigger machine vs more machines. Where each hits a wall.
Vertical scaling is a bigger machine (more CPU/RAM) — simple, hits a hardware ceiling, and is a single point of failure. Horizontal scaling is more machines behind a balancer — needs stateless apps and shared data stores. Freshers should say: scale out the web tier first; databases scale out later (replicas, then shards) because data has gravity. Cost and failure domains differ, not just “faster.”
More reading
Caching
What to cache, TTL, cache stampede, where (CDN, Redis, app).
A cache stores a computed or fetched result so the next read is cheaper. Put it at the CDN (static), Redis (shared hot keys), or in-process (fast, not shared). TTL and invalidation decide staleness. Cache stampede is many misses hitting the DB at once when a key expires — mitigate with lock, slightly random TTL, or serving stale. Cache what is read often and expensive; do not cache what must be correct to the millisecond unless you have a plan.
More reading
Redis
In-memory store. Cache, sessions, rate limits, simple queues.
Redis is an in-memory key-value store with useful types (strings, hashes, lists, sorted sets) and optional persistence. Typical uses: cache, session store, rate-limit counters, leaderboards, simple queues. It is not your system of record for money unless you design durability on purpose. Interview sentence: “hot path reads go to Redis; source of truth stays in Postgres.”
More reading
Database indexing
Same idea as DBMS indexes, now in a system-design sentence: reads vs writes.
In HLD, indexes are how you keep reads fast as tables grow: you design access patterns (lookup by user_id, time range) and add indexes to match. Every index slows writes and uses disk. “We’ll shard” is the wrong first answer to a slow query — check the query and the index. Say which column you index and why, not “we add indexes.”
More reading
SQL vs NoSQL
Joins and transactions vs flexible scale. Pick based on access patterns, not hype.
SQL (Postgres/MySQL) gives schemas, joins, and ACID transactions — default for user accounts, orders, money. NoSQL (document, key-value, wide column) trades some of that for flexible documents or easier horizontal scale on simple access patterns. Pick from how you query and whether you need multi-row transactions, not from trend. Many systems use SQL plus Redis, not “NoSQL because scale.”
More reading
Replication
Primary + replicas. Read scaling. Failover at a high level.
Replication copies data from a primary to replicas. Reads can go to replicas; writes go to the primary (typical). Failover promotes a replica if the primary dies — there is a window of possible data loss with async replication. Replicas lag; stale reads are the tradeoff for read scale. This is how you scale reads before sharding.
More reading
Sharding
Split data by key. Hot partitions. Why you postpone this as a fresher.
Sharding splits a dataset across machines by a key (user_id % N, hash ranges). Each shard is a smaller database. Cross-shard joins and transactions get hard; a hot key (celebrity user) overloads one shard. Freshers should postpone sharding: indexes, caching, and replicas usually come first. If you shard, say the key and how you avoid hotspots.
More reading
Message queues
Decouple producers and consumers. Buffer spikes. At-least-once delivery.
A queue sits between a producer and workers: the API enqueues “send email” and returns; workers consume at their pace. That decouples spikes from slow I/O and lets you retry. Most queues are at-least-once — design consumers to be idempotent. Use a queue when work can be async; do not queue the user’s login response.
More reading
Kafka
Log of events, consumer groups. Enough to say why it's used, not how to operate a cluster.
Kafka is a durable, ordered log of events partitioned by key. Producers append; consumer groups share partitions so each message is processed by one consumer in the group, and you can replay. It is for high-throughput event streams and multiple independent consumers, not a simple job queue (though people use it that way). As a fresher, say “append-only log, replay, fan-out” — not broker tuning.
More reading
CDN
Cache static assets close to users.
A CDN caches static files (JS, CSS, images, video segments) on edge servers near users so origin is barely hit. TTL and cache keys matter; HTML is often shorter-lived than hashed assets. YouTube/Netflix HLD is mostly CDN + object storage. Dynamic API calls still go to your region unless you add more machinery. Interview line: put the CDN in front of blobs, not as a magic DB.
More reading
Rate limiting
Token bucket / sliding window at a high level. Protect APIs.
Rate limiting caps how many requests a client (IP, user, API key) can make in a window so one caller cannot exhaust the API. Token bucket allows short bursts; sliding window is smoother than fixed windows. Redis is the usual shared counter. Return 429. Place it at the gateway. It is protection, not a substitute for horizontal scale.
More reading
CAP theorem
Partition happens. You trade consistency vs availability. Don't over-apply it.
CAP says if the network partitions, a distributed store cannot be both fully consistent and fully available — you choose. Most interview answers over-apply it to a single Postgres. Use it when you have replicas across failure domains and must say whether you serve stale data or error. PACELC (latency vs consistency when the network is fine) is the honest extra. Do not recite CAP as the design.
More reading
Consistency
Strong vs eventual. What the user sees after a write.
Consistency here is what a read returns after a write. Strong: the next read (in the agreed scope) sees the write. Eventual: replicas catch up; a read might be stale for a while. Users notice this as “I liked the post but the count didn’t move.” Pick strong for money and inventory; eventual is fine for counts and feeds if you say the lag. Isolation levels in one DB are a related but different topic.
More reading
Availability
Uptime, redundancy, health checks. nines as a talking point, not a religion.
Availability is the fraction of time the system successfully serves requests. You buy it with redundancy (multi-AZ, replicas, load balancers) and health checks that stop sending traffic to dead boxes. “Three nines” is ~8 hours down per year — a talking point, not a design. Single primary DB without failover is the usual fresher hole. Measure user-facing success, not just process uptime.
More reading
Reliability
Retries, timeouts, idempotency. Things fail; your design should expect it.
Reliability is behaving correctly under failure: networks drop, timeouts fire, workers crash mid-job. Timeouts bound waits; retries with backoff handle blips; idempotency keys make retries safe. At-least-once delivery plus idempotent consumers is the standard story. A design that assumes every RPC succeeds is not a design. This is more useful in a fresher HLD than naming six new databases.
More reading
URL Shortener
Create short links, redirect, analytics. The default fresher HLD question.
A URL shortener maps a short code to a long URL: POST creates the mapping, GET redirects (301/302). The read path is extremely hot, so cache codes in Redis and generate unique IDs (hash or ticket server) without collisions. Analytics are optional counters. Do not start with sharding; a single DB plus cache handles a lot. This is the default fresher HLD because it is small and still has IDs, cache, and redirects.
Requirements
- Create short URL
- Redirect 301/302
- Optional click counts
Components
- API
- DB for mappings
- Cache for hot keys
- unique ID generator
Data flow. Client → API → write mapping → on GET, lookup cache then DB → 302.
Scaling. Cache reads. Hash or ticket IDs. Don't start with sharding.
Twitter / Instagram Feed
Follow graph + timeline. Fan-out on write vs read.
A social feed is posts plus a follow graph and a home timeline. Fan-out on write pushes a post into each follower’s cache (fast read, painful for celebrities). Fan-out on read pulls from followees at read time (cheap write, slow read). Hybrid (fan-out normal users, pull celebrities) is the honest answer. Storage of posts is separate from the precomputed timeline cache.
Requirements
- Post
- Follow
- Home timeline
Components
- User service
- Post service
- Fan-out / timeline cache
Data flow. Publish post → store → push to followers' caches or pull at read time.
Scaling. Celebrities break fan-out-on-write. Hybrid is the honest answer.
1:1 messages, delivery receipts, online status. Connection-heavy.
Chat is connection-heavy: clients keep a long-lived connection (WebSocket) to a gateway so messages push instantly. If the recipient is offline, store and deliver later. Presence (online/last seen) is a separate service with TTLs. Delivery receipts are extra events. Do not design full E2E encryption unless asked. The bottleneck is millions of open connections, not SQL for every message fan-out.
Requirements
- Send/receive
- Online/offline
- Last seen optional
Components
- Gateway (WebSocket)
- Message store
- Presence service
Data flow. Client keeps a long-lived connection. Messages queued if recipient is offline.
Scaling. Sticky sessions or a connection registry. Don't design end-to-end encryption unless asked.
YouTube
Upload, process, playback. CDN is the star.
Video HLD is upload to object storage, async transcoding into renditions, then playback almost entirely from a CDN. Metadata (title, owner) lives in a DB; bytes do not. Thumbnails are another derived asset. Almost no watch traffic should hit origin. Upload is a write path with a queue; watch is a cache path. That split is the design.
Requirements
- Upload
- Watch
- Thumbnails
Components
- Upload API
- Object storage
- Transcoding workers
- CDN
Data flow. Upload → store original → workers emit renditions → CDN serves playback.
Scaling. Almost all watch traffic should never hit origin.
More reading
Notification System
Events in, notifications out. Email/push/in-app. Retries.
A notification system takes domain events (order shipped) and fans out to channels (email, push, in-app) according to user preferences. The API enqueues; workers call providers; failures retry then dead-letter. Idempotency avoids double SMS. The queue absorbs spikes so checkout does not wait on Gmail. Scale workers independently of the request path.
Requirements
- Fan-out to channels
- User preferences
- At-least-once with idempotency
Components
- API
- Queue
- Workers per channel
- Preference store
Data flow. Event → queue → worker → provider. Failed jobs retry then dead-letter.
Scaling. Queue absorbs spikes. Workers scale independently of the API.
More reading
Phase 6
Interview Preparation
DSA, CS, project deep-dives, and behavioral stories. · ongoing
DSA interview patterns
Arrays, trees, graphs, DP, binary search, sliding window — spoken out loud.
CS fundamentals interview
OS, DBMS, CN, OOP questions you should answer in 60–90 seconds.
Project interview
Defend architecture, database, and 10x traffic without freezing.
More reading
Behavioral interview
STAR stories: yourself, conflict, failure, leadership, proud project.