Operations that execute in the same time regardless of input size.
Example
// JavaScriptfunctiongetFirst(arr){return arr[0];}const map =newMap();
map.set('key',42);
map.get('key');// O(1) average
# Python
def get_first(arr):return arr[0]
lookup ={'key':42}
lookup['key'] # O(1) average
Output
Time: O(1) | Space: O(1)
Note Hash map lookups are O(1) average but O(n) worst case due to collisions. Array index access is always O(1). Interviewers love asking: 'Is this truly constant?' - know the difference between average and worst case.
constant timeO(1)big ohash map lookuparray access
O(log n) - Logarithmic Time
Syntax
Each step halves the remaining work.Classic sign: dividing the problem space in two.
Example
// JavaScriptfunctionbinarySearch(arr, target){let lo =0, hi = arr.length-1;while(lo <= hi){const mid = lo +Math.floor((hi - lo)/2);if(arr[mid]=== target)return mid;elseif(arr[mid]< target) lo = mid +1;else hi = mid -1;}return-1;}
# Python
def binary_search(arr, target):
lo, hi =0,len(arr)-1while lo <= hi:
mid = lo +(hi - lo)// 2if arr[mid]== target:return mid
elif arr[mid]< target:
lo = mid +1else:
hi = mid -1return-1
Output
Time: O(log n) | Space: O(1)
Note Balanced BST operations are O(log n). Use mid = lo + (hi - lo) // 2 instead of (lo + hi) // 2 to prevent integer overflow. If you see 'sorted array' in a problem, think binary search immediately.
logarithmic timeO(log n)binary searchbig odivide and conquer
O(n) - Linear Time
Syntax
Work grows directly with input size.One pass through the data.
Example
// JavaScriptfunctionfindMax(arr){let max =-Infinity;for(const val of arr){if(val > max) max = val;}return max;}
# Python
def find_max(arr):
maximum =float('-inf')for val in arr:if val > maximum:
maximum = val
return maximum
Output
Time: O(n) | Space: O(1)
Note Single loop over n elements is O(n). Two separate loops (not nested) is still O(n) - O(2n) simplifies to O(n). Interviewers want you to drop constants and lower-order terms.
linear timeO(n)big osingle passloop complexity
O(n log n) - Linearithmic Time
Syntax
Typicalof efficient comparison-based sorts.Youdivide(log n levels) and doO(n) work per level.
Time: O(n log n) | Space: O(n) for merge sort, O(log n) for quicksort avg
Note O(n log n) is the theoretical lower bound for comparison-based sorting. If an interviewer asks you to do better, the input must have special structure (e.g., bounded integers for counting sort). Heap operations on n elements also yield O(n log n).
n log nO(n log n)sorting complexitymerge sortbig o
O(n^2) - Quadratic Time
Syntax
Nested loops where both iterate over n.Often a signal to optimize.
Example
// JavaScriptfunctionhasDuplicateBrute(arr){for(let i =0; i < arr.length; i++){for(let j = i +1; j < arr.length; j++){if(arr[i]=== arr[j])returntrue;}}returnfalse;}
# Python
def has_duplicate_brute(arr):for i inrange(len(arr)):for j inrange(i +1,len(arr)):if arr[i]== arr[j]:returnTruereturnFalse
Output
Time: O(n^2) | Space: O(1)
Note Bubble sort, selection sort, and insertion sort are all O(n^2). If your brute force is O(n^2), try using a hash map or sorting to bring it down to O(n) or O(n log n). Interviewers often want you to identify the brute force first, then optimize.
quadratic timeO(n^2)nested loopsbrute forcebig o
O(2^n) - Exponential Time
Syntax
Each element doubles the work.Commonin recursive solutions without memoization.
Example
// JavaScriptfunctionfibNaive(n){if(n <=1)return n;returnfibNaive(n -1)+fibNaive(n -2);}// Each call branches into 2 → O(2^n)
# Python
def fib_naive(n):if n <=1:return n
returnfib_naive(n -1)+fib_naive(n -2)
# Fixwith memoization → O(n)
Output
Time: O(2^n) without memo | O(n) with memo | Space: O(n)
Note Generating all subsets of a set is O(2^n). This is a red flag in interviews - if your solution is exponential, look for overlapping subproblems (DP) or pruning (backtracking). Always mention that memoization brings it down.
Generating all permutations of n items.Grows astronomically fast.
Example
// JavaScriptfunctionpermutations(arr){if(arr.length<=1)return[arr];const result =[];for(let i =0; i < arr.length; i++){const rest =[...arr.slice(0, i),...arr.slice(i +1)];for(const perm ofpermutations(rest)){
result.push([arr[i],...perm]);}}return result;}
# Python
def get_permutations(arr):iflen(arr)<=1:return[arr[:]]
result =[]for i inrange(len(arr)):
rest = arr[:i]+ arr[i+1:]for perm inget_permutations(rest):
result.append([arr[i]]+ perm)return result
Output
Time: O(n!) | Space: O(n!) to store all permutations
Note 10! = 3,628,800 and 20! is over 2 quintillion. If n > ~10-12, factorial algorithms won't finish in time. The traveling salesman brute force is O(n!). Interviewers accept factorial only when generating all permutations is required.
1.Count nested loops
2.Identify recursive branching factor and depth
3.Drop constants and lower-order terms
4.Consider best / average / worst case separately
Example
// JavaScript - Analyzing a functionfunctionexample(arr){// Loop 1: O(n)for(let i =0; i < arr.length; i++){/* ... */}// Loop 2 (nested): O(n^2)for(let i =0; i < arr.length; i++){for(let j =0; j < arr.length; j++){/* ... */}}}// Total: O(n) + O(n^2) = O(n^2) - dominated by the larger term
# Python-Same analysis
def example(arr):for x in arr: # O(n)
pass
for x in arr: # O(n^2)for y in arr:
pass
# Total:O(n^2)
Output
Always state the dominant term as the final answer.
Note Common trap: a loop inside a loop is not always O(n^2). If the inner loop runs a fixed number of times (say 26 for alphabet), it is O(26n) = O(n). Also watch for hidden loops: string concatenation in a loop is O(n) per concat in many languages, making the total O(n^2).
analyze complexitytime complexityhow to calculate big onested loopsdominant term
Space Complexity
Syntax
Measure extra memory used beyond the input.-Variables/ pointers:O(1)-New array of size n:O(n)-Recursive call stack of depth n:O(n)-2D matrix n×m:O(n*m)
Example
// JavaScript// O(1) space - in-place swapfunctionreverseInPlace(arr){let l =0, r = arr.length-1;while(l < r){[arr[l], arr[r]]=[arr[r], arr[l]];
l++; r--;}}// O(n) space - new arrayfunctionreversed(arr){return arr.slice().reverse();}
# Python
def reverse_in_place(arr):
l, r =0,len(arr)-1while l < r:
arr[l], arr[r]= arr[r], arr[l]
l +=1; r -=1
def reversed_copy(arr):return arr[::-1] # O(n) space
Output
In-place: O(1) space | Copy: O(n) space
Note Interviewers often ask 'Can you do it in O(1) space?' - this means modify the input in place. Recursive solutions use O(depth) stack space even if no extra data structures are created. Always mention auxiliary space vs total space.
space complexityin-placeauxiliary spacememory usagebig o space
Amortized Analysis
Syntax
Average cost per operation over a sequence of operations.A single operation may be expensive, but averaged over many operations the cost is low.
Example
// JavaScript// Dynamic array (push) - occasionally resizes (O(n) copy)// but amortized cost per push is O(1)const arr =[];for(let i =0; i <1000; i++){
arr.push(i);// Amortized O(1) per push}
# Python
# Python list.appendis amortized O(1)
arr =[]for i inrange(1000):
arr.append(i) # AmortizedO(1)
Output
Amortized O(1) per append despite occasional O(n) resize
Note Classic examples: dynamic array resizing (doubling strategy), hash map rehashing. The key insight is that expensive operations happen infrequently enough that the cost 'spreads out'. Interviewers rarely ask you to prove amortized bounds, but mentioning 'amortized O(1)' for array pushes shows depth.
amortized analysisamortized O(1)dynamic arraybig o amortizedarray resize
Use two indices(left and right) moving toward each other or in the same direction.Works on sorted arrays or when searching for pairs.
Example
// JavaScript - Find pair that sums to target in sorted arrayfunctiontwoSumSorted(arr, target){let left =0, right = arr.length-1;while(left < right){const sum = arr[left]+ arr[right];if(sum === target)return[left, right];elseif(sum < target) left++;else right--;}return[-1,-1];}
# Python
def two_sum_sorted(arr, target):
left, right =0,len(arr)-1while left < right:
total = arr[left]+ arr[right]if total == target:return[left, right]
elif total < target:
left +=1else:
right -=1return[-1,-1]
Output
twoSumSorted([1,3,5,7,9], 8) → [1, 3]
Note Time O(n), Space O(1). Requires sorted input for the converging pattern. Edge cases: empty array, single element, no valid pair. Tell the interviewer you chose two pointers over hash map to achieve O(1) space.
two pointerssorted array pairtwo sum sortedconverging pointers
Sliding Window
Syntax
Maintain a window[left..right] and expand/shrink to satisfy a condition.Fixed-size window: move both pointers together.Variable-size window: expand right, shrink left when constraint violated.
Example
// JavaScript - Max sum subarray of size kfunctionmaxSumWindow(arr, k){let windowSum =0, maxSum =-Infinity;for(let i =0; i < arr.length; i++){
windowSum += arr[i];if(i >= k) windowSum -= arr[i - k];if(i >= k -1) maxSum =Math.max(maxSum, windowSum);}return maxSum;}
# Python-Max sum subarray of size k
def max_sum_window(arr, k):
window_sum =0
max_sum =float('-inf')for i inrange(len(arr)):
window_sum += arr[i]if i >= k:
window_sum -= arr[i - k]if i >= k -1:
max_sum =max(max_sum, window_sum)return max_sum
Note Time O(n), Space O(1). Sliding window converts O(n*k) brute force to O(n). For variable-size windows (e.g., longest substring without repeats), use a hash set to track window contents. Always clarify: is the window fixed or variable size?
sliding windowmax sum subarrayfixed windowvariable windowsubstring
Prefix Sum
Syntax
Build a cumulative sum array so any range sum can be computed inO(1).
prefix[i]= sum of arr[0..i-1]Range sum [l..r]= prefix[r+1]- prefix[l]
Example
// JavaScriptfunctionbuildPrefix(arr){const prefix =[0];for(const val of arr){
prefix.push(prefix[prefix.length-1]+ val);}return prefix;}functionrangeSum(prefix, left, right){return prefix[right +1]- prefix[left];}
# Python
def build_prefix(arr):
prefix =[0]for val in arr:
prefix.append(prefix[-1]+ val)return prefix
def range_sum(prefix, left, right):return prefix[right +1]- prefix[left]
Note Build: O(n) time, O(n) space. Query: O(1). Extremely useful when you need many range sum queries. Variant: prefix XOR for range XOR problems. For 2D grids, use 2D prefix sums with inclusion-exclusion.
prefix sumrange sum querycumulative sumsubarray sum
Kadane's Algorithm - Maximum Subarray
Syntax
Track current subarray sum.If it drops below 0, reset to 0.At each step: currentSum =max(num, currentSum + num)Keep a global max.
Example
// JavaScriptfunctionmaxSubarraySum(arr){let current = arr[0], best = arr[0];for(let i =1; i < arr.length; i++){
current =Math.max(arr[i], current + arr[i]);
best =Math.max(best, current);}return best;}
# Python
def max_subarray_sum(arr):
current = best = arr[0]for num in arr[1:]:
current =max(num, current + num)
best =max(best, current)return best
Note Time O(n), Space O(1). Edge case: all negative numbers - algorithm still works since we initialize with arr[0]. To find the actual subarray indices, track start/end when best updates. Variant: maximum circular subarray uses total_sum - min_subarray.
lo =0, hi = length -1while lo <= hi:
mid = lo +(hi - lo)// 2
compare and adjust lo or hi
Example
// JavaScriptfunctionbinarySearch(arr, target){let lo =0, hi = arr.length-1;while(lo <= hi){const mid = lo +Math.floor((hi - lo)/2);if(arr[mid]=== target)return mid;if(arr[mid]< target) lo = mid +1;else hi = mid -1;}return-1;// not found}
# Python
def binary_search(arr, target):
lo, hi =0,len(arr)-1while lo <= hi:
mid = lo +(hi - lo)// 2if arr[mid]== target:return mid
elif arr[mid]< target:
lo = mid +1else:
hi = mid -1return-1
Output
binary_search([1,3,5,7,9,11], 7) → 3
Note Time O(log n), Space O(1). Off-by-one errors are the #1 bug - practice until the template is muscle memory. Use lo <= hi when searching for exact match. Use lo < hi when narrowing to a single candidate. Always test with 0, 1, and 2 element arrays.
binary searchsorted arraysearch algorithmlog n
String Reversal
Syntax
Two pointers from ends, swap toward center.Or use built-in reverse methods.
Example
// JavaScriptfunctionreverseString(s){const chars = s.split('');let l =0, r = chars.length-1;while(l < r){[chars[l], chars[r]]=[chars[r], chars[l]];
l++; r--;}return chars.join('');}// Built-in: s.split('').reverse().join('')
# Python
def reverse_string(s):
chars =list(s)
l, r =0,len(chars)-1while l < r:
chars[l], chars[r]= chars[r], chars[l]
l +=1; r -=1return''.join(chars)
# Built-in: s[::-1]
Output
reverseString('interview') → 'weivretni'
Note Time O(n), Space O(n) due to string immutability (both JS and Python strings are immutable). In-place reversal is possible on char arrays. Common follow-ups: reverse words in a sentence, reverse only vowels, check if palindrome.
Two strings are anagrams if they have identical character frequencies.Approach1:Sort both and compare.Approach2:Build frequency map and compare.
Example
// JavaScriptfunctionisAnagram(s, t){if(s.length!== t.length)returnfalse;const freq ={};for(const ch of s) freq[ch]=(freq[ch]||0)+1;for(const ch of t){if(!freq[ch])returnfalse;
freq[ch]--;}returntrue;}
# Python
def is_anagram(s, t):iflen(s)!=len(t):returnFalse
freq ={}for ch in s:
freq[ch]= freq.get(ch,0)+1for ch in t:if freq.get(ch,0)==0:returnFalse
freq[ch]-=1returnTrue
Output
is_anagram('listen', 'silent') → True
Note Frequency map: O(n) time, O(1) space (bounded by alphabet size). Sorting approach: O(n log n). Always ask: are inputs lowercase only? Unicode? This affects space analysis. Follow-up: find all anagram groups in a list of words.
Approach1:Hashset-O(n) time,O(n) space
Approach2:Sort first -O(n log n) time,O(1) space
Approach3:Floyd's cycle(special constraints)-O(n) time,O(1) space
Example
// JavaScript - Hash set approachfunctioncontainsDuplicate(arr){const seen =newSet();for(const val of arr){if(seen.has(val))returntrue;
seen.add(val);}returnfalse;}functionfindDuplicate(arr){// Values in range [1, n], exactly one duplicateconst seen =newSet();for(const val of arr){if(seen.has(val))return val;
seen.add(val);}}
# Python
def contains_duplicate(arr):
seen =set()for val in arr:if val in seen:returnTrue
seen.add(val)returnFalse
def find_duplicate(arr):
seen =set()for val in arr:if val in seen:return val
seen.add(val)
Note The hash set approach is the go-to. If asked for O(1) space with values in [1,n], use Floyd's tortoise and hare or index marking (negate values). Always clarify constraints: can you modify the input? What is the value range?
Note Time O(n), Space O(k) where k is unique elements. Python's Counter is a powerful shortcut. In interviews, building the map manually shows understanding. Tie-breaking: clarify with interviewer what to return if multiple elements share max frequency.
frequency countcharacter countmost common elementcounterhash map
Two Sum Pattern (Hash Map)
Syntax
For each element, check if(target - element) exists in the map.Single pass: check then insert.
Example
// JavaScriptfunctiontwoSum(nums, target){const map =newMap();for(let i =0; i < nums.length; i++){const complement = target - nums[i];if(map.has(complement)){return[map.get(complement), i];}
map.set(nums[i], i);}return[];}
# Python
def two_sum(nums, target):
seen ={}for i, num inenumerate(nums):
complement = target - num
if complement in seen:return[seen[complement], i]
seen[num]= i
return[]
Output
two_sum([2, 7, 11, 15], 9) → [0, 1]
Note Time O(n), Space O(n). The classic interview opener. Single-pass approach works because we only need one pair. Edge cases: duplicate values, negative numbers, target is double of an element. For three-sum, sort + two pointers is preferred over triple hash map lookups.
two sumhash map paircomplement searchtarget sum
Group Anagrams
Syntax
Use sorted string(or character frequency tuple)as hash map key.All anagrams produce the same key.
Example
// JavaScriptfunctiongroupAnagrams(words){const groups =newMap();for(const word of words){const key = word.split('').sort().join('');if(!groups.has(key)) groups.set(key,[]);
groups.get(key).push(word);}returnArray.from(groups.values());}
# Python
def group_anagrams(words):
groups ={}for word in words:
key =''.join(sorted(word))
groups.setdefault(key,[]).append(word)returnlist(groups.values())
Note Sorting key: O(n * k log k) where k is max word length. Frequency key alternative: O(n * k) but more code. Interviewers may ask for the optimal approach - mention the frequency-tuple key to avoid k log k sorting per word.
group anagramsanagram groupinghash map groupingsorted key
Subarray Sum Equals K
Syntax
Use prefix sum + hash map.At each index, check if(currentPrefix - k) was seen before.Store prefix sum frequencies in the map.
Example
// JavaScriptfunctionsubarraySum(nums, k){const prefixCount =newMap([[0,1]]);let prefix =0, count =0;for(const num of nums){
prefix += num;if(prefixCount.has(prefix - k)){
count += prefixCount.get(prefix - k);}
prefixCount.set(prefix,(prefixCount.get(prefix)||0)+1);}return count;}
# Python
def subarray_sum(nums, k):
prefix_count ={0:1}
prefix =0
count =0for num in nums:
prefix += num
count += prefix_count.get(prefix - k,0)
prefix_count[prefix]= prefix_count.get(prefix,0)+1return count
Note Time O(n), Space O(n). Initialize map with {0: 1} to handle subarrays starting at index 0. This pattern is reusable: subarray sum divisible by k, subarray with equal 0s and 1s. One of the most asked medium-level problems.
subarray sumprefix sum hash mapsubarray sum equals kcontiguous sum
Intersection of Collections
Syntax
Convert one collection to a set, iterate the other and check membership.For sorted arrays: use two pointers instead.
Example
// JavaScriptfunctionintersection(arr1, arr2){const set1 =newSet(arr1);const result =[];const seen =newSet();for(const val of arr2){if(set1.has(val)&&!seen.has(val)){
result.push(val);
seen.add(val);}}return result;}
# Python
def intersection(arr1, arr2):returnlist(set(arr1)&set(arr2))
# With duplicates preserved:
def intersect_with_dupes(arr1, arr2):from collections importCounter
c1, c2 =Counter(arr1),Counter(arr2)returnlist((c1 & c2).elements())
Note Set approach: O(n + m) time, O(min(n,m)) space. Sorted two-pointer approach: O(n log n + m log m) time, O(1) extra space. Ask the interviewer: unique results or preserve duplicates? Are inputs sorted?
set intersectionarray intersectioncommon elementshash set
LRU Cache Concept
Syntax
LeastRecentlyUsed cache: evict the oldest unused entry when at capacity.Implementwith:HashMap+DoublyLinkedList-Map: key → node(O(1) lookup)-DLL: maintains access order(O(1) move/remove)
Example
// JavaScript - Simplified using Map (preserves insertion order)classLRUCache{constructor(capacity){this.capacity= capacity;this.cache=newMap();}get(key){if(!this.cache.has(key))return-1;const val =this.cache.get(key);this.cache.delete(key);this.cache.set(key, val);// move to end (most recent)return val;}put(key, value){this.cache.delete(key);this.cache.set(key, value);if(this.cache.size>this.capacity){const oldest =this.cache.keys().next().value;this.cache.delete(oldest);}}}
# Python-UsingOrderedDictfrom collections importOrderedDictclassLRUCache:
def __init__(self, capacity):
self.capacity= capacity
self.cache=OrderedDict()
def get(self, key):if key not in self.cache:return-1
self.cache.move_to_end(key)return self.cache[key]
def put(self, key, value):if key in self.cache:
self.cache.move_to_end(key)
self.cache[key]= value
iflen(self.cache)> self.capacity:
self.cache.popitem(last=False)
Note Both get and put must be O(1). In a real interview, they may want the DLL implementation from scratch - practice building a Node class with prev/next pointers. This is one of the most commonly asked design questions at top companies.
classListNode:
val, next
Start at head, follow next pointers until null.
Example
// JavaScriptclassListNode{constructor(val, next =null){this.val= val;this.next= next;}}functiontraverse(head){const values =[];let current = head;while(current !==null){
values.push(current.val);
current = current.next;}return values;}
# PythonclassListNode:
def __init__(self, val=0, next=None):
self.val= val
self.next= next
def traverse(head):
values =[]
current = head
while current:
values.append(current.val)
current = current.nextreturn values
Output
1 → 2 → 3 → None
traverse(head) → [1, 2, 3]
Note Time O(n), Space O(1) for traversal itself. The dummy/sentinel node trick simplifies edge cases: create a dummy node pointing to head, return dummy.next at the end. This avoids special-casing operations on the head node.
linked list traversaliterate linked listListNodesingly linked list
Reverse a Linked List
Syntax
Iterative: maintain prev, current, next pointers.At each step: save next, point current.next to prev, advance both.
Example
// JavaScript - IterativefunctionreverseList(head){let prev =null, current = head;while(current !==null){const next = current.next;
current.next= prev;
prev = current;
current = next;}return prev;}// RecursivefunctionreverseListRecursive(head){if(!head ||!head.next)return head;const newHead =reverseListRecursive(head.next);
head.next.next= head;
head.next=null;return newHead;}
# Python-Iterative
def reverse_list(head):
prev, current =None, head
while current:
nxt = current.next
current.next= prev
prev = current
current = nxt
return prev
# Recursive
def reverse_list_recursive(head):if not head or not head.next:return head
new_head =reverse_list_recursive(head.next)
head.next.next= head
head.next=Nonereturn new_head
Output
1→2→3→4 becomes 4→3→2→1
Note Iterative: O(n) time, O(1) space. Recursive: O(n) time, O(n) stack space. This is the single most common linked list question. Draw the pointer changes on paper. Follow-up: reverse a sublist from position m to n.
Useslow(1 step) and fast(2 steps) pointers.If they meet → cycle exists.To find cycle start: reset one pointer to head, move both at 1 step.
Example
// JavaScriptfunctionhasCycle(head){let slow = head, fast = head;while(fast && fast.next){
slow = slow.next;
fast = fast.next.next;if(slow === fast)returntrue;}returnfalse;}functionfindCycleStart(head){let slow = head, fast = head;while(fast && fast.next){
slow = slow.next;
fast = fast.next.next;if(slow === fast){
slow = head;while(slow !== fast){
slow = slow.next;
fast = fast.next;}return slow;// cycle start node}}returnnull;}
# Python
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.nextif slow is fast:returnTruereturnFalse
def find_cycle_start(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.nextif slow is fast:
slow = head
while slow is not fast:
slow = slow.next
fast = fast.nextreturn slow
returnNone
Output
Has cycle: True/False
Cycle start: node where cycle begins
Note Time O(n), Space O(1). The math behind finding the cycle start: when they meet, the distance from head to cycle start equals the distance from meeting point to cycle start (going around). Always use 'is' (identity) not '==' (equality) for node comparison.
detect cycleFloyd's algorithmtortoise and harecycle detectionlinked list cycle
Find Middle of Linked List
Syntax
Slow pointer moves 1 step, fast moves 2 steps.When fast reaches end, slow is at the middle.
Example
// JavaScriptfunctionfindMiddle(head){let slow = head, fast = head;while(fast && fast.next){
slow = slow.next;
fast = fast.next.next;}return slow;}
# Python
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.nextreturn slow
Output
1→2→3→4→5 → middle is 3
1→2→3→4 → middle is 3 (second of two middles)
Note Time O(n), Space O(1). For even-length lists, this returns the second middle node. To get the first middle, use: while fast.next and fast.next.next. This technique is a building block for merge sort on linked lists and palindrome checking.
find middlemiddle nodeslow fast pointerlinked list middle
Merge Two Sorted Linked Lists
Syntax
Use a dummy node.Compare heads of both lists, attach the smaller one.Advance the pointer of the list you took from.
Note Time O(n + m), Space O(1). The dummy node pattern eliminates edge cases for choosing the initial head. Follow-up: merge k sorted lists - use a min-heap for O(n log k) or divide and conquer.
merge sorted listsmerge two listsdummy nodesorted merge
Remove N-th Node from End
Syntax
Use two pointers with a gap of n between them.Advance both until the lead pointer hits the end.The trailing pointer is right before the target.
Example
// JavaScriptfunctionremoveNthFromEnd(head, n){const dummy =newListNode(0, head);let lead = dummy, trail = dummy;for(let i =0; i <= n; i++) lead = lead.next;while(lead){
lead = lead.next;
trail = trail.next;}
trail.next= trail.next.next;return dummy.next;}
# Python
def remove_nth_from_end(head, n):
dummy =ListNode(0, head)
lead = trail = dummy
for _ inrange(n +1):
lead = lead.nextwhile lead:
lead = lead.next
trail = trail.next
trail.next= trail.next.nextreturn dummy.next
Output
1→2→3→4→5, n=2 → 1→2→3→5 (removed 4)
Note Time O(n), Space O(1), single pass. The dummy node handles removing the head itself (when n equals list length). Always advance lead n+1 times so trail stops one node before the target.
remove nth from endtwo pointer gaplinked list removalsingle pass removal
Palindrome Check for Linked List
Syntax
1.Find the middle using slow/fast pointers
2.Reverse the second half
3.Compare first half with reversed second half
4.(Optional)Restore the list
Example
// JavaScriptfunctionisPalindrome(head){let slow = head, fast = head;while(fast && fast.next){
slow = slow.next;
fast = fast.next.next;}// Reverse second halflet prev =null;while(slow){const next = slow.next;
slow.next= prev;
prev = slow;
slow = next;}// Compare halveslet left = head, right = prev;while(right){if(left.val!== right.val)returnfalse;
left = left.next;
right = right.next;}returntrue;}
# Python
def is_palindrome(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev =Nonewhile slow:
slow.next, prev, slow = prev, slow, slow.next
left, right = head, prev
while right:if left.val!= right.val:returnFalse
left, right = left.next, right.nextreturnTrue
Output
1→2→3→2→1 → True
1→2→3→4 → False
Note Time O(n), Space O(1). Combines three linked list skills: find middle, reverse, and compare. An O(n) space alternative: copy values to an array and check palindrome there. Interviewers prefer the O(1) space approach.
palindrome linked listcheck palindromereverse halflinked list palindrome
Note Time O(n), Space O(n). Edge cases: empty string (valid), single character (invalid), only opening brackets (invalid). This is the quintessential stack problem - if you see matching/nesting, think stack.
Maintain a secondary stack that tracks the current minimum.When pushing, also push to min stack if value <= current min.When popping, also pop from min stack if value equals current min.
Note All operations O(1) time, O(n) extra space for the min stack. The trick: each entry in min_stack stores the minimum at that height of the main stack. Alternative: store (value, currentMin) tuples in one stack.
min stackminimum stackstack with getMinO(1) minimum
Evaluate Reverse Polish Notation
Syntax
Process tokens left to right.Numbers: push onto stack.Operators: pop two operands, apply operator, push result.
Example
// JavaScriptfunctionevalRPN(tokens){const stack =[];const ops ={'+':(a, b)=> a + b,'-':(a, b)=> a - b,'*':(a, b)=> a * b,'/':(a, b)=>Math.trunc(a / b),};for(const token of tokens){if(token in ops){const b = stack.pop(), a = stack.pop();
stack.push(ops[token](a, b));}else{
stack.push(Number(token));}}return stack[0];}
# Python
def eval_rpn(tokens):
stack =[]
ops ={'+','-','*','/'}for token in tokens:if token in ops:
b, a = stack.pop(), stack.pop()if token =='+': stack.append(a + b)
elif token =='-': stack.append(a - b)
elif token =='*': stack.append(a * b)else: stack.append(int(a / b)) # truncate toward zero
else:
stack.append(int(token))return stack[0]
Output
evalRPN(['2','1','+','3','*']) → 9
((2+1)*3 = 9)
Note Time O(n), Space O(n). Watch out: division truncates toward zero (not floor). Order matters: first popped is right operand, second popped is left. For infix to postfix conversion, use the Shunting Yard algorithm.
Traversefrom right to left(or left to right).Maintain a decreasing stack.For each element, pop smaller elements - the top is the next greater.
Example
// JavaScriptfunctionnextGreaterElements(arr){const result =newArray(arr.length).fill(-1);const stack =[];// stores indicesfor(let i =0; i < arr.length; i++){while(stack.length>0&& arr[stack[stack.length-1]]< arr[i]){
result[stack.pop()]= arr[i];}
stack.push(i);}return result;}
# Python
def next_greater_elements(arr):
result =[-1]*len(arr)
stack =[] # stores indices
for i inrange(len(arr)):while stack and arr[stack[-1]]< arr[i]:
result[stack.pop()]= arr[i]
stack.append(i)return result
Note Time O(n), Space O(n). Each element is pushed and popped at most once. Used in: stock span, daily temperatures, histogram problems. For circular arrays, iterate through the array twice (use i % n).
next greater elementmonotonic stackdaily temperaturesstock span
BFS with Queue
Syntax
Use a queue(FIFO)for breadth-first traversal.Process level by level.Enqueue neighbors/children, dequeue to process.
Example
// JavaScript - BFS level order traversal of binary treefunctionlevelOrder(root){if(!root)return[];const result =[];const queue =[root];while(queue.length>0){const levelSize = queue.length;const level =[];for(let i =0; i < levelSize; i++){const node = queue.shift();
level.push(node.val);if(node.left) queue.push(node.left);if(node.right) queue.push(node.right);}
result.push(level);}return result;}
# Pythonfrom collections import deque
def level_order(root):if not root:return[]
result =[]
queue =deque([root])while queue:
level =[]for _ inrange(len(queue)):
node = queue.popleft()
level.append(node.val)if node.left:
queue.append(node.left)if node.right:
queue.append(node.right)
result.append(level)return result
Output
Tree: 3
/ \
9 20
→ [[3], [9, 20]]
Note Time O(n), Space O(n). Use deque in Python for O(1) popleft - list.pop(0) is O(n). The 'capture level size' trick (for loop with current queue length) lets you process one level at a time. BFS is the go-to for shortest path in unweighted graphs.
BFS queuelevel order traversalbreadth first searchqueue
Monotonic Stack Pattern
Syntax
A stack that maintains elements in sorted order(increasing or decreasing).Before pushing, pop all elements that violate the ordering.Usedfor: next greater/smaller, largest rectangle in histogram.
Example
// JavaScript - Largest rectangle in histogramfunctionlargestRectangle(heights){const stack =[];// indices of increasing heightslet maxArea =0;for(let i =0; i <= heights.length; i++){const h = i < heights.length? heights[i]:0;while(stack.length>0&& h < heights[stack[stack.length-1]]){const height = heights[stack.pop()];const width = stack.length===0? i : i - stack[stack.length-1]-1;
maxArea =Math.max(maxArea, height * width);}
stack.push(i);}return maxArea;}
# Python
def largest_rectangle(heights):
stack =[]
max_area =0for i inrange(len(heights)+1):
h = heights[i]if i <len(heights)else0while stack and h < heights[stack[-1]]:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1]-1
max_area =max(max_area, height * width)
stack.append(i)return max_area
Note Time O(n), Space O(n). The sentinel value (appending 0 at the end) forces all remaining bars to be processed. This is a hard problem but the monotonic stack template is reusable. Variant: maximal rectangle in a binary matrix applies this per row.
Visit left subtree → process node → visit right subtree.ForBST: inorder gives sorted order.
Example
// JavaScriptfunctioninorder(root){const result =[];functiondfs(node){if(!node)return;dfs(node.left);
result.push(node.val);dfs(node.right);}dfs(root);return result;}// Iterative with stackfunctioninorderIterative(root){const result =[], stack =[];let current = root;while(current || stack.length){while(current){
stack.push(current);
current = current.left;}
current = stack.pop();
result.push(current.val);
current = current.right;}return result;}
# Python
def inorder(root):
result =[]
def dfs(node):if not node:returndfs(node.left)
result.append(node.val)dfs(node.right)dfs(root)return result
Output
Tree: 4
/ \
2 6
/ \
1 3
Inorder: [1, 2, 3, 4, 6]
Note Time O(n), Space O(h) where h = tree height. For balanced tree h = log n, for skewed h = n. Know both recursive and iterative versions - interviewers may ask for iterative. Inorder on BST is a common trick to verify sorted property.
Preorder:Root → Left → Right(useful for copying/serializing trees)Postorder:Left → Right → Root(useful for deletion, calculating heights)
Example
// JavaScriptfunctionpreorder(root){const result =[];functiondfs(node){if(!node)return;
result.push(node.val);// process before childrendfs(node.left);dfs(node.right);}dfs(root);return result;}functionpostorder(root){const result =[];functiondfs(node){if(!node)return;dfs(node.left);dfs(node.right);
result.push(node.val);// process after children}dfs(root);return result;}
# Python
def preorder(root):if not root:return[]return[root.val]+preorder(root.left)+preorder(root.right)
def postorder(root):if not root:return[]returnpostorder(root.left)+postorder(root.right)+[root.val]
Note Both O(n) time, O(h) space. Preorder is the order you would write nodes in serialization. Postorder is natural for bottom-up computations (e.g., calculating subtree sizes or heights). Interviewers may ask: given preorder + inorder, reconstruct the tree.
Note Time O(n), Space O(w) where w = max width of tree. Variants: zigzag level order (alternate direction), right side view (last node per level), average of levels. BFS is the natural tool whenever you need level-by-level information.
level orderBFS treebreadth first treetree by level
Maximum Depth of Binary Tree
Syntax
Recursive: depth =1+max(depth(left),depth(right))Basecase:null node has depth 0.
Example
// JavaScriptfunctionmaxDepth(root){if(!root)return0;return1+Math.max(maxDepth(root.left),maxDepth(root.right));}
# Python
def max_depth(root):if not root:return0return1+max(max_depth(root.left),max_depth(root.right))
Output
Tree: 3
/ \
9 20
/ \
15 7
→ depth = 3
Note Time O(n), Space O(h). One of the simplest tree recursion problems - great for warming up. Iterative BFS approach: count number of levels. Follow-up: minimum depth (BFS is more efficient - stops at first leaf).
max depthtree heightbinary tree depthrecursive depth
Validate Binary Search Tree
Syntax
Pass down valid range(min, max) at each node.Left child must be in(min, node.val).Right child must be in(node.val, max).
Example
// JavaScriptfunctionisValidBST(root){functionvalidate(node, min, max){if(!node)returntrue;if(node.val<= min || node.val>= max)returnfalse;returnvalidate(node.left, min, node.val)&&validate(node.right, node.val, max);}returnvalidate(root,-Infinity,Infinity);}
# Python
def is_valid_bst(root):
def validate(node, lo, hi):if not node:returnTrueif node.val<= lo or node.val>= hi:returnFalsereturnvalidate(node.left, lo, node.val) and \
validate(node.right, node.val, hi)returnvalidate(root,float('-inf'),float('inf'))
Output
Valid BST: 5 Invalid: 5
/ \ / \
3 7 3 7
/ \ / \
1 4 1 6 ← 6 > 5 but in left subtree
Note Time O(n), Space O(h). Common mistake: only checking node against its parent. The range-based approach catches nodes that violate a grandparent constraint. Alternative: inorder traversal and verify the sequence is strictly increasing.
If current node is p or q,return it.Recurse left and right.If both sides return non-null, current node is the LCA.Otherwisereturn whichever side is non-null.
Example
// JavaScriptfunctionlowestCommonAncestor(root, p, q){if(!root || root === p || root === q)return root;const left =lowestCommonAncestor(root.left, p, q);const right =lowestCommonAncestor(root.right, p, q);if(left && right)return root;return left || right;}
# Python
def lowest_common_ancestor(root, p, q):if not root or root == p or root == q:return root
left =lowest_common_ancestor(root.left, p, q)
right =lowest_common_ancestor(root.right, p, q)if left and right:return root
return left or right
Note Time O(n), Space O(h). For BST: exploit sorted property - if both values < node, go left; if both > node, go right; otherwise current node is LCA. This is an O(h) optimization for BSTs. Always clarify: can a node be its own ancestor?
lowest common ancestorLCAtree ancestorcommon parent
Path Sum
Syntax
Subtract current node value from target as you recurse.At a leaf, check if remaining target equals the leaf value.
Example
// JavaScript - Has path with target sum (root to leaf)functionhasPathSum(root, target){if(!root)returnfalse;if(!root.left&&!root.right)return root.val=== target;returnhasPathSum(root.left, target - root.val)||hasPathSum(root.right, target - root.val);}
# Python
def has_path_sum(root, target):if not root:returnFalseif not root.left and not root.right:return root.val== target
returnhas_path_sum(root.left, target - root.val) or \
has_path_sum(root.right, target - root.val)
Note Time O(n), Space O(h). Must reach a leaf - internal nodes with matching sum do not count. Variants: return all paths (collect paths in a list), path sum III (any downward path, use prefix sum + hash map). Clarify: root-to-leaf or any path?
path sumroot to leaftree pathtarget sum tree
Serialize & Deserialize Binary Tree (Concept)
Syntax
Serialize:BFS or preorder DFS, use a marker fornull nodes.Deserialize: reconstruct from the serialized format using same traversal order.
Example
// JavaScript - Preorder approachfunctionserialize(root){const parts =[];functiondfs(node){if(!node){ parts.push('X');return;}
parts.push(String(node.val));dfs(node.left);dfs(node.right);}dfs(root);return parts.join(',');}functiondeserialize(data){const vals = data.split(',');let idx =0;functiondfs(){if(vals[idx]==='X'){ idx++;returnnull;}const node =newTreeNode(Number(vals[idx++]));
node.left=dfs();
node.right=dfs();return node;}returndfs();}
# Python
def serialize(root):
parts =[]
def dfs(node):if not node:
parts.append('X')return
parts.append(str(node.val))dfs(node.left)dfs(node.right)dfs(root)return','.join(parts)
def deserialize(data):
vals =iter(data.split(','))
def dfs():
val =next(vals)if val =='X':returnNone
node =TreeNode(int(val))
node.left=dfs()
node.right=dfs()return node
returndfs()
Note Time O(n), Space O(n). The null marker is essential - without it you cannot reconstruct the tree uniquely. BFS approach works too: serialize level by level. This is a common hard interview question. Practice the deserialization - it is the tricky part.
serialize treedeserialize treeencode treetree to string
Note Space: O(V + E). Adjacency list is preferred over adjacency matrix for sparse graphs (most interview problems). Always ask: directed or undirected? Weighted or unweighted? Can there be self-loops or parallel edges?
adjacency listgraph representationbuild graphedge list to graph
Graph BFS
Syntax
Queue+ visited set.Startfrom source, explore all neighbors at distance 1, then distance 2, etc.Guarantees shortest path in unweighted graphs.
Example
// JavaScriptfunctionbfs(graph, start){const visited =newSet([start]);const queue =[start];const order =[];while(queue.length>0){const node = queue.shift();
order.push(node);for(const neighbor of(graph.get(node)||[])){if(!visited.has(neighbor)){
visited.add(neighbor);
queue.push(neighbor);}}}return order;}
# Pythonfrom collections import deque
def bfs(graph, start):
visited ={start}
queue =deque([start])
order =[]while queue:
node = queue.popleft()
order.append(node)for neighbor in graph.get(node,[]):if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)return order
Output
bfs(graph, 0) → [0, 1, 2, 3]
Note Time O(V + E), Space O(V). Mark visited WHEN ENQUEUING, not when dequeuing - this prevents duplicate queue entries. For shortest path distance, track a distance array. BFS on a grid: treat each cell as a node with 4 directional neighbors.
graph BFSbreadth first search graphshortest path unweightedBFS traversal
Graph DFS
Syntax
Stack(or recursion)+ visited set.Goas deep as possible before backtracking.Usefulfor: connectivity, cycle detection, topological sort.
Example
// JavaScript - Iterativefunctiondfs(graph, start){const visited =newSet();const stack =[start];const order =[];while(stack.length>0){const node = stack.pop();if(visited.has(node))continue;
visited.add(node);
order.push(node);for(const neighbor of(graph.get(node)||[])){if(!visited.has(neighbor)) stack.push(neighbor);}}return order;}
# Python-Recursive
def dfs(graph, start, visited=None):if visited isNone:
visited =set()
visited.add(start)
order =[start]for neighbor in graph.get(start,[]):if neighbor not in visited:
order.extend(dfs(graph, neighbor, visited))return order
Output
dfs(graph, 0) → [0, 2, 3, 1] (one possible order)
Note Time O(V + E), Space O(V). Recursive DFS risks stack overflow on very deep graphs - iterative is safer for large inputs. DFS visit order depends on neighbor iteration order. For interview purposes, both iterative and recursive should be in your toolkit.
graph DFSdepth first search graphDFS traversalrecursive DFS
Detect Cycle in Graph
Syntax
Undirected:DFS-if we visit a node already visited(and it's not the parent), cycle exists.Directed:Track3 states - unvisited,in current path, completed.
Example
// JavaScript - Directed graph cycle detectionfunctionhasCycleDirected(graph, numNodes){constWHITE=0,GRAY=1,BLACK=2;const color =newArray(numNodes).fill(WHITE);functiondfs(node){
color[node]=GRAY;// in current pathfor(const neighbor of(graph.get(node)||[])){if(color[neighbor]===GRAY)returntrue;// back edge = cycleif(color[neighbor]===WHITE&&dfs(neighbor))returntrue;}
color[node]=BLACK;// completedreturnfalse;}for(let i =0; i < numNodes; i++){if(color[i]===WHITE&&dfs(i))returntrue;}returnfalse;}
# Python-Directed graph
def has_cycle_directed(graph, num_nodes):WHITE,GRAY,BLACK=0,1,2
color =[WHITE]* num_nodes
def dfs(node):
color[node]=GRAYfor neighbor in graph.get(node,[]):if color[neighbor]==GRAY:returnTrueif color[neighbor]==WHITE and dfs(neighbor):returnTrue
color[node]=BLACKreturnFalsereturnany(color[i]==WHITE and dfs(i)for i inrange(num_nodes))
Output
Cycle: 0→1→2→0 → True
No cycle: 0→1→2 → False
Note Time O(V + E), Space O(V). The three-color technique (white/gray/black) is standard for directed graphs. Gray = currently on the recursion stack. A back edge to a gray node proves a cycle. For undirected graphs, simply track parent to avoid false positives.
Note Time O(V + E), Space O(V). If the result has fewer nodes than the graph, a cycle exists (useful for course schedule problems). Kahn's is easier to implement and also detects cycles. Multiple valid orderings may exist.
RunBFS or DFSfrom each unvisited node.Each run discovers one connected component.Count the number of runs = number of components.
Example
// JavaScriptfunctioncountComponents(n, edges){const graph =newMap();for(let i =0; i < n; i++) graph.set(i,[]);for(const[u, v]of edges){
graph.get(u).push(v);
graph.get(v).push(u);}const visited =newSet();let components =0;for(let i =0; i < n; i++){if(!visited.has(i)){
components++;const queue =[i];
visited.add(i);while(queue.length){const node = queue.shift();for(const nb of graph.get(node)){if(!visited.has(nb)){
visited.add(nb);
queue.push(nb);}}}}}return components;}
# Python
def count_components(n, edges):from collections import defaultdict, deque
graph =defaultdict(list)for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited =set()
components =0for i inrange(n):if i not in visited:
components +=1
queue =deque([i])
visited.add(i)while queue:
node = queue.popleft()for nb in graph[node]:if nb not in visited:
visited.add(nb)
queue.append(nb)return components
Output
n=5, edges=[[0,1],[1,2],[3,4]] → 2 components ({0,1,2} and {3,4})
Note Time O(V + E), Space O(V). Alternative: Union-Find achieves the same result and is better for dynamic connectivity. This pattern is the basis for 'number of islands' and 'number of provinces' problems.
connected componentsnumber of componentsgraph connectivityunion find
Shortest Path - Dijkstra's Concept
Syntax
For weighted graphs with non-negative edges.Use a min-heap(priority queue).Greedily expand the nearest unvisited node.
Example
// JavaScript - using a simple priority queue approachfunctiondijkstra(graph, start, n){const dist =newArray(n).fill(Infinity);
dist[start]=0;// Min-heap: [distance, node]const pq =[[0, start]];while(pq.length>0){
pq.sort((a, b)=> a[0]- b[0]);// simplified; use real heapconst[d, u]= pq.shift();if(d > dist[u])continue;for(const[v, w]of(graph.get(u)||[])){if(dist[u]+ w < dist[v]){
dist[v]= dist[u]+ w;
pq.push([dist[v], v]);}}}return dist;}
# Pythonimport heapq
def dijkstra(graph, start, n):
dist =[float('inf')]* n
dist[start]=0
pq =[(0, start)] # (distance, node)while pq:
d, u = heapq.heappop(pq)if d > dist[u]:continuefor v, w in graph.get(u,[]):if dist[u]+ w < dist[v]:
dist[v]= dist[u]+ w
heapq.heappush(pq,(dist[v], v))return dist
Output
Graph: 0→1(4), 0→2(1), 2→1(2)
dijkstra(graph, 0) → [0, 3, 1] (shortest to node 1 is via node 2)
Note Time O((V + E) log V) with binary heap. Does NOT work with negative edge weights (use Bellman-Ford for that). The 'if d > dist[u]: continue' line is the lazy deletion optimization - critical for performance. For unweighted graphs, BFS is simpler and sufficient.
Treat grid as a graph.Each'1' cell is a node, connected to 4-directional '1' neighbors.BFS or DFSfrom each unvisited '1'.Count how many searches you start.
Example
// JavaScriptfunctionnumIslands(grid){if(!grid.length)return0;const rows = grid.length, cols = grid[0].length;let count =0;functiondfs(r, c){if(r <0|| r >= rows || c <0|| c >= cols || grid[r][c]!=='1')return;
grid[r][c]='0';// mark visiteddfs(r +1, c);dfs(r -1, c);dfs(r, c +1);dfs(r, c -1);}for(let r =0; r < rows; r++){for(let c =0; c < cols; c++){if(grid[r][c]==='1'){
count++;dfs(r, c);}}}return count;}
# Python
def num_islands(grid):if not grid:return0
rows, cols =len(grid),len(grid[0])
count =0
def dfs(r, c):if r <0 or r >= rows or c <0 or c >= cols or grid[r][c]!='1':return
grid[r][c]='0'dfs(r +1, c);dfs(r -1, c)dfs(r, c +1);dfs(r, c -1)for r inrange(rows):for c inrange(cols):if grid[r][c]=='1':
count +=1dfs(r, c)return count
Output
Grid:
1 1 0 0
1 0 0 1
0 0 1 1
→ 3 islands
Note Time O(rows * cols), Space O(rows * cols) worst case for recursion stack. Modifying the input grid to mark visited saves space but is destructive - ask the interviewer if that is acceptable. BFS alternative avoids deep recursion. Variants: max area of island, surrounded regions.
number of islandsgrid DFSgrid BFSisland countingflood fill
Repeatedly swap adjacent elements if out of order.After each pass, the largest unsorted element 'bubbles' to its correct position.
Example
// JavaScriptfunctionbubbleSort(arr){const n = arr.length;for(let i =0; i < n -1; i++){let swapped =false;for(let j =0; j < n -1- i; j++){if(arr[j]> arr[j +1]){[arr[j], arr[j +1]]=[arr[j +1], arr[j]];
swapped =true;}}if(!swapped)break;// already sorted}return arr;}
# Python
def bubble_sort(arr):
n =len(arr)for i inrange(n -1):
swapped =Falsefor j inrange(n -1- i):if arr[j]> arr[j +1]:
arr[j], arr[j +1]= arr[j +1], arr[j]
swapped =Trueif not swapped:breakreturn arr
Output
bubble_sort([5,3,8,1,2]) → [1,2,3,5,8]
Note Time: O(n^2) average/worst, O(n) best (already sorted with early exit). Space: O(1). Stable sort. Never use in production - only know it for interviews. The early termination optimization (swapped flag) is worth mentioning.
Note Time: O(n^2) all cases. Space: O(1). NOT stable (swapping can change relative order of equal elements). Minimizes the number of swaps (at most n-1), which can matter when writes are expensive.
Build sorted portion from left.Take next unsorted element, insert it into the correct position in the sorted portion.
Example
// JavaScriptfunctioninsertionSort(arr){for(let i =1; i < arr.length; i++){const key = arr[i];let j = i -1;while(j >=0&& arr[j]> key){
arr[j +1]= arr[j];
j--;}
arr[j +1]= key;}return arr;}
# Python
def insertion_sort(arr):for i inrange(1,len(arr)):
key = arr[i]
j = i -1while j >=0 and arr[j]> key:
arr[j +1]= arr[j]
j -=1
arr[j +1]= key
return arr
Output
insertion_sort([5,2,4,6,1,3]) → [1,2,3,4,5,6]
Note Time: O(n^2) worst/avg, O(n) best (nearly sorted). Space: O(1). Stable. Excellent for small arrays (< ~20 elements) and nearly sorted data. TimSort (Python/Java default) uses insertion sort for small subarrays within merge sort.
Note Time: O(n log n) always. Space: O(n). Stable. Guaranteed O(n log n) regardless of input - unlike quicksort. Preferred for linked lists (no random access needed, O(1) space merge). The merge function is reusable in many problems.
merge sortdivide and conquer sortstable sortguaranteed n log n
Quick Sort
Syntax
Pick a pivot.Partition: elements < pivot go left,>= pivot go right.Recursively sort left and right partitions.
Example
// JavaScriptfunctionquickSort(arr, lo =0, hi = arr.length-1){if(lo >= hi)return arr;const pivotIdx =partition(arr, lo, hi);quickSort(arr, lo, pivotIdx -1);quickSort(arr, pivotIdx +1, hi);return arr;}functionpartition(arr, lo, hi){const pivot = arr[hi];let i = lo;for(let j = lo; j < hi; j++){if(arr[j]< pivot){[arr[i], arr[j]]=[arr[j], arr[i]];
i++;}}[arr[i], arr[hi]]=[arr[hi], arr[i]];return i;}
# Python
def quick_sort(arr, lo=0, hi=None):if hi isNone:
hi =len(arr)-1if lo >= hi:return arr
pivot_idx =partition(arr, lo, hi)quick_sort(arr, lo, pivot_idx -1)quick_sort(arr, pivot_idx +1, hi)return arr
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo
for j inrange(lo, hi):if arr[j]< pivot:
arr[i], arr[j]= arr[j], arr[i]
i +=1
arr[i], arr[hi]= arr[hi], arr[i]return i
Output
quick_sort([10,7,8,9,1,5]) → [1,5,7,8,9,10]
Note Time: O(n log n) avg, O(n^2) worst (already sorted with bad pivot). Space: O(log n) avg stack. NOT stable. Randomizing the pivot avoids worst case. In practice, quicksort is often faster than merge sort due to cache locality. Lomuto partition (shown) is simpler; Hoare partition is faster.
Count occurrences of each value.Build output array from the counts.Only works when the range of values is bounded.
Example
// JavaScriptfunctioncountingSort(arr, maxVal){const count =newArray(maxVal +1).fill(0);for(const val of arr) count[val]++;const result =[];for(let i =0; i <= maxVal; i++){for(let j =0; j < count[i]; j++){
result.push(i);}}return result;}
# Python
def counting_sort(arr, max_val):
count =[0]*(max_val +1)for val in arr:
count[val]+=1
result =[]for i inrange(max_val +1):
result.extend([i]* count[i])return result
Note Time: O(n + k) where k = value range. Space: O(k). Beats comparison-based O(n log n) when k is small. Not suitable for large ranges or floating-point numbers. Radix sort extends this to handle larger ranges digit by digit.
counting sortnon-comparison sortinteger sortbounded range sort
When to Use Which Sort
Syntax
Smalln(<20): insertion sort
General purpose: merge sort(stable) or quicksort(fast avg)Bounded integers: counting/radix sort
Nearly sorted: insertion sort
Linked lists: merge sort
Stability needed: merge sort or TimSort
Example
// JavaScript - just use built-in for interviewsconst nums =[5,3,8,1];
nums.sort((a, b)=> a - b);// ALWAYS pass comparator for numbers!// Without comparator, JS sorts lexicographically: [1, 3, 5, 8]// But [10, 9, 80].sort() → [10, 80, 9] - WRONG!
# Python
nums =[5,3,8,1]
nums.sort() # in-place, returns None
sorted_nums =sorted(nums) # returns new list
# Custom:sorted(items, key=lambda x: x[1])
Note In interviews, use the built-in sort unless asked to implement one. JS trap: .sort() without a comparator converts elements to strings - always pass (a,b) => a-b for numbers. Know the trade-offs between sorts for the 'which sort would you use' question.
which sort to usesorting comparisonbuilt-in sortsort comparatorTimSort
Sort Stability
Syntax
A stable sort preserves the relative order of elements with equal keys.Stable: merge sort, insertion sort, bubble sort,TimSort.Unstable: quicksort, selection sort, heap sort.
Example
// JavaScript - Stability matters for multi-key sortingconst students =[{ name:'Alice', grade:'B'},{ name:'Bob', grade:'A'},{ name:'Carol', grade:'B'},{ name:'Dave', grade:'A'},];// Sort by grade - stable sort keeps Alice before Carol (both B)
students.sort((a, b)=> a.grade.localeCompare(b.grade));// Result: Bob, Dave, Alice, Carol (A's first, original order preserved)
# Python
students =[('Alice','B'),('Bob','A'),('Carol','B'),('Dave','A')]
students.sort(key=lambda x: x[1])
# [('Bob','A'),('Dave','A'),('Alice','B'),('Carol','B')]
Output
Stable: equal elements keep original relative order.
Unstable: equal elements may be reordered.
Note Stability matters when sorting by multiple criteria (e.g., sort by grade, then by name within same grade). Python's sort is guaranteed stable. JS sort stability was implementation-dependent before ES2019 but is now required to be stable in the spec.
sort stabilitystable sortunstable sortmulti-key sortrelative order
lo =0, hi = n -1while lo <= hi:
mid = lo +(hi - lo)// 2if found:return mid
if target > arr[mid]: lo = mid +1else: hi = mid -1return-1(not found)
Example
// JavaScriptfunctionsearch(arr, target){let lo =0, hi = arr.length-1;while(lo <= hi){const mid = lo +Math.floor((hi - lo)/2);if(arr[mid]=== target)return mid;if(arr[mid]< target) lo = mid +1;else hi = mid -1;}return-1;}
# Python
def search(arr, target):
lo, hi =0,len(arr)-1while lo <= hi:
mid = lo +(hi - lo)// 2if arr[mid]== target:return mid
elif arr[mid]< target:
lo = mid +1else:
hi = mid -1return-1
Output
search([1,3,5,7,9,11,13], 9) → 4
Note Time O(log n), Space O(1). Use lo <= hi for exact match search. After the loop, lo is the insertion point (where target would go). This is equivalent to Python's bisect_left when target is not found. Memorize this template cold.
Array was sorted then rotated.One half is always sorted.Determine which half is sorted, check if target isin that half.
Example
// JavaScriptfunctionsearchRotated(arr, target){let lo =0, hi = arr.length-1;while(lo <= hi){const mid = lo +Math.floor((hi - lo)/2);if(arr[mid]=== target)return mid;// Left half is sortedif(arr[lo]<= arr[mid]){if(target >= arr[lo]&& target < arr[mid]) hi = mid -1;else lo = mid +1;}else{// Right half is sortedif(target > arr[mid]&& target <= arr[hi]) lo = mid +1;else hi = mid -1;}}return-1;}
# Python
def search_rotated(arr, target):
lo, hi =0,len(arr)-1while lo <= hi:
mid = lo +(hi - lo)// 2if arr[mid]== target:return mid
if arr[lo]<= arr[mid]: # left half sorted
if arr[lo]<= target < arr[mid]:
hi = mid -1else:
lo = mid +1else: # right half sorted
if arr[mid]< target <= arr[hi]:
lo = mid +1else:
hi = mid -1return-1
Output
search_rotated([4,5,6,7,0,1,2], 0) → 4
Note Time O(log n). Key insight: at least one half is always sorted after rotation. The condition arr[lo] <= arr[mid] determines which half. Edge case: duplicates make worst case O(n) since you cannot determine the sorted half. Very commonly asked.
Two binary searches: one for leftmost occurrence, one for rightmost.Leftmost: when found, keep searching left(hi = mid -1).Rightmost: when found, keep searching right(lo = mid +1).
Example
// JavaScriptfunctionsearchRange(arr, target){return[findFirst(arr, target),findLast(arr, target)];}functionfindFirst(arr, target){let lo =0, hi = arr.length-1, result =-1;while(lo <= hi){const mid = lo +Math.floor((hi - lo)/2);if(arr[mid]=== target){ result = mid; hi = mid -1;}elseif(arr[mid]< target) lo = mid +1;else hi = mid -1;}return result;}functionfindLast(arr, target){let lo =0, hi = arr.length-1, result =-1;while(lo <= hi){const mid = lo +Math.floor((hi - lo)/2);if(arr[mid]=== target){ result = mid; lo = mid +1;}elseif(arr[mid]< target) lo = mid +1;else hi = mid -1;}return result;}
# Python
def search_range(arr, target):
def find_bound(is_left):
lo, hi, result =0,len(arr)-1,-1while lo <= hi:
mid = lo +(hi - lo)// 2if arr[mid]== target:
result = mid
if is_left:
hi = mid -1else:
lo = mid +1
elif arr[mid]< target:
lo = mid +1else:
hi = mid -1return result
return[find_bound(True),find_bound(False)]
Output
search_range([5,7,7,8,8,10], 8) → [3, 4]
Note Time O(log n) for each search, O(log n) total. This is essentially bisect_left and bisect_right in Python. The count of target = last - first + 1. Follow-up: can also be used to count occurrences in a sorted array in O(log n).
first and last positionleftmost binary searchrightmost binary searchbisect left right
Search Insert Position
Syntax
Find the index where target would be inserted to keep array sorted.Thisis the standard binary search - when target is not found, lo is the answer.
Example
// JavaScriptfunctionsearchInsert(arr, target){let lo =0, hi = arr.length-1;while(lo <= hi){const mid = lo +Math.floor((hi - lo)/2);if(arr[mid]=== target)return mid;if(arr[mid]< target) lo = mid +1;else hi = mid -1;}return lo;// insertion point}
# Pythonimport bisect
def search_insert(arr, target):
lo, hi =0,len(arr)-1while lo <= hi:
mid = lo +(hi - lo)// 2if arr[mid]== target:return mid
elif arr[mid]< target:
lo = mid +1else:
hi = mid -1return lo
# Or simply: bisect.bisect_left(arr, target)
Note Time O(log n). After the while loop exits, lo == hi + 1 and lo is exactly where target belongs. This is equivalent to bisect_left in Python. Understanding why lo is the insertion point deepens your binary search intuition.
A peak is greater than its neighbors.Binary search: compare mid with mid+1.If mid < mid+1, peak is to the right.Otherwise, peak is to the left(or mid itself).
Example
// JavaScriptfunctionfindPeak(arr){let lo =0, hi = arr.length-1;while(lo < hi){const mid = lo +Math.floor((hi - lo)/2);if(arr[mid]< arr[mid +1]){
lo = mid +1;// peak is to the right}else{
hi = mid;// mid could be the peak}}return lo;// lo === hi, pointing to a peak}
# Python
def find_peak(arr):
lo, hi =0,len(arr)-1while lo < hi:
mid = lo +(hi - lo)// 2if arr[mid]< arr[mid +1]:
lo = mid +1else:
hi = mid
return lo
Output
find_peak([1,2,3,1]) → 2 (peak is 3 at index 2)
find_peak([1,2,1,3,5,6,4]) → 5 (peak is 6 at index 5)
Note Time O(log n). Note: use lo < hi (not lo <= hi) because we narrow to a single element. The problem guarantees arr[-1] = arr[n] = -infinity conceptually. Multiple peaks may exist - this finds any one of them.
When the answer is a number in a range and you can verify feasibility:1.Define search range [lo, hi]for the answer
2.Binary search: check if mid is a feasible answer
3.Narrow the range based on feasibility
Example
// JavaScript - Minimum capacity to ship packages in d daysfunctionshipWithinDays(weights, days){let lo =Math.max(...weights);// must fit largest packagelet hi = weights.reduce((a, b)=> a + b,0);// ship everything in 1 daywhile(lo < hi){const mid = lo +Math.floor((hi - lo)/2);if(canShip(weights, days, mid)){
hi = mid;// try smaller capacity}else{
lo = mid +1;// need more capacity}}return lo;}functioncanShip(weights, days, capacity){let daysNeeded =1, currentLoad =0;for(const w of weights){if(currentLoad + w > capacity){
daysNeeded++;
currentLoad =0;}
currentLoad += w;}return daysNeeded <= days;}
# Python
def ship_within_days(weights, days):
lo =max(weights)
hi =sum(weights)while lo < hi:
mid = lo +(hi - lo)// 2ifcan_ship(weights, days, mid):
hi = mid
else:
lo = mid +1return lo
def can_ship(weights, days, capacity):
days_needed, current_load =1,0for w in weights:if current_load + w > capacity:
days_needed +=1
current_load =0
current_load += w
return days_needed <= days
Output
ship_within_days([1,2,3,4,5,6,7,8,9,10], 5) → 15
Note Time O(n * log(sum - max)). This is an advanced pattern: instead of searching an array, you binary search the answer space. Works when: the feasibility function is monotonic (if capacity X works, X+1 also works). Other applications: minimum speed to eat bananas, split array largest sum.
binary search on answerminimize maximumfeasibility checkcapacity to shipsplit array
Memoization(top-down):Recursive+ cache results of subproblems.Tabulation(bottom-up):Iterative+ fill a table from base cases up.Both avoid recomputing overlapping subproblems.
Example
// JavaScript - Fibonacci both ways// Top-down (memoization)functionfibMemo(n, memo ={}){if(n <=1)return n;if(n in memo)return memo[n];
memo[n]=fibMemo(n -1, memo)+fibMemo(n -2, memo);return memo[n];}// Bottom-up (tabulation)functionfibTab(n){if(n <=1)return n;const dp =[0,1];for(let i =2; i <= n; i++){
dp[i]= dp[i -1]+ dp[i -2];}return dp[n];}
# Python
# Top-down
def fib_memo(n, memo={}):if n <=1:return n
if n not in memo:
memo[n]=fib_memo(n -1, memo)+fib_memo(n -2, memo)return memo[n]
# Bottom-up
def fib_tab(n):if n <=1:return n
dp =[0,1]for i inrange(2, n +1):
dp.append(dp[-1]+ dp[-2])return dp[n]
Output
fib_memo(10) → 55
fib_tab(10) → 55
Note Both are O(n) time, O(n) space. Memoization is easier to write (natural recursion) but has call stack overhead. Tabulation avoids stack overflow and can be space-optimized (keep only last 2 values → O(1) space). Start with memoization in interviews, then optimize to tabulation if asked.
Note Time O(n), Space O(1) with the two-variable optimization. This is literally Fibonacci shifted by one index. Classic DP warm-up - if you see this, solve it fast and mention the Fibonacci connection. Generalize to k steps: dp[i] = sum of dp[i-1]...dp[i-k].
climbing stairsstaircase problemfibonacci variantways to reach top
Coin Change - Minimum Coins
Syntax
dp[amount]= minimum coins needed to make that amount.
dp[0]=0For each amount,try each coin: dp[amount]=min(dp[amount], dp[amount - coin]+1)
Example
// JavaScriptfunctioncoinChange(coins, amount){const dp =newArray(amount +1).fill(Infinity);
dp[0]=0;for(let a =1; a <= amount; a++){for(const coin of coins){if(coin <= a && dp[a - coin]!==Infinity){
dp[a]=Math.min(dp[a], dp[a - coin]+1);}}}return dp[amount]===Infinity?-1: dp[amount];}
# Python
def coin_change(coins, amount):
dp =[float('inf')]*(amount +1)
dp[0]=0for a inrange(1, amount +1):for coin in coins:if coin <= a and dp[a - coin]!=float('inf'):
dp[a]=min(dp[a], dp[a - coin]+1)return dp[amount]if dp[amount]!=float('inf')else-1
Note Time O(amount * numCoins), Space O(amount). Greedy (always pick largest coin) does NOT work for all coin sets - DP is needed. Variant: number of ways to make change (count combinations instead of minimize). Return -1 if amount cannot be formed.
2DDP: dp[i][j]=LCS length of first i chars of s1 and first j chars of s2.If s1[i-1]== s2[j-1]: dp[i][j]= dp[i-1][j-1]+1Else: dp[i][j]=max(dp[i-1][j], dp[i][j-1])
Example
// JavaScriptfunctionlongestCommonSubsequence(s1, s2){const m = s1.length, n = s2.length;const dp =Array.from({ length: m +1},()=>newArray(n +1).fill(0));for(let i =1; i <= m; i++){for(let j =1; j <= n; j++){if(s1[i -1]=== s2[j -1]){
dp[i][j]= dp[i -1][j -1]+1;}else{
dp[i][j]=Math.max(dp[i -1][j], dp[i][j -1]);}}}return dp[m][n];}
# Python
def longest_common_subsequence(s1, s2):
m, n =len(s1),len(s2)
dp =[[0]*(n +1)for _ inrange(m +1)]for i inrange(1, m +1):for j inrange(1, n +1):if s1[i -1]== s2[j -1]:
dp[i][j]= dp[i -1][j -1]+1else:
dp[i][j]=max(dp[i -1][j], dp[i][j -1])return dp[m][n]
Note Time O(m*n), Space O(m*n), reducible to O(min(m,n)) with rolling array. To reconstruct the actual subsequence, backtrack through the DP table. LCS is the foundation for diff algorithms and edit distance. Subsequence ≠ substring (subsequence elements need not be contiguous).
longest common subsequenceLCS2D DPsubsequence matching
0/1 Knapsack
Syntax
Given items with weight and value, maximize value within capacity.Each item can be taken or left(0 or 1 times).
dp[i][w]= max value using first i items with capacity w.
Example
// JavaScriptfunctionknapsack(weights, values, capacity){const n = weights.length;const dp =Array.from({ length: n +1},()=>newArray(capacity +1).fill(0));for(let i =1; i <= n; i++){for(let w =0; w <= capacity; w++){
dp[i][w]= dp[i -1][w];// skip itemif(weights[i -1]<= w){
dp[i][w]=Math.max(
dp[i][w],
dp[i -1][w - weights[i -1]]+ values[i -1]);}}}return dp[n][capacity];}
# Python
def knapsack(weights, values, capacity):
n =len(weights)
dp =[[0]*(capacity +1)for _ inrange(n +1)]for i inrange(1, n +1):for w inrange(capacity +1):
dp[i][w]= dp[i -1][w]if weights[i -1]<= w:
dp[i][w]=max(dp[i][w],
dp[i -1][w - weights[i -1]]+ values[i -1])return dp[n][capacity]
Output
knapsack([2,3,4,5], [3,4,5,6], 5) → 7 (items with weight 2+3, value 3+4)
Note Time O(n * capacity), Space O(n * capacity), reducible to O(capacity) with 1D DP (iterate weights backwards). The 0/1 constraint means we look at dp[i-1] (previous row). For unbounded knapsack (items reusable), look at dp[i] (current row). Recognize the pattern: subset selection with a constraint.
dp[i]= length ofLIS ending at index i.For each i, check all j < i:if arr[j]< arr[i], dp[i]=max(dp[i], dp[j]+1).Optimal: patience sorting with binary search → O(n log n).
Example
// JavaScript - O(n^2) DPfunctionlisDP(arr){const dp =newArray(arr.length).fill(1);for(let i =1; i < arr.length; i++){for(let j =0; j < i; j++){if(arr[j]< arr[i]) dp[i]=Math.max(dp[i], dp[j]+1);}}returnMath.max(...dp);}// O(n log n) with binary searchfunctionlisBinarySearch(arr){const tails =[];for(const num of arr){let lo =0, hi = tails.length;while(lo < hi){const mid = lo +Math.floor((hi - lo)/2);if(tails[mid]< num) lo = mid +1;else hi = mid;}
tails[lo]= num;}return tails.length;}
# Python-O(n log n)import bisect
def lis(arr):
tails =[]for num in arr:
pos = bisect.bisect_left(tails, num)if pos ==len(tails):
tails.append(num)else:
tails[pos]= num
returnlen(tails)
Output
lis([10,9,2,5,3,7,101,18]) → 4 (subsequence: 2,3,7,101 or 2,5,7,101)
Note O(n^2) DP is straightforward. O(n log n) uses a 'tails' array: tails[i] = smallest tail element for all increasing subsequences of length i+1. The tails array is NOT the actual LIS. To reconstruct, keep a parent pointer array. This is a very popular hard DP problem.
Minimumoperations(insert,delete, replace) to transform s1 into s2.
dp[i][j]= edit distance for s1[0..i-1] and s2[0..j-1].If chars match: dp[i][j]= dp[i-1][j-1]Else:1+min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
Example
// JavaScriptfunctioneditDistance(s1, s2){const m = s1.length, n = s2.length;const dp =Array.from({ length: m +1},(_, i)=>Array.from({ length: n +1},(_, j)=>(i ===0? j : j ===0? i :0)));for(let i =1; i <= m; i++){for(let j =1; j <= n; j++){if(s1[i -1]=== s2[j -1]){
dp[i][j]= dp[i -1][j -1];}else{
dp[i][j]=1+Math.min(
dp[i -1][j],// delete
dp[i][j -1],// insert
dp[i -1][j -1]// replace);}}}return dp[m][n];}
# Python
def edit_distance(s1, s2):
m, n =len(s1),len(s2)
dp =[[0]*(n +1)for _ inrange(m +1)]for i inrange(m +1):
dp[i][0]= i
for j inrange(n +1):
dp[0][j]= j
for i inrange(1, m +1):for j inrange(1, n +1):if s1[i -1]== s2[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])return dp[m][n]
Note Time O(m*n), Space O(m*n), reducible to O(min(m,n)). Base cases: transforming empty string to s requires len(s) operations. Used in spell checkers, DNA analysis, and fuzzy matching. To reconstruct the operations, backtrack through the DP table.
Cannot rob two adjacent houses.Maximize total.
dp[i]=max(dp[i-1], dp[i-2]+ nums[i])At each house: skip it(take prev best) or rob it(prev-prev best + current).
Example
// JavaScriptfunctionrob(nums){if(nums.length===0)return0;if(nums.length===1)return nums[0];let prev2 =0, prev1 =0;for(const num of nums){const current =Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = current;}return prev1;}
# Python
def rob(nums):
prev2, prev1 =0,0for num in nums:
prev2, prev1 = prev1,max(prev1, prev2 + num)return prev1
Note Time O(n), Space O(1). The circular variant (houses in a circle): run the algorithm twice - once excluding the first house, once excluding the last - and take the max. This pattern of 'take or skip' with constraints appears in many DP problems.
house robbermaximum non-adjacenttake or skipDP optimizationcircular variant
Every recursive function needs:1.Basecase: when to stop(prevents infinite recursion)2.Recursivecase:break problem into smaller subproblem
3.Progress: each call must move toward the base case
Example
// JavaScript - Sum of array using recursionfunctionsumArray(arr, idx =0){if(idx >= arr.length)return0;// base casereturn arr[idx]+sumArray(arr, idx +1);// recursive case}// Power functionfunctionpower(base, exp){if(exp ===0)return1;// base caseif(exp %2===0){const half =power(base, exp /2);return half * half;// O(log n)}return base *power(base, exp -1);}
# Python
def sum_array(arr, idx=0):if idx >=len(arr):return0return arr[idx]+sum_array(arr, idx +1)
def power(base, exp):if exp ==0:return1if exp %2==0:
half =power(base, exp // 2)return half * half
return base *power(base, exp -1)
Output
sum_array([1,2,3,4]) → 10
power(2, 10) → 1024
Note Always identify the base case first. Stack overflow risk: Python default limit is 1000 frames (sys.setrecursionlimit can increase). For deep recursion, convert to iteration. The power function shows how recursion can achieve O(log n) - a common follow-up.
base caserecursive caserecursion fundamentalsstack overflowrecursive thinking
Permutations
Syntax
Generate all orderings of elements.Backtrack: at each position,try each unused element.Swap or use a 'used' boolean array to track which elements are placed.
Example
// JavaScriptfunctionpermute(nums){const result =[];functionbacktrack(current, remaining){if(remaining.length===0){
result.push([...current]);return;}for(let i =0; i < remaining.length; i++){
current.push(remaining[i]);backtrack(current,[...remaining.slice(0, i),...remaining.slice(i +1)]);
current.pop();// undo choice}}backtrack([], nums);return result;}
# Python
def permute(nums):
result =[]
def backtrack(current, remaining):if not remaining:
result.append(current[:])returnfor i inrange(len(remaining)):
current.append(remaining[i])backtrack(current, remaining[:i]+ remaining[i+1:])
current.pop()backtrack([], nums)return result
Note Time O(n! * n), Space O(n). The 'undo choice' step (current.pop()) is the hallmark of backtracking. For permutations with duplicates: sort first, and skip if nums[i] == nums[i-1] and nums[i-1] was not used in this branch. n! grows extremely fast - practical only for n ≤ ~10.
Choose k items from n without regard to order.Backtrack: at each step, choose to include or exclude the current element.Only pick elements with index >= start to avoid duplicates.
Example
// JavaScriptfunctioncombine(n, k){const result =[];functionbacktrack(start, current){if(current.length=== k){
result.push([...current]);return;}for(let i = start; i <= n; i++){
current.push(i);backtrack(i +1, current);
current.pop();}}backtrack(1,[]);return result;}
# Python
def combine(n, k):
result =[]
def backtrack(start, current):iflen(current)== k:
result.append(current[:])returnfor i inrange(start, n +1):
current.append(i)backtrack(i +1, current)
current.pop()backtrack(1,[])return result
Note Time O(C(n,k) * k), Space O(k) for recursion depth. The key difference from permutations: use a 'start' parameter to only pick forward, preventing duplicate combinations. Optimization: prune when remaining elements < needed elements (n - i + 1 < k - len(current)).
combinationschoose k from nbacktracking combinationsC(n,k)
Subsets (Power Set)
Syntax
Generate all 2^n subsets of a set.Backtrack:for each element, choose to include it or not.Alternative: iterative bit manipulation.
Example
// JavaScriptfunctionsubsets(nums){const result =[];functionbacktrack(start, current){
result.push([...current]);// every state is a valid subsetfor(let i = start; i < nums.length; i++){
current.push(nums[i]);backtrack(i +1, current);
current.pop();}}backtrack(0,[]);return result;}// Iterative approachfunctionsubsetsIterative(nums){const result =[[]];for(const num of nums){const newSubsets = result.map(sub =>[...sub, num]);
result.push(...newSubsets);}return result;}
# Python
def subsets(nums):
result =[]
def backtrack(start, current):
result.append(current[:])for i inrange(start,len(nums)):
current.append(nums[i])backtrack(i +1, current)
current.pop()backtrack(0,[])return result
Note Time O(2^n * n), Space O(n) recursion depth. Unlike combinations, we add to result at every recursive call (not just when a condition is met). For subsets with duplicates: sort the input, then skip nums[i] == nums[i-1] when i > start. The iterative approach is elegant and avoids recursion.
Place n queens on an n×n board so no two attack each other.Backtrack row by row.For each row,try placing a queen in each column.Check conflicts: same column, same diagonal(row-col), same anti-diagonal(row+col).
solve_n_queens(4) → 2 solutions
['.Q..','...Q','Q...','..Q.'] and ['..Q.','Q...','...Q','.Q..']
Note Time O(n!), Space O(n). The diagonal trick: queens on the same diagonal have the same (row-col), same anti-diagonal have same (row+col). Using sets for O(1) conflict checking is more elegant than iterating over placed queens. This is the canonical backtracking problem.
Fill empty cells one at a time.For each empty cell,try digits 1-9.Check row, column, and 3x3 box constraints.Backtrackif no valid digit fits.
Example
// JavaScriptfunctionsolveSudoku(board){functionisValid(board, row, col, num){const ch =String(num);for(let i =0; i <9; i++){if(board[row][i]=== ch)returnfalse;// rowif(board[i][col]=== ch)returnfalse;// columnconst boxR =3*Math.floor(row /3)+Math.floor(i /3);const boxC =3*Math.floor(col /3)+(i %3);if(board[boxR][boxC]=== ch)returnfalse;// box}returntrue;}functionsolve(board){for(let r =0; r <9; r++){for(let c =0; c <9; c++){if(board[r][c]==='.'){for(let num =1; num <=9; num++){if(isValid(board, r, c, num)){
board[r][c]=String(num);if(solve(board))returntrue;
board[r][c]='.';}}returnfalse;// no valid digit → backtrack}}}returntrue;// all cells filled}solve(board);}
# Python
def solve_sudoku(board):
def is_valid(row, col, num):
ch =str(num)for i inrange(9):if board[row][i]== ch:returnFalseif board[i][col]== ch:returnFalse
br =3*(row // 3) + i // 3
bc =3*(col // 3) + i % 3if board[br][bc]== ch:returnFalsereturnTrue
def solve():for r inrange(9):for c inrange(9):if board[r][c]=='.':for num inrange(1,10):ifis_valid(r, c, num):
board[r][c]=str(num)ifsolve():returnTrue
board[r][c]='.'returnFalsereturnTruesolve()
Output
Fills in all '.' cells with valid digits 1-9.
Note Time O(9^(empty cells)) worst case, but pruning makes it much faster in practice. Optimization: use sets for each row, column, and box to check validity in O(1) instead of O(9). Finding the cell with fewest candidates first (MRV heuristic) dramatically speeds up solving.
DFSfrom each cell.At each step, check if the current cell matches the next character.Mark cell asvisited(temporarily modify it), recurse in4 directions, then unmark.
Example
// JavaScriptfunctionexist(board, word){const rows = board.length, cols = board[0].length;functiondfs(r, c, idx){if(idx === word.length)returntrue;if(r <0|| r >= rows || c <0|| c >= cols)returnfalse;if(board[r][c]!== word[idx])returnfalse;const saved = board[r][c];
board[r][c]='#';// mark visitedconst found =dfs(r+1,c,idx+1)||dfs(r-1,c,idx+1)||dfs(r,c+1,idx+1)||dfs(r,c-1,idx+1);
board[r][c]= saved;// unmarkreturn found;}for(let r =0; r < rows; r++)for(let c =0; c < cols; c++)if(dfs(r, c,0))returntrue;returnfalse;}
# Python
def exist(board, word):
rows, cols =len(board),len(board[0])
def dfs(r, c, idx):if idx ==len(word):returnTrueif r <0 or r >= rows or c <0 or c >= cols:returnFalseif board[r][c]!= word[idx]:returnFalse
saved = board[r][c]
board[r][c]='#'
found =(dfs(r+1,c,idx+1) or dfs(r-1,c,idx+1)
or dfs(r,c+1,idx+1) or dfs(r,c-1,idx+1))
board[r][c]= saved
return found
for r inrange(rows):for c inrange(cols):ifdfs(r, c,0):returnTruereturnFalse
Note Time O(m * n * 4^L) where L = word length. The temporary cell modification is a clean alternative to a separate visited set. Always restore the cell after backtracking. Optimization: check if the board has all needed characters before starting DFS.
word searchgrid DFSbacktracking gridpath finding word
When to use:-Sorted array pair problems
-Removing duplicates in place
-Containerwith most water
-Palindrome checking
Variants:-Oppositeends(converging)-Samedirection(fast/slow or lagging)
Example
// JavaScript - Remove duplicates from sorted arrayfunctionremoveDuplicates(arr){if(arr.length===0)return0;let writeIdx =1;for(let i =1; i < arr.length; i++){if(arr[i]!== arr[i -1]){
arr[writeIdx]= arr[i];
writeIdx++;}}return writeIdx;}
# Python
def remove_duplicates(arr):if not arr:return0
write_idx =1for i inrange(1,len(arr)):if arr[i]!= arr[i -1]:
arr[write_idx]= arr[i]
write_idx +=1return write_idx
Note O(n) time, O(1) space. The 'read pointer / write pointer' variant is essential for in-place array problems. Always ask: is the input sorted? If yes, two pointers likely applies. If unsorted, consider hash set instead.
two pointers patternremove duplicatesconverging pointersin-place modification
Pattern: Fast & Slow Pointer
Syntax
When to use:-Cycledetection(linked list, array)-Finding middle of linked list
-Finding the start of a cycle
-Happy number problem
Slow moves 1 step, fast moves 2 steps.
Example
// JavaScript - Happy number (sum of squared digits eventually reaches 1)functionisHappy(n){functiondigitSquareSum(num){let sum =0;while(num >0){const digit = num %10;
sum += digit * digit;
num =Math.floor(num /10);}return sum;}let slow = n, fast = n;do{
slow =digitSquareSum(slow);
fast =digitSquareSum(digitSquareSum(fast));}while(slow !== fast);return slow ===1;}
# Python
def is_happy(n):
def digit_square_sum(num):
total =0while num >0:
digit = num %10
total += digit * digit
num //= 10return total
slow = fast = n
whileTrue:
slow =digit_square_sum(slow)
fast =digit_square_sum(digit_square_sum(fast))if slow == fast:breakreturn slow ==1
Note The fast/slow pointer pattern detects cycles in any sequence where each value maps to the next. It uses O(1) space compared to a hash set. For linked lists, this is Floyd's algorithm. For number sequences (like happy number), the function that generates the next value plays the role of 'next pointer'.
fast slow pointerFloyd's cyclehappy numbertortoise harecycle detection pattern
Pattern: Sliding Window (Summary)
Syntax
When to use:-Subarray/substring withconstraint(max sum, min length, distinct chars)-Fixed-size window statistics
-Longest/shortest substring matching a condition
Template:-Expand right pointer
-Whenwindow invalid, shrink left pointer
-Update answer at each valid state
Example
// JavaScript - Longest substring without repeating charactersfunctionlengthOfLongestSubstring(s){const charIdx =newMap();let maxLen =0, left =0;for(let right =0; right < s.length; right++){if(charIdx.has(s[right])&& charIdx.get(s[right])>= left){
left = charIdx.get(s[right])+1;}
charIdx.set(s[right], right);
maxLen =Math.max(maxLen, right - left +1);}return maxLen;}
# Python
def length_of_longest_substring(s):
char_idx ={}
max_len = left =0for right, ch inenumerate(s):if ch in char_idx and char_idx[ch]>= left:
left = char_idx[ch]+1
char_idx[ch]= right
max_len =max(max_len, right - left +1)return max_len
Note O(n) time, O(k) space where k = alphabet/window contents. The trick: store the last index of each character so you can jump the left pointer forward without shrinking one step at a time. This is one of the most frequently asked medium problems.
When to use:-Overlapping intervals
-Meeting room scheduling
-Insert interval into sorted list
1.Sort intervals by start time
2.Iterate:if current overlaps with previous, merge them
3.Otherwise, add current asnew interval
Example
// JavaScriptfunctionmergeIntervals(intervals){
intervals.sort((a, b)=> a[0]- b[0]);const merged =[intervals[0]];for(let i =1; i < intervals.length; i++){const last = merged[merged.length-1];if(intervals[i][0]<= last[1]){
last[1]=Math.max(last[1], intervals[i][1]);}else{
merged.push(intervals[i]);}}return merged;}
# Python
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged =[intervals[0]]for start, end in intervals[1:]:if start <= merged[-1][1]:
merged[-1][1]=max(merged[-1][1], end)else:
merged.append([start, end])return merged
Note Time O(n log n) for sorting. Space O(n) for result. The overlap condition: current.start <= prev.end. For 'meeting rooms needed' (minimum rooms), use a min-heap on end times or a sweep line approach. Always sort by start time first.
When to use:-K most frequent elements
-K closest points
-K largest/smallest values
Approaches:1.Sort → O(n log n)2.Min-heap of size k → O(n log k)3.Quickselect → O(n) average
Example
// JavaScript - Top K frequent elements using bucket sortfunctiontopKFrequent(nums, k){const freq =newMap();for(const n of nums) freq.set(n,(freq.get(n)||0)+1);// Bucket: index = frequency, value = list of elementsconst buckets =Array.from({ length: nums.length+1},()=>[]);for(const[num, count]of freq) buckets[count].push(num);const result =[];for(let i = buckets.length-1; i >=0&& result.length< k; i--){
result.push(...buckets[i]);}return result.slice(0, k);}
# Pythonimport heapq
from collections importCounter
def top_k_frequent(nums, k):
freq =Counter(nums)
# nlargest uses a heap internally
return[item for item, count in freq.most_common(k)]
Output
top_k_frequent([1,1,1,2,2,3], 2) → [1, 2]
Note Bucket sort approach: O(n) time and space. Heap approach: O(n log k). For 'top K', a min-heap of size k is optimal - you evict the smallest when the heap exceeds k, so only the K largest remain. Python's heapq.nlargest and Counter.most_common are powerful shortcuts.
top K elementsK most frequentheap top Kbucket sort frequencyquickselect
Pattern: Prefix Sum (Applications)
Syntax
When to use:-Range sum queries
-Subarray sum equals K-Subarray sum divisible by K-Binary subarrays with sum
-Count subarrays with given XORCore idea: prefix[i]- prefix[j]= sum of arr[j..i-1]
Example
// JavaScript - Count subarrays with sum divisible by kfunctionsubarraysDivByK(arr, k){const modCount =newMap([[0,1]]);let prefix =0, count =0;for(const num of arr){
prefix =((prefix + num)% k + k)% k;// handle negatives
count += modCount.get(prefix)||0;
modCount.set(prefix,(modCount.get(prefix)||0)+1);}return count;}
# Python
def subarrays_div_by_k(arr, k):
mod_count ={0:1}
prefix =0
count =0for num in arr:
prefix =(prefix + num)% k
count += mod_count.get(prefix,0)
mod_count[prefix]= mod_count.get(prefix,0)+1return count
Output
subarrays_div_by_k([4,5,0,-2,-3,1], 5) → 7
Note Time O(n), Space O(k). The key insight: if two prefix sums have the same remainder mod k, the subarray between them is divisible by k. Handle negative modulo carefully: (x % k + k) % k ensures a non-negative remainder. This is a very common interview pattern.
prefix sum patternsubarray divisible by kmodular prefixrange sum pattern
Pattern: Union-Find (Disjoint Set)
Syntax
Track connected components efficiently.Two operations:-find(x):return the root/representative of x's set-union(x, y): merge the sets containing x and y
Optimizations: path compression + union by rank
Note With both optimizations, operations are nearly O(1) amortized (technically O(alpha(n)) inverse Ackermann). Perfect for: connected components, redundant connections, accounts merge, minimum spanning tree (Kruskal's). Union returns false when already connected - useful for cycle detection.
union finddisjoint setconnected componentspath compressionunion by rank
Pattern: When to Use BFS vs DFS
Syntax
UseBFS when:-Shortest path in unweighted graph
-Level-by-level processing
-Closest node / nearest distance
UseDFS when:-Exploring all paths / all possibilities
-Cycle detection
-Topological sort
-Treetraversals(in/pre/post order)-Backtracking problems
Example
// Decision guide:// 'Shortest' or 'minimum steps' → BFS// 'All paths' or 'does a path exist' → DFS// 'Level order' → BFS// 'Permutations/combinations' → DFS (backtracking)// JavaScript - Minimum steps to reach target in gridfunctionminSteps(grid, start, end){const rows = grid.length, cols = grid[0].length;const queue =[[...start,0]];// [row, col, steps]const visited =newSet([start.toString()]);const dirs =[[0,1],[0,-1],[1,0],[-1,0]];while(queue.length){const[r, c, steps]= queue.shift();if(r === end[0]&& c === end[1])return steps;for(const[dr, dc]of dirs){const nr = r + dr, nc = c + dc;const key =`${nr},${nc}`;if(nr >=0&& nr < rows && nc >=0&& nc < cols
&& grid[nr][nc]===0&&!visited.has(key)){
visited.add(key);
queue.push([nr, nc, steps +1]);}}}return-1;}
# Pythonfrom collections import deque
def min_steps(grid, start, end):
rows, cols =len(grid),len(grid[0])
queue =deque([(start[0], start[1],0)])
visited ={(start[0], start[1])}for dr, dc in[(0,1),(0,-1),(1,0),(-1,0)]:
pass # directions defined in loop below
while queue:
r, c, steps = queue.popleft()if(r, c)==tuple(end):return steps
for dr, dc in[(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if0<= nr < rows and 0<= nc < cols and grid[nr][nc]==0and(nr,nc) not in visited:
visited.add((nr, nc))
queue.append((nr, nc, steps +1))return-1
Output
BFS guarantees shortest path in unweighted graphs.
DFS is better for exhaustive search and backtracking.
Note BFS time/space: O(V + E). DFS time: O(V + E), space: O(V) worst case. In grid problems, treat each cell as a node with 4 edges. For BFS on grids, always mark visited when enqueuing (not when dequeuing) to avoid processing a cell multiple times.
BFS vs DFSwhen to use BFSwhen to use DFSshortest path gridgraph traversal choice
Note Start simple, scale when needed. In interviews, show you can estimate back-of-the-envelope numbers: daily active users, requests per second, storage needs. Mention trade-offs: horizontal scaling adds complexity (load balancing, distributed state) but has no ceiling like vertical scaling.
Distributes traffic across multiple servers.Strategies:-Round robin: rotate through servers
-Least connections: send to least busy
-IP hash: consistent routing per client
-Weighted: more traffic to stronger servers
Example
// Architecture:// Client → Load Balancer → Server 1// → Server 2// → Server 3// Layer 4 (TCP): fast, routes by IP/port// Layer 7 (HTTP): smarter, can route by URL/headers/cookies// Health checks: LB periodically pings servers// If server fails health check → removed from rotation// When it recovers → added back
Output
Load balancers enable horizontal scaling and high availability.
Note In interviews, mention: single point of failure risk → use redundant LBs (active-passive pair). Session stickiness (sticky sessions) can solve stateful server issues but reduces flexibility. Modern cloud: AWS ALB/NLB, GCP Load Balancer handle this automatically.
Store frequently accessed data in fast storage(memory).Layers: browser cache → CDN → application cache → database cache
Patterns:-Cache-aside: app checks cache first, loads fromDB on miss
-Write-through: write to cache and DB simultaneously
-Write-back: write to cache,async flush to DB
Example
// Cache-aside pattern (most common):// 1. App receives request// 2. Check cache (Redis/Memcached)// 3. Cache HIT → return cached data// 4. Cache MISS → query database → store in cache → return// Eviction policies:// LRU: remove least recently used (most common)// LFU: remove least frequently used// TTL: expire after fixed time// Cache invalidation strategies:// 1. TTL-based: set expiry, eventually consistent// 2. Event-based: invalidate on write// 3. Version-based: cache key includes version number
Note Cache invalidation is one of the two hard problems in CS (along with naming things). Always discuss: cache stampede (many misses at once → thundering herd), consistency vs performance trade-off, and cold start (empty cache after deploy). Redis is the go-to answer for distributed caching.
Split a large database into smaller pieces(shards), each on a separate server.Sharding key: determines which shard stores each record.Types:-Range-based: shard by ID ranges
-Hash-based:hash(key)% num_shards
-Geographic: shard by region
Example
// Hash-based sharding:// shard_id = hash(user_id) % num_shards// User 12345 → hash(12345) % 4 → shard 2// Example with 4 shards:// Shard 0: users where hash(id) % 4 = 0// Shard 1: users where hash(id) % 4 = 1// Shard 2: users where hash(id) % 4 = 2// Shard 3: users where hash(id) % 4 = 3// Consistent hashing: minimizes data movement when adding/removing shards// Instead of hash % N, map keys and shards to a ring
Output
Sharding enables databases to handle billions of rows.
Note Trade-offs: cross-shard queries are expensive, joins across shards are very difficult, rebalancing shards is painful. Choose sharding key carefully - it should distribute data evenly and align with your most common access pattern. Mention consistent hashing to impress - it minimizes data migration when topology changes.
In a distributed system, you can only guarantee 2of3:-Consistency: every read gets the most recent write
-Availability: every request gets a response
-Partition tolerance: system works despite network failures
Since partitions are inevitable, the real choice isC vs A during a partition.
Example
// CP systems (consistency over availability):// - Bank transactions: must be consistent// - Examples: HBase, MongoDB (with majority write concern)// - During partition: some requests may fail// AP systems (availability over consistency):// - Social media feeds: slightly stale data is OK// - Examples: Cassandra, DynamoDB// - During partition: may serve stale data// Real-world: most systems mix both// Critical data (payments) → strong consistency// Non-critical data (user profile pic) → eventual consistency
Output
In practice: choose between consistency and availability during network partitions.
Note Saying 'I would choose CP' or 'AP' without context is a red flag. Instead, discuss WHICH parts of the system need which guarantee. Payment processing needs CP. A news feed can tolerate AP. Mention 'eventual consistency' - most modern distributed databases use it.
CAP theoremconsistency availabilitydistributed systemseventual consistencypartition tolerance
REST vs GraphQL
Syntax
REST:-Resource-based URLs:/users/123-Fixed response shape per endpoint
-Multiple endpoints for related data
GraphQL:-Single endpoint, query specifies shape
-Client requests exactly what it needs
-Reduces over/under-fetching
Example
// REST:// GET /users/123 → full user object// GET /users/123/posts → all posts// Problem: 2 requests, might get unused fields// GraphQL:// POST /graphql// query {// user(id: 123) {// name// posts(limit: 5) {// title// }// }// }// → exactly the fields requested, single request// When to use REST:// - Simple CRUD APIs, caching is important (HTTP caching)// - Public APIs, broad adoption// When to use GraphQL:// - Mobile apps (bandwidth-sensitive)// - Complex data relationships// - Multiple client types needing different data shapes
Output
REST: simpler, cacheable | GraphQL: flexible, efficient data fetching
Note Neither is universally better. REST is simpler to cache (GET requests are cacheable by URL). GraphQL can cause N+1 query problems on the backend if not careful (use DataLoader pattern). In interviews, discuss trade-offs rather than picking a winner. Most companies use REST unless they have specific needs for GraphQL.
REST vs GraphQLAPI designover-fetchingunder-fetchingsystem design API
Message Queues
Syntax
Decouple producers from consumers.Producer sends messages to queue, consumer processes them asynchronously.Use cases:-Async task processing(email sending, image resizing)-Rate limiting / traffic smoothing
-Decoupling microservices
Examples:RabbitMQ,ApacheKafka,AWSSQS
Example
// Without queue:// User request → Process image → Respond (slow, 5 seconds)// With queue:// User request → Enqueue 'process image' → Respond immediately (50ms)// Background worker → Dequeue → Process image → Update status// Kafka vs SQS:// Kafka: ordered, replayable, high throughput, log-based// SQS: simple, managed, at-least-once delivery, auto-scaling// Key concepts:// At-least-once: message may be delivered multiple times// At-most-once: message may be lost but never duplicated// Exactly-once: hardest to achieve, often app-level idempotency
Output
Queues enable async processing, better reliability, and decoupled services.
Note In interviews, mention idempotency: since messages can be delivered multiple times, consumers should handle duplicates safely. Dead letter queues (DLQ) capture messages that fail processing repeatedly. Kafka is the go-to answer for event streaming; SQS/RabbitMQ for simple task queues.
Restrict how many requests a client can make in a time window.Protects services from abuse, ensures fair usage.Algorithms:1.Fixedwindow: count requests per time window2.Slidingwindow: smoother, avoids burst at window boundary
3.Token bucket: tokens refill at fixed rate, each request costs a token
4.Leaky bucket: requests processed at fixed rate, excess queued
Example
// Token bucket pseudocode:// bucket has 'tokens' (max capacity), refill rate// On request:// refill tokens based on elapsed time// if tokens >= 1:// tokens -= 1// allow request// else:// reject (429 Too Many Requests)// Example: 100 requests/minute, burst of 10// capacity = 10, refill rate = 100/60 ≈ 1.67 tokens/sec// Where to implement:// API Gateway level (centralized)// Application level (per-service)// Client-side (self-throttling)// Distributed rate limiting:// Use Redis INCR + EXPIRE for shared counter across instances
Note Token bucket is the most common answer in interviews - it allows bursts while maintaining an average rate. For distributed systems, use Redis as a shared counter (INCR + EXPIRE atomic operation). Return 429 status code with Retry-After header. Rate limiting is commonly asked in system design interviews for URL shortener, API gateway, and chat systems.
rate limitingtoken bucketthrottlingAPI protection429 too many requests
Structure behavioral answers with:S-Situation:set the scene, context
T-Task: what was your responsibility
A-Action: what YOU specifically did(use 'I', not 'we')R-Result: quantifiable outcome, what you learned
Example
// Question: 'Tell me about a time you dealt with a difficult bug.'// Situation: 'Our payment service was intermittently failing// for about 2% of transactions on weekends.'// Task: 'As the on-call engineer, I needed to diagnose and// fix it before Monday's peak traffic.'// Action: 'I correlated the failures with database connection// pool exhaustion, traced it to a missing timeout on a// third-party API call, added a 3-second timeout with// retry logic, and deployed with a feature flag.'// Result: 'Payment failures dropped to 0.01%, saving an// estimated $50K in lost weekend revenue. I also added// monitoring alerts so the team would catch similar// issues earlier.'
Output
Keep answers to 2-3 minutes. Be specific, not generic.
Note Prepare 5-7 stories that cover: leadership, conflict, failure, ambiguity, tight deadline, cross-team collaboration. Each story can be reframed for multiple questions. Practice aloud - timing matters. The most common mistake is saying 'we' too much - interviewers want YOUR contributions.
STAR methodbehavioral interviewtell me about a timestructured answer
// Tip 1: Don't start coding immediately.// Spend 5 minutes thinking → saves 15 minutes of rewriting.// Tip 2: State the brute force first.// 'The naive approach is O(n^2)...but I think we can do// O(n) using a hash map. Let me explain before coding.'// Tip 3: If stuck after 3 minutes, ask for a hint.// 'I'm thinking about using X, does that sound like the// right direction?' - This is better than silent struggling.// Tip 4: Code the core logic first, handle edge cases after.// Get the main algorithm working, then add null checks,// empty input handling, etc.// Tip 5: Talk while you code.// 'I'm initializing two pointers at each end because...'
Output
The interview is as much about communication as correctness.
Note If you realize your approach is wrong halfway through, say so. 'I think there is an issue with this approach because X. Can I pivot to Y?' Interviewers respect self-awareness more than stubbornly debugging a flawed approach. Also: running out of time on a correct approach scores higher than finishing an incorrect one.
time managementinterview pacingcoding interview tipswhen to start coding
Clarifying Questions to Ask
Syntax
Before coding, always clarify:1.Inputconstraints(size, range,type)2.Edgecases(empty, single element, duplicates)3.Returnformat(index vs value, one solution vs all)4.CanI modify the input?5.Is the input sorted?Are there duplicates?
Example
// Great clarifying questions by problem type:// Array/String:// 'Can there be negative numbers?'// 'Is the array sorted?'// 'Should I handle empty input?'// 'Are there duplicate values?'// 'ASCII or Unicode characters?'// Graph:// 'Is it directed or undirected?'// 'Can there be cycles?'// 'Are edge weights positive?'// 'Is the graph connected?'// Design:// 'How many users/requests per second?'// 'What is the read/write ratio?'// 'What are the latency requirements?'// 'Do we need strong or eventual consistency?'
Output
Asking clarifying questions shows maturity and thoroughness.
Note Never assume constraints that are not stated. Asking questions is NOT a sign of weakness - it is expected and valued. Good engineers clarify requirements before building. If the interviewer says 'you can assume X,' that is a useful constraint that simplifies your solution. Write down the constraints before coding.
Strategies when you hit a wall:1.Restate the problem in your own words
2.Work through a small example by hand
3.Think about related problems you have solved
4.Try a different data structure
5.Simplify: solve a smaller version first
6.Askfor a targeted hint(not 'what should I do?')
Example
// Instead of going silent, try these phrases:// 'Let me trace through this example manually to see// if I can spot a pattern...'// 'I've been thinking about a hash map approach, but// the ordering constraint makes me think maybe a// stack or monotonic structure would be better.'// 'The brute force would be O(n^2) with nested loops.// I wonder if sorting first could help us do better.'// 'I'm stuck on how to handle this edge case. Can you// give me a hint about what should happen when the// input has all identical values?'// 'This reminds me of the two-sum pattern - let me// think about whether a complement approach works here.'
Output
Getting stuck is normal. How you recover matters more than never being stuck.
Note Silence is the worst thing in an interview. Even if your thoughts are half-formed, share them. Interviewers cannot give credit for ideas in your head. Many interviewers are WAITING to give hints - they want you to succeed but need you to show your thinking process first. A candidate who gets stuck, asks a good question, gets a hint, and solves it can still get a strong hire.
getting stuckinterview recoveryasking for hintsproblem solvingthinking out loud
Communication Tips During Interviews
Syntax
1.Think aloud - narrate your reasoning
2.Explain trade-offs, not just the solution
3.Use precise language('I chose a hash map because lookups are O(1)')4.Draw diagrams when explaining complex logic
5.Acknowledge what you don't know ('I'm not sure about X, but my intuition is Y')
Example
// Strong communication pattern:// Step 1: 'I understand the problem as...'// Step 2: 'My initial thought is to use X because...'// Step 3: 'The trade-off is A vs B. I'll go with A because...'// Step 4: While coding: 'This loop handles the case where...'// Step 5: 'Let me verify with the example: for input [1,2,3],...'// Step 6: 'The time complexity is O(n) because we visit each// element once. Space is O(n) for the hash map.'// Weak communication:// 'Um...let me think...okay I'll try this...'// *codes silently for 20 minutes*// 'I think this works.'
Output
Strong communicators get more benefit of the doubt on borderline solutions.
Note Practice explaining your solutions to a rubber duck or recording yourself. Many candidates who solve the problem still get rejected for poor communication. The interviewer is evaluating: would I want to work with this person? Can they explain complex ideas clearly? Would they be effective in code reviews and design discussions?
communication skillsthink aloudinterview communicationexplain trade-offs
Most Common Behavioral Questions
Syntax
Prepare stories for these categories:1.'Tell me about yourself'(90-second pitch)2.Conflict/ disagreement with a teammate
3.A project you are most proud of4.A time you failed or made a mistake
5.Working under a tight deadline
6.Leading without formal authority
7.Dealingwith ambiguous requirements
8.Whythis company?
Example
// 'Tell me about yourself' template:// 'I'm a [role] with [X years] of experience focused on [area].// Most recently at [Company], I worked on [project] where I// [key achievement with metric]. I'm excited about [company]// because [specific reason tied to their product/mission].// I'm looking for [what you want in next role].'// Failure question template:// Situation: what happened// What went wrong and YOUR role in it (own it)// What you learned// How you applied that lesson later// Do NOT blame others or external factors// 'Why this company?' - research 3 specific things:// 1. A product feature you admire// 2. A company value that resonates// 3. A technical challenge they face that excites you
Output
Preparation prevents generic answers. Specificity is memorable.
Note For 'tell me about yourself,' do NOT recite your resume chronologically. Lead with your strongest, most relevant experience. For failure questions, pick a REAL failure (not 'I work too hard') but one where you learned something meaningful. Interviewers can tell rehearsed non-answers. Have your 'why this company' answer ready - it is almost always asked and a weak answer signals low interest.
common behavioral questionstell me about yourselfwhy this companyfailure questionbehavioral prep