Sign-in isn't set up on this site yet. Your progress is still being
saved in this browser (localStorage) — it just won't sync across
devices until the site owner finishes the Firebase setup.
or
Interview Prep
DSA Patterns · Code Templates · LeetCode
A structured reference for coding interviews. Each topic explains the underlying pattern and a reusable template — so problems become recognition exercises, not memory tests.
18
Topics
~165
Problems
0
Solved
How to use
Read the pattern — understand the core technique and when to apply it
Study the code template until you can write it cold; use the copy button
Work through problems in order (Easy → Hard) and check them off as you go
Press / to focus
DIFFICULTY:
0 / 0 solved
No matches found.
Arrays & Strings
The Pattern
Most array/string problems reduce to one of four shapes: prefix sums (range queries in O(1)), Kadane's algorithm (max-sum subarray), in-place two-pass (extra space → O(1)), or frequency counting. Recognise the shape first.
Reach for this when: the problem mentions a contiguous subarray/substring, a running total or range sum, a "maximum/minimum subarray", or asks you to modify an array without extra space.
Template — Prefix Sum
# Build prefix sums → range sum query in O(1)
prefix = [0] * (len(arr) + 1)
for i, v in enumerate(arr):
prefix[i + 1] = prefix[i] + v
# sum of arr[l..r] (0-indexed, inclusive)
def range_sum(l, r):
return prefix[r + 1] - prefix[l]
// Build prefix sums -> range sum query in O(1)
int[] prefix = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
prefix[i + 1] = prefix[i] + arr[i];
}
// sum of arr[l..r] (0-indexed, inclusive)
int rangeSum(int l, int r) {
return prefix[r + 1] - prefix[l];
}
// Build prefix sums -> range sum query in O(1)
int[] prefix = new int[arr.Length + 1];
for (int i = 0; i < arr.Length; i++) {
prefix[i + 1] = prefix[i] + arr[i];
}
// sum of arr[l..r] (0-indexed, inclusive)
int RangeSum(int l, int r) {
return prefix[r + 1] - prefix[l];
}
Template — Kadane's (Max Subarray)
max_sum = cur_sum = arr[0]
for num in arr[1:]:
cur_sum = max(num, cur_sum + num) # restart or extend
max_sum = max(max_sum, cur_sum)
# max_sum holds the answer
int maxSum = arr[0], curSum = arr[0];
for (int i = 1; i < arr.length; i++) {
curSum = Math.max(arr[i], curSum + arr[i]); // restart or extend
maxSum = Math.max(maxSum, curSum);
}
// maxSum holds the answer
int maxSum = arr[0], curSum = arr[0];
for (int i = 1; i < arr.Length; i++) {
curSum = Math.Max(arr[i], curSum + arr[i]); // restart or extend
maxSum = Math.Max(maxSum, curSum);
}
// maxSum holds the answer
Two pointers eliminate a nested loop. On a sorted array, a meet-in-the-middle pair (left=0, right=n−1) finds pairs/triplets in O(n). A fast-slow pair (both moving right) partitions the array in-place without extra space.
Reach for this when: the input is sorted (or can be sorted without breaking the answer), you need to find pairs/triplets summing to a target, remove/move elements in-place, or check palindrome-like properties.
Template — Meet in the Middle
left, right = 0, len(arr) - 1
while left < right:
s = arr[left] + arr[right]
if s == target:
# found a pair
left += 1; right -= 1
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
int left = 0, right = arr.length - 1;
while (left < right) {
int s = arr[left] + arr[right];
if (s == target) {
// found a pair
left++; right--;
} else if (s < target) {
left++; // need larger sum
} else {
right--; // need smaller sum
}
}
int left = 0, right = arr.Length - 1;
while (left < right) {
int s = arr[left] + arr[right];
if (s == target) {
// found a pair
left++; right--;
} else if (s < target) {
left++; // need larger sum
} else {
right--; // need smaller sum
}
}
Template — Fast / Slow (in-place partition)
slow = 0 # next write position
for fast in range(len(arr)):
if keep(arr[fast]): # your condition here
arr[slow] = arr[fast]
slow += 1
# arr[:slow] is the filtered result
int slow = 0; // next write position
for (int fast = 0; fast < arr.length; fast++) {
if (keep(arr[fast])) { // your condition here
arr[slow] = arr[fast];
slow++;
}
}
// arr[0..slow) is the filtered result
int slow = 0; // next write position
for (int fast = 0; fast < arr.Length; fast++) {
if (Keep(arr[fast])) { // your condition here
arr[slow] = arr[fast];
slow++;
}
}
// arr[0..slow) is the filtered result
Template — 3Sum (sort + two-pointer for each pivot)
nums.sort()
result = []
for i, pivot in enumerate(nums):
if i > 0 and nums[i] == nums[i-1]: continue # skip dup pivots
l, r = i + 1, len(nums) - 1
while l < r:
s = pivot + nums[l] + nums[r]
if s < 0: l += 1
elif s > 0: r -= 1
else:
result.append([pivot, nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]: l += 1
while l < r and nums[r] == nums[r-1]: r -= 1
l += 1; r -= 1
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // skip dup pivots
int l = i + 1, r = nums.length - 1;
while (l < r) {
int s = nums[i] + nums[l] + nums[r];
if (s < 0) l++;
else if (s > 0) r--;
else {
result.add(Arrays.asList(nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++; r--;
}
}
}
Array.Sort(nums);
var result = new List<List<int>>();
for (int i = 0; i < nums.Length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // skip dup pivots
int l = i + 1, r = nums.Length - 1;
while (l < r) {
int s = nums[i] + nums[l] + nums[r];
if (s < 0) l++;
else if (s > 0) r--;
else {
result.Add(new List<int> { nums[i], nums[l], nums[r] });
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++; r--;
}
}
}
Maintain a window [left, right] over the array. Expand right greedily; shrink left only when the window violates the constraint. The key question to ask yourself: "what makes a window valid, and how do I check it in O(1)?" Usually the answer is a counter or a hash map.
Reach for this when: the problem asks for the longest/shortest contiguous subarray or substring satisfying a constraint. If window size is fixed, it's a simpler rolling sum. If variable, use the expand-shrink template.
Template — Variable Window
from collections import defaultdict
left = 0
window = defaultdict(int) # or a Counter / set
result = 0
for right in range(len(s)):
window[s[right]] += 1 # expand: include s[right]
while not valid(window): # shrink until valid
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
left += 1
result = max(result, right - left + 1) # window size
Map<Character, Integer> window = new HashMap<>();
int left = 0, result = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
window.merge(c, 1, Integer::sum); // expand: include s[right]
while (!valid(window)) { // shrink until valid
char lc = s.charAt(left);
window.merge(lc, -1, Integer::sum);
if (window.get(lc) == 0) window.remove(lc);
left++;
}
result = Math.max(result, right - left + 1); // window size
}
var window = new Dictionary<char, int>();
int left = 0, result = 0;
for (int right = 0; right < s.Length; right++) {
char c = s[right];
window[c] = window.GetValueOrDefault(c) + 1; // expand: include s[right]
while (!Valid(window)) { // shrink until valid
char lc = s[left];
window[lc]--;
if (window[lc] == 0) window.Remove(lc);
left++;
}
result = Math.Max(result, right - left + 1); // window size
}
Template — Fixed Window (size k)
k = ...
window_sum = sum(arr[:k])
best = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k] # slide
best = max(best, window_sum)
int k = ...;
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int best = windowSum;
for (int i = k; i < arr.length; i++) {
windowSum += arr[i] - arr[i - k]; // slide
best = Math.max(best, windowSum);
}
int k = ...;
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int best = windowSum;
for (int i = k; i < arr.Length; i++) {
windowSum += arr[i] - arr[i - k]; // slide
best = Math.Max(best, windowSum);
}
Key trick — "at most K distinct" → longest window with ≤ K distinct
# Many hard window problems decompose:
# "exactly K" = f(at most K) - f(at most K-1)
Time: O(n) — each element enters/leaves onceSpace: O(k) window state
Linked list problems almost always reduce to one of three techniques: reversal with prev/curr pointers, a dummy head node to simplify edge cases at the head, and a two-pointer runner (e.g., move one pointer k steps ahead to find the kth-from-end node). Always draw the pointer reassignment order before coding — getting it backwards causes off-by-one bugs that are hard to debug.
Reach for this when: you see "reverse", "merge sorted lists", "remove nth from end", "reorder", "add two numbers", or "palindrome linked list". For cycle problems, use Fast & Slow Pointers instead.
Template — Iterative Reversal
def reverse_list(head):
prev, curr = None, head
while curr:
nxt = curr.next # save next
curr.next = prev # reverse the link
prev = curr # advance prev
curr = nxt # advance curr
return prev # new head
ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode nxt = curr.next; // save next
curr.next = prev; // reverse the link
prev = curr; // advance prev
curr = nxt; // advance curr
}
return prev; // new head
}
ListNode ReverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode nxt = curr.next; // save next
curr.next = prev; // reverse the link
prev = curr; // advance prev
curr = nxt; // advance curr
}
return prev; // new head
}
Template — Dummy Head (merge / remove)
def merge_two_lists(l1, l2):
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next, l1 = l1, l1.next
else:
cur.next, l2 = l2, l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
def remove_nth_from_end(head, n):
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n + 1): # advance fast n+1 steps
fast = fast.next
while fast: # move both until fast hits end
fast = fast.next
slow = slow.next
slow.next = slow.next.next # skip the target node
return dummy.next
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode fast = dummy, slow = dummy;
for (int i = 0; i < n + 1; i++) { // advance fast n+1 steps
fast = fast.next;
}
while (fast != null) { // move both until fast hits end
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next; // skip the target node
return dummy.next;
}
ListNode RemoveNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode fast = dummy, slow = dummy;
for (int i = 0; i < n + 1; i++) { // advance fast n+1 steps
fast = fast.next;
}
while (fast != null) { // move both until fast hits end
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next; // skip the target node
return dummy.next;
}
Two pointers advance at different speeds through the same structure. The fast pointer moves 2 steps per iteration; the slow moves 1. If a cycle exists, they must eventually meet — the fast pointer laps the slow one inside the loop. If no cycle, fast reaches null first.
This works on any structure where you can follow a "next" link, including arrays used as implicit linked lists (e.g., 287. Find the Duplicate, where index → value forms a linked list).
Reach for this when: you see "detect cycle", "find cycle entry", "find middle of linked list", "happy number", or any problem where following a chain of values could loop.
Template — Cycle Detection
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True # cycle detected
return False
Template — Find Cycle Entry (Linked List Cycle II)
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
# Reset one pointer to head; advance both at speed 1.
# They meet at the cycle entry.
slow = head
while slow is not fast:
slow, fast = slow.next, fast.next
return slow
return None
ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// Reset one pointer to head; advance both at speed 1.
// They meet at the cycle entry.
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
ListNode DetectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// Reset one pointer to head; advance both at speed 1.
// They meet at the cycle entry.
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
Template — Find Middle
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second middle
ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // for even length, returns second middle
}
ListNode MiddleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // for even length, returns second middle
}
Hash maps trade O(n) extra space for O(1) lookup, turning brute-force O(n²) into O(n). Three main uses: complement lookup (two-sum style), frequency counting (anagram/top-K), and canonical grouping (group anagrams). For existence checks alone, a set is enough.
Reach for this when: you need to find a pair, detect a duplicate, count frequencies, or group items by some property — and O(n²) is too slow.
Template — Complement Lookup
seen = {} # val → index
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
Map<Integer, Integer> seen = new HashMap<>(); // val -> index
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (seen.containsKey(complement)) {
return new int[]{seen.get(complement), i};
}
seen.put(nums[i], i);
}
var seen = new Dictionary<int, int>(); // val -> index
for (int i = 0; i < nums.Length; i++) {
int complement = target - nums[i];
if (seen.ContainsKey(complement)) {
return new int[] { seen[complement], i };
}
seen[nums[i]] = i;
}
Template — Frequency / Top-K
from collections import Counter
freq = Counter(nums)
# bucket sort for O(n) top-K (beats heap when k ~ n)
buckets = [[] for _ in range(len(nums) + 1)]
for val, cnt in freq.items():
buckets[cnt].append(val)
result = []
for cnt in range(len(buckets) - 1, 0, -1):
result.extend(buckets[cnt])
if len(result) >= k:
return result[:k]
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);
// bucket sort for O(n) top-K (beats heap when k ~ n)
List<Integer>[] buckets = new List[nums.length + 1];
for (int i = 0; i <= nums.length; i++) buckets[i] = new ArrayList<>();
for (var entry : freq.entrySet()) {
buckets[entry.getValue()].add(entry.getKey());
}
List<Integer> result = new ArrayList<>();
for (int cnt = buckets.length - 1; cnt > 0 && result.size() < k; cnt--) {
result.addAll(buckets[cnt]);
}
return result.subList(0, k);
var freq = new Dictionary<int, int>();
foreach (var n in nums) freq[n] = freq.GetValueOrDefault(n) + 1;
// bucket sort for O(n) top-K (beats heap when k ~ n)
var buckets = new List<int>[nums.Length + 1];
for (int i = 0; i <= nums.Length; i++) buckets[i] = new List<int>();
foreach (var kv in freq) buckets[kv.Value].Add(kv.Key);
var result = new List<int>();
for (int cnt = buckets.Length - 1; cnt > 0 && result.Count < k; cnt--) {
result.AddRange(buckets[cnt]);
}
return result.Take(k).ToList();
Template — Canonical Grouping
from collections import defaultdict
groups = defaultdict(list)
for word in words:
key = tuple(sorted(word)) # canonical form
groups[key].append(word)
return list(groups.values())
Map<String, List<String>> groups = new HashMap<>();
for (String word : words) {
char[] chars = word.toCharArray();
Arrays.sort(chars);
String key = new String(chars); // canonical form
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
}
return new ArrayList<>(groups.values());
var groups = new Dictionary<string, List<string>>();
foreach (var word in words) {
var chars = word.ToCharArray();
Array.Sort(chars);
string key = new string(chars); // canonical form
if (!groups.ContainsKey(key)) groups[key] = new List<string>();
groups[key].Add(word);
}
return groups.Values.ToList();
A stack is useful whenever you need to undo or match something recently seen (parentheses, function calls). The power move is the monotonic stack: maintain a stack that is always increasing (or decreasing). When a new element breaks monotonicity, pop and process — this gives you "next greater/smaller element" in O(n).
Reach for this when: you see nested/matching structure (brackets, HTML tags), need the "next greater/smaller element" for each position, or need to compute span/histogram areas.
Template — Balanced Brackets
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in '([{':
stack.append(ch)
elif not stack or stack[-1] != pairs[ch]:
return False
else:
stack.pop()
return not stack
var pairs = new Dictionary<char, char> { [')'] = '(', [']'] = '[', ['}'] = '{' };
var stack = new Stack<char>();
foreach (char ch in s) {
if (ch == '(' || ch == '[' || ch == '{') {
stack.Push(ch);
} else if (stack.Count == 0 || stack.Peek() != pairs[ch]) {
return false;
} else {
stack.Pop();
}
}
return stack.Count == 0;
Template — Monotonic Stack (Next Greater Element)
result = [-1] * len(arr)
stack = [] # stores indices, arr is decreasing from bottom→top
for i in range(len(arr)):
# arr[i] is greater than everything under it → pop and resolve
while stack and arr[stack[-1]] < arr[i]:
result[stack.pop()] = arr[i]
stack.append(i)
# remaining indices in stack have no greater element → result stays -1
int[] result = new int[arr.length];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // stores indices, arr is decreasing from bottom->top
for (int i = 0; i < arr.length; i++) {
// arr[i] is greater than everything under it -> pop and resolve
while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
result[stack.pop()] = arr[i];
}
stack.push(i);
}
// remaining indices in stack have no greater element -> result stays -1
var result = new int[arr.Length];
Array.Fill(result, -1);
var stack = new Stack<int>(); // stores indices, arr is decreasing from bottom->top
for (int i = 0; i < arr.Length; i++) {
// arr[i] is greater than everything under it -> pop and resolve
while (stack.Count > 0 && arr[stack.Peek()] < arr[i]) {
result[stack.Pop()] = arr[i];
}
stack.Push(i);
}
// remaining indices in stack have no greater element -> result stays -1
Template — Two Stacks = Queue
inbox, outbox = [], []
def push(x): inbox.append(x)
def pop():
if not outbox: # amortised O(1)
while inbox:
outbox.append(inbox.pop())
return outbox.pop()
Deque<Integer> inbox = new ArrayDeque<>(), outbox = new ArrayDeque<>();
void push(int x) { inbox.push(x); }
int pop() {
if (outbox.isEmpty()) { // amortised O(1)
while (!inbox.isEmpty()) outbox.push(inbox.pop());
}
return outbox.pop();
}
var inbox = new Stack<int>();
var outbox = new Stack<int>();
void Push(int x) { inbox.Push(x); }
int Pop() {
if (outbox.Count == 0) { // amortised O(1)
while (inbox.Count > 0) outbox.Push(inbox.Pop());
}
return outbox.Pop();
}
Time: O(n) amortised (each element pushed/popped once)Space: O(n)
Sort intervals by start time. Then iterate: if the current interval's start is ≤ the previous interval's end, they overlap — merge by extending the end to max(prev.end, curr.end). Otherwise push the previous interval and start fresh with the current one.
A common variant is "how many rooms are needed?" — sort start and end times into separate arrays and use a two-pointer sweep to count concurrent overlaps.
Reach for this when: the input is a list of intervals and the problem asks to merge, count overlaps, find gaps, remove minimum, or find intersections. Dead giveaway words: "meeting rooms", "overlapping", "insert interval", "minimum arrows".
Template — Merge Overlapping Intervals
def merge(intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlap
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
merged.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int start = intervals[i][0], end = intervals[i][1];
int[] last = merged.get(merged.size() - 1);
if (start <= last[1]) { // overlap
last[1] = Math.max(last[1], end);
} else {
merged.add(new int[]{start, end});
}
}
return merged.toArray(new int[0][]);
}
int[][] Merge(int[][] intervals) {
Array.Sort(intervals, (a, b) => a[0] - b[0]);
var merged = new List<int[]> { intervals[0] };
for (int i = 1; i < intervals.Length; i++) {
int start = intervals[i][0], end = intervals[i][1];
var last = merged[merged.Count - 1];
if (start <= last[1]) { // overlap
last[1] = Math.Max(last[1], end);
} else {
merged.Add(new int[] { start, end });
}
}
return merged.ToArray();
}
Template — Minimum Meeting Rooms (sweep)
import heapq
def min_meeting_rooms(intervals):
intervals.sort() # sort by start
heap = [] # min-heap of end times
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end) # reuse freed room
else:
heapq.heappush(heap, end) # need new room
return len(heap)
int minMeetingRooms(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // sort by start
PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap of end times
for (int[] iv : intervals) {
int start = iv[0], end = iv[1];
if (!heap.isEmpty() && heap.peek() <= start) {
heap.poll(); // reuse freed room
}
heap.offer(end); // need new room (or the one just freed)
}
return heap.size();
}
int MinMeetingRooms(int[][] intervals) {
Array.Sort(intervals, (a, b) => a[0] - b[0]); // sort by start
var heap = new PriorityQueue<int, int>(); // min-heap of end times
foreach (var iv in intervals) {
int start = iv[0], end = iv[1];
if (heap.Count > 0 && heap.Peek() <= start) {
heap.Dequeue(); // reuse freed room
}
heap.Enqueue(end, end); // need new room (or the one just freed)
}
return heap.Count;
}
Almost every tree problem is a variant of DFS or BFS. Post-order DFS (process children before parent) solves path-sum and height problems. Pre-order (process parent first) suits serialization or printing. BFS with a deque naturally gives you level-by-level access. For BSTs, exploit the invariant: left < node < right.
Reach for this when: you see a tree structure. Default to recursive DFS — write the helper's return value contract first, then implement. Switch to BFS only when you need levels or shortest-path semantics.
Template — DFS (post-order)
def dfs(node):
if not node:
return 0 # base case (adjust per problem)
left = dfs(node.left)
right = dfs(node.right)
# combine at current node
return 1 + max(left, right) # e.g. height
int dfs(TreeNode node) {
if (node == null) {
return 0; // base case (adjust per problem)
}
int left = dfs(node.left);
int right = dfs(node.right);
// combine at current node
return 1 + Math.max(left, right); // e.g. height
}
int Dfs(TreeNode node) {
if (node == null) {
return 0; // base case (adjust per problem)
}
int left = Dfs(node.left);
int right = Dfs(node.right);
// combine at current node
return 1 + Math.Max(left, right); // e.g. height
}
Template — BFS (level-order)
from collections import deque
def level_order(root):
if not root: return []
q, result = deque([root]), []
while q:
level = []
for _ in range(len(q)): # freeze level size
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
result.append(level)
return result
List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
List<Integer> level = new ArrayList<>();
int size = q.size(); // freeze level size
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
level.add(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
result.add(level);
}
return result;
}
IList<IList<int>> LevelOrder(TreeNode root) {
var result = new List<IList<int>>();
if (root == null) return result;
var q = new Queue<TreeNode>();
q.Enqueue(root);
while (q.Count > 0) {
var level = new List<int>();
int size = q.Count; // freeze level size
for (int i = 0; i < size; i++) {
var node = q.Dequeue();
level.Add(node.val);
if (node.left != null) q.Enqueue(node.left);
if (node.right != null) q.Enqueue(node.right);
}
result.Add(level);
}
return result;
}
Template — BST Validation (pass valid range down)
def is_valid(node, lo=float('-inf'), hi=float('inf')):
if not node: return True
if not (lo < node.val < hi): return False
return (is_valid(node.left, lo, node.val) and
is_valid(node.right, node.val, hi))
boolean isValid(TreeNode node, long lo, long hi) {
if (node == null) return true;
if (!(lo < node.val && node.val < hi)) return false;
return isValid(node.left, lo, node.val) &&
isValid(node.right, node.val, hi);
}
// initial call: isValid(root, Long.MIN_VALUE, Long.MAX_VALUE)
bool IsValid(TreeNode node, long lo, long hi) {
if (node == null) return true;
if (!(lo < node.val && node.val < hi)) return false;
return IsValid(node.left, lo, node.val) &&
IsValid(node.right, node.val, hi);
}
// initial call: IsValid(root, long.MinValue, long.MaxValue)
Graph problems are just DFS/BFS with a visited set. Choose BFS for shortest path (unweighted). Use DFS for connectivity, cycle detection, and topological sort. Union-Find (Disjoint Set Union) is the cleanest tool for dynamic connectivity. Dijkstra handles weighted shortest paths.
Reach for this when: you see a 2D grid (islands, flow), a node-edge relationship (courses, dependencies), or need connectivity/path queries. Grids are implicit graphs — (r, c) is a node, 4-directional neighbours are edges.
Template — BFS (shortest path / flood fill)
from collections import deque
def bfs(start, graph):
visited = {start}
q = deque([(start, 0)]) # (node, distance)
while q:
node, dist = q.popleft()
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
q.append((nb, dist + 1))
void bfs(int start, Map<Integer, List<Integer>> graph) {
Set<Integer> visited = new HashSet<>();
visited.add(start);
Deque<int[]> q = new ArrayDeque<>(); // (node, distance)
q.offer(new int[]{start, 0});
while (!q.isEmpty()) {
int[] cur = q.poll();
int node = cur[0], dist = cur[1];
for (int nb : graph.get(node)) {
if (!visited.contains(nb)) {
visited.add(nb);
q.offer(new int[]{nb, dist + 1});
}
}
}
}
void Bfs(int start, Dictionary<int, List<int>> graph) {
var visited = new HashSet<int> { start };
var q = new Queue<(int node, int dist)>();
q.Enqueue((start, 0));
while (q.Count > 0) {
var (node, dist) = q.Dequeue();
foreach (var nb in graph[node]) {
if (!visited.Contains(nb)) {
visited.Add(nb);
q.Enqueue((nb, dist + 1));
}
}
}
}
Template — Union-Find (with path compression + union by rank)
int[] parent = new int[n];
int[] rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
boolean union(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false; // already connected
if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
parent[py] = px;
if (rank[px] == rank[py]) rank[px]++;
return true;
}
int[] parent = Enumerable.Range(0, n).ToArray();
int[] rank = new int[n];
int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]); // path compression
}
return parent[x];
}
bool Union(int x, int y) {
int px = Find(x), py = Find(y);
if (px == py) return false; // already connected
if (rank[px] < rank[py]) { (px, py) = (py, px); }
parent[py] = px;
if (rank[px] == rank[py]) rank[px]++;
return true;
}
Template — Topological Sort (Kahn's BFS)
from collections import deque, defaultdict
indegree = [0] * numCourses
adj = defaultdict(list)
for a, b in prerequisites:
adj[b].append(a)
indegree[a] += 1
q = deque([i for i in range(numCourses) if indegree[i] == 0])
order = []
while q:
node = q.popleft()
order.append(node)
for nb in adj[node]:
indegree[nb] -= 1
if indegree[nb] == 0:
q.append(nb)
# cycle exists if len(order) < numCourses
int[] indegree = new int[numCourses];
Map<Integer, List<Integer>> adj = new HashMap<>();
for (int[] pr : prerequisites) {
int a = pr[0], b = pr[1];
adj.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
indegree[a]++;
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) q.offer(i);
}
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
int node = q.poll();
order.add(node);
for (int nb : adj.getOrDefault(node, List.of())) {
if (--indegree[nb] == 0) q.offer(nb);
}
}
// cycle exists if order.size() < numCourses
var indegree = new int[numCourses];
var adj = new Dictionary<int, List<int>>();
foreach (var pr in prerequisites) {
int a = pr[0], b = pr[1];
if (!adj.ContainsKey(b)) adj[b] = new List<int>();
adj[b].Add(a);
indegree[a]++;
}
var q = new Queue<int>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) q.Enqueue(i);
}
var order = new List<int>();
while (q.Count > 0) {
int node = q.Dequeue();
order.Add(node);
if (adj.TryGetValue(node, out var neighbors)) {
foreach (var nb in neighbors) {
if (--indegree[nb] == 0) q.Enqueue(nb);
}
}
}
// cycle exists if order.Count < numCourses
Whenever a problem asks for the K largest, K most frequent, or K closest items, a heap is almost always the right tool. The key insight: maintain a min-heap of size K while scanning. When the heap exceeds size K, pop the smallest — what remains is the K largest seen so far.
For K smallest, flip to a max-heap (negate values in Python). For "top K frequent", use a bucket sort approach for O(n) time.
Reach for this when: you see "kth largest/smallest", "top K frequent elements", "K closest points". The brute-force is sort-then-slice at O(n log n); a heap gives O(n log k) — better when k ≪ n. Use heapq.nlargest(k, arr) in a pinch, but know the manual approach.
Template — K Largest with Min-Heap
import heapq
def find_kth_largest(nums, k):
heap = []
for n in nums:
heapq.heappush(heap, n)
if len(heap) > k:
heapq.heappop(heap) # discard smallest seen
return heap[0] # smallest of the K largest = kth largest
int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int n : nums) {
heap.offer(n);
if (heap.size() > k) {
heap.poll(); // discard smallest seen
}
}
return heap.peek(); // smallest of the K largest = kth largest
}
int FindKthLargest(int[] nums, int k) {
var heap = new PriorityQueue<int, int>();
foreach (var n in nums) {
heap.Enqueue(n, n);
if (heap.Count > k) {
heap.Dequeue(); // discard smallest seen
}
}
return heap.Peek(); // smallest of the K largest = kth largest
}
Template — Top K Frequent (bucket sort, O(n))
from collections import Counter
def top_k_frequent(nums, k):
count = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for num, freq in count.items():
buckets[freq].append(num)
result = []
for i in range(len(buckets) - 1, 0, -1):
result.extend(buckets[i])
if len(result) >= k:
return result[:k]
int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
for (int n : nums) count.merge(n, 1, Integer::sum);
List<Integer>[] buckets = new List[nums.length + 1];
for (int i = 0; i <= nums.length; i++) buckets[i] = new ArrayList<>();
for (var e : count.entrySet()) buckets[e.getValue()].add(e.getKey());
List<Integer> result = new ArrayList<>();
for (int i = buckets.length - 1; i > 0 && result.size() < k; i--) {
result.addAll(buckets[i]);
}
return result.stream().limit(k).mapToInt(Integer::intValue).toArray();
}
int[] TopKFrequent(int[] nums, int k) {
var count = new Dictionary<int, int>();
foreach (var n in nums) count[n] = count.GetValueOrDefault(n) + 1;
var buckets = new List<int>[nums.Length + 1];
for (int i = 0; i <= nums.Length; i++) buckets[i] = new List<int>();
foreach (var e in count) buckets[e.Value].Add(e.Key);
var result = new List<int>();
for (int i = buckets.Length - 1; i > 0 && result.Count < k; i--) {
result.AddRange(buckets[i]);
}
return result.Take(k).ToArray();
}
Maintain two heaps that partition a running dataset at its median: a max-heap for the lower half and a min-heap for the upper half. Keep them balanced (size difference ≤ 1). The median is either the top of the larger heap, or the average of both tops.
Each insertion is O(log n). Finding the median is O(1). This beats sorting the array on every query (O(n log n) per query).
Reach for this when: you need a running median as elements arrive, or when a problem partitions a set into two halves where you need the maximum of one half and the minimum of the other simultaneously (scheduling, IPO).
DP applies when a problem has overlapping subproblems (same inputs recomputed) and optimal substructure (optimal answer to sub-problems → optimal answer to whole). The method: (1) define state clearly, (2) write the recurrence, (3) identify base cases, (4) decide memo vs tabulation.
Common DP shapes: 1-D (Fibonacci-style), 2-D (grid or two-sequence), knapsack (subset-sum), interval DP.
Reach for this when: the problem says "count ways", "min/max cost", "can we achieve X", and the brute-force tries all combinations. If you're writing recursion with repeated sub-problems, add memo — you have DP.
Template — Top-down (memoization)
from functools import lru_cache
@lru_cache(maxsize=None)
def dp(i, ...): # define your state
if i == base: return base_value
return min(dp(i-1, ...) + cost, ...) # recurrence
Map<Integer, Integer> memo = new HashMap<>();
int dp(int i /* ... */) { // define your state
if (i == base) return baseValue;
if (memo.containsKey(i)) return memo.get(i);
int result = Math.min(dp(i - 1) + cost, /* ... */ 0); // recurrence
memo.put(i, result);
return result;
}
Dictionary<int, int> memo = new();
int Dp(int i /* ... */) { // define your state
if (i == base) return baseValue;
if (memo.TryGetValue(i, out var cached)) return cached;
int result = Math.Min(Dp(i - 1) + cost, /* ... */ 0); // recurrence
memo[i] = result;
return result;
}
Template — Bottom-up 1-D
dp = [0] * (n + 1)
dp[0], dp[1] = base0, base1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2] # or your recurrence
return dp[n]
int[] dp = new int[n + 1];
dp[0] = base0; dp[1] = base1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // or your recurrence
}
return dp[n];
var dp = new int[n + 1];
dp[0] = base0; dp[1] = base1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // or your recurrence
}
return dp[n];
dp = [0] * (capacity + 1)
for weight, value in items:
for w in range(capacity, weight - 1, -1): # ← reverse prevents reuse
dp[w] = max(dp[w], dp[w - weight] + value)
int[] dp = new int[capacity + 1];
for (int[] item : items) {
int weight = item[0], value = item[1];
for (int w = capacity; w >= weight; w--) { // <- reverse prevents reuse
dp[w] = Math.max(dp[w], dp[w - weight] + value);
}
}
var dp = new int[capacity + 1];
foreach (var item in items) {
int weight = item[0], value = item[1];
for (int w = capacity; w >= weight; w--) { // <- reverse prevents reuse
dp[w] = Math.Max(dp[w], dp[w - weight] + value);
}
}
Template — 2-D (edit distance / LCS)
dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
for i in range(1, len(s)+1):
for j in range(1, len(t)+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
At each step, take the locally optimal choice and never look back. Greedy works when you can prove (via exchange argument) that swapping any two adjacent choices doesn't improve the answer. The typical setup: sort by some criteria, then iterate linearly making irrevocable decisions.
Reach for this when: the problem involves scheduling, intervals, or building a result incrementally. If you can show "there's always an optimal solution that makes this greedy choice first", it works.
intervals.sort(key=lambda x: x[1]) # sort by end time
count, end = 0, float('-inf')
for start, finish in intervals:
if start >= end: # no overlap
count += 1
end = finish
Arrays.sort(intervals, (a, b) -> a[1] - b[1]); // sort by end time
int count = 0;
int end = Integer.MIN_VALUE;
for (int[] iv : intervals) {
int start = iv[0], finish = iv[1];
if (start >= end) { // no overlap
count++;
end = finish;
}
}
Array.Sort(intervals, (a, b) => a[1] - b[1]); // sort by end time
int count = 0;
int end = int.MinValue;
foreach (var iv in intervals) {
int start = iv[0], finish = iv[1];
if (start >= end) { // no overlap
count++;
end = finish;
}
}
Template — Jump Game (max reach)
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach: return False # unreachable
max_reach = max(max_reach, i + jump)
return True
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) return false; // unreachable
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
int maxReach = 0;
for (int i = 0; i < nums.Length; i++) {
if (i > maxReach) return false; // unreachable
maxReach = Math.Max(maxReach, i + nums[i]);
}
return true;
Template — Partition Labels (last occurrence)
last = {c: i for i, c in enumerate(s)} # rightmost position of each char
start = end = 0
sizes = []
for i, c in enumerate(s):
end = max(end, last[c])
if i == end: # can cut here
sizes.append(end - start + 1)
start = i + 1
Map<Character, Integer> last = new HashMap<>();
for (int i = 0; i < s.length(); i++) last.put(s.charAt(i), i); // rightmost position of each char
int start = 0, end = 0;
List<Integer> sizes = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, last.get(s.charAt(i)));
if (i == end) { // can cut here
sizes.add(end - start + 1);
start = i + 1;
}
}
var last = new Dictionary<char, int>();
for (int i = 0; i < s.Length; i++) last[s[i]] = i; // rightmost position of each char
int start = 0, end = 0;
var sizes = new List<int>();
for (int i = 0; i < s.Length; i++) {
end = Math.Max(end, last[s[i]]);
if (i == end) { // can cut here
sizes.Add(end - start + 1);
start = i + 1;
}
}
Backtracking is exhaustive search with pruning. You build a candidate solution one element at a time; if at any point the partial candidate cannot lead to a valid solution, you undo the last choice and try the next one. Think of it as a DFS over a decision tree.
The three-step loop: choose → explore → un-choose (backtrack).
Reach for this when: the problem asks for all solutions (permutations, subsets, combinations), constraint satisfaction (N-queens, Sudoku), or when "try every possibility" is the only option but pruning makes it feasible.
Template — Subsets / Combinations
def backtrack(start, path):
result.append(path[:]) # record every state (subsets)
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue # skip duplicates at same depth
path.append(nums[i]) # choose
backtrack(i + 1, path) # explore (i+1 = no reuse)
path.pop() # un-choose
nums.sort() # sort first to group duplicates
result = []
backtrack(0, [])
void backtrack(int start, List<Integer> path) {
result.add(new ArrayList<>(path)); // record every state (subsets)
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue; // skip duplicates at same depth
}
path.add(nums[i]); // choose
backtrack(i + 1, path); // explore (i+1 = no reuse)
path.remove(path.size() - 1); // un-choose
}
}
Arrays.sort(nums); // sort first to group duplicates
List<List<Integer>> result = new ArrayList<>();
backtrack(0, new ArrayList<>());
void Backtrack(int start, List<int> path) {
result.Add(new List<int>(path)); // record every state (subsets)
for (int i = start; i < nums.Length; i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue; // skip duplicates at same depth
}
path.Add(nums[i]); // choose
Backtrack(i + 1, path); // explore (i+1 = no reuse)
path.RemoveAt(path.Count - 1); // un-choose
}
}
Array.Sort(nums); // sort first to group duplicates
var result = new List<List<int>>();
Backtrack(0, new List<int>());
Template — Permutations
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i, num in enumerate(nums):
if used[i]: continue
if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue # dup check
used[i] = True
path.append(num)
backtrack(path, used)
path.pop()
used[i] = False
void backtrack(List<Integer> path, boolean[] used) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // dup check
used[i] = true;
path.add(nums[i]);
backtrack(path, used);
path.remove(path.size() - 1);
used[i] = false;
}
}
void Backtrack(List<int> path, bool[] used) {
if (path.Count == nums.Length) {
result.Add(new List<int>(path));
return;
}
for (int i = 0; i < nums.Length; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // dup check
used[i] = true;
path.Add(nums[i]);
Backtrack(path, used);
path.RemoveAt(path.Count - 1);
used[i] = false;
}
}
Binary search halves the search space each iteration. The classic form finds a value in a sorted array. The power form is "binary search on the answer": when you can define a monotone predicate f(x) — true for all x above some threshold, false below — binary search finds that threshold in O(log n) even if you never see the array explicitly.
Reach for this when: the input is sorted (or sorted after some transform), or when the problem asks for "minimum X such that condition holds" / "maximum X such that condition holds". The "Koko Eating Bananas" family of problems are binary search on the answer.
Template — Standard Binary Search
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # avoids overflow
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1 # not found
int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoids overflow
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1; // not found
}
int BinarySearch(int[] arr, int target) {
int lo = 0, hi = arr.Length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoids overflow
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1; // not found
}
Template — Binary Search on Answer (find minimum feasible x)
def feasible(x):
# returns True if x satisfies the problem's constraint
...
lo, hi = min_possible_answer, max_possible_answer
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid # try smaller
else:
lo = mid + 1
return lo # minimum feasible value
boolean feasible(int x) {
// returns true if x satisfies the problem's constraint
...
}
int lo = minPossibleAnswer, hi = maxPossibleAnswer;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (feasible(mid)) {
hi = mid; // try smaller
} else {
lo = mid + 1;
}
}
return lo; // minimum feasible value
bool Feasible(int x) {
// returns true if x satisfies the problem's constraint
...
}
int lo = minPossibleAnswer, hi = maxPossibleAnswer;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (Feasible(mid)) {
hi = mid; // try smaller
} else {
lo = mid + 1;
}
}
return lo; // minimum feasible value
Template — Rotated Sorted Array
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target: return mid
# figure out which half is sorted
if nums[lo] <= nums[mid]: # left half is sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
// figure out which half is sorted
if (nums[lo] <= nums[mid]) { // left half is sorted
if (nums[lo] <= target && target < nums[mid]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else { // right half is sorted
if (nums[mid] < target && target <= nums[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
int lo = 0, hi = nums.Length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
// figure out which half is sorted
if (nums[lo] <= nums[mid]) { // left half is sorted
if (nums[lo] <= target && target < nums[mid]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else { // right half is sorted
if (nums[mid] < target && target <= nums[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
Time: O(log n) search · O(n log n) sort first if neededSpace: O(1)
Bit tricks give O(1) solutions to problems that otherwise take O(n). The two most useful facts: XOR cancels duplicates (a ^ a = 0, a ^ 0 = a), so XOR-ing an array leaves the unique element. And n & (n−1) clears the lowest set bit, giving you popcount in O(set bits) iterations.
Reach for this when: you need to find a single unpaired number (XOR all), check powers of 2 (n & (n−1) == 0), enumerate subsets (for mask in range(1 << n)), or simulate addition without +.
Cheat-Sheet
# --- Core operations ---
x & y # AND: bits set in both
x | y # OR: bits set in either
x ^ y # XOR: bits set in exactly one
~x # NOT: flip all bits
x << k # left shift = x * 2^k
x >> k # right shift = x // 2^k
# --- Key tricks ---
n & (n - 1) # clear lowest set bit
n & (-n) # isolate lowest set bit
n & 1 # check if odd
(n >> k) & 1 # check k-th bit
# Find single number (XOR all)
result = 0
for num in nums: result ^= num
# Count set bits (Brian Kernighan)
count = 0
while n: n &= n - 1; count += 1
# Is power of 2?
n > 0 and (n & (n - 1)) == 0
# Enumerate all subsets of n-element set
for mask in range(1 << n):
subset = [i for i in range(n) if mask >> i & 1]
// --- Core operations ---
x & y // AND: bits set in both
x | y // OR: bits set in either
x ^ y // XOR: bits set in exactly one
~x // NOT: flip all bits
x << k // left shift = x * 2^k
x >> k // right shift = x / 2^k
// --- Key tricks ---
n & (n - 1) // clear lowest set bit
n & (-n) // isolate lowest set bit
n & 1 // check if odd
(n >> k) & 1 // check k-th bit
// Find single number (XOR all)
int result = 0;
for (int num : nums) result ^= num;
// Count set bits (Brian Kernighan)
int count = 0;
while (n != 0) { n &= n - 1; count++; }
// Is power of 2?
n > 0 && (n & (n - 1)) == 0
// Enumerate all subsets of n-element set
for (int mask = 0; mask < (1 << n); mask++) {
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask >> i & 1) == 1) subset.add(i);
}
}
// --- Core operations ---
x & y // AND: bits set in both
x | y // OR: bits set in either
x ^ y // XOR: bits set in exactly one
~x // NOT: flip all bits
x << k // left shift = x * 2^k
x >> k // right shift = x / 2^k
// --- Key tricks ---
n & (n - 1) // clear lowest set bit
n & (-n) // isolate lowest set bit
n & 1 // check if odd
(n >> k) & 1 // check k-th bit
// Find single number (XOR all)
int result = 0;
foreach (var num in nums) result ^= num;
// Count set bits (Brian Kernighan)
int count = 0;
while (n != 0) { n &= n - 1; count++; }
// Is power of 2?
n > 0 && (n & (n - 1)) == 0
// Enumerate all subsets of n-element set
for (int mask = 0; mask < (1 << n); mask++) {
var subset = new List<int>();
for (int i = 0; i < n; i++) {
if ((mask >> i & 1) == 1) subset.Add(i);
}
}
Interview Framework (use this structure every time)
Clarify — functional requirements (what it does) + non-functional (scale, latency, consistency, availability). Never design before you know the scope.
Estimate — QPS, storage GB/TB, bandwidth. Back-of-napkin math shows you're reasoning about scale.
High-Level Design — draw client → LB → servers → DB → cache. Name the components before detailing them.
Deep Dive — data model, key APIs, the one component the interviewer cares about most (usually the hardest one).
Bottlenecks & Trade-offs — SPOF, sharding strategy, caching eviction policy, eventual vs strong consistency. Show you know what you're giving up.
Key rule: drive the conversation. Don't wait to be asked — propose a design, then critique it yourself. Interviewers want to see your thought process, not a memorised answer.