Don't memorize 200 problems — learn the patterns behind them. Solutions are in Python, with Big-O. Examples use classic, public problems (Two Sum, Binary Search, etc.).
Brand new, or just looking around? These 8 classics are completely free — full solutions, run them right in the terminal, no account or credits needed. Work top to bottom, then dip into the rest of the page for depth. (With Learn Premium, every section below works exactly like this one.)
Print 1–100, but "Fizz" for multiples of 3, "Buzz" for 5, "FizzBuzz" for both. The classic warm-up — check the most specific case (15) first.
for n in range(1, 101):
if n % 15 == 0: print("FizzBuzz")
elif n % 3 == 0: print("Fizz")
elif n % 5 == 0: print("Buzz")
else: print(n)Slicing does it in one line; the two-pointer version is what an interviewer wants to see you reason about.
def reverse(s):
return s[::-1] # Pythonic one-liner
def reverse_two_pointer(chars): # in-place, O(n)
lo, hi = 0, len(chars) - 1
while lo < hi:
chars[lo], chars[hi] = chars[hi], chars[lo]
lo += 1; hi -= 1
return charsA word that reads the same backwards. Compare the string to its reverse.
def is_palindrome(s):
s = s.lower()
return s == s[::-1] # "Racecar" -> TrueOne pass, tracking the biggest seen so far — the pattern behind countless harder problems.
def largest(nums):
biggest = nums[0]
for n in nums[1:]:
if n > biggest:
biggest = n
return biggest # (built-in shortcut: max(nums))Loop the characters and tally the ones in "aeiou" — a gentle intro to string scanning.
def count_vowels(s):
return sum(1 for c in s.lower() if c in "aeiou")The single most common interview opener: return the indices of the two numbers that add to target. A hash map turns O(n²) into O(n).
def two_sum(nums, target):
seen = {} # value -> index
for i, n in enumerate(nums):
if target - n in seen:
return [seen[target - n], i]
seen[n] = i
return None # no pair foundEach number is the sum of the two before it. The iterative version is O(n) and uses no recursion stack.
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # fib(10) -> 55On a sorted array, halve the search space each step — O(log n). Knowing this cold is non-negotiable.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target: return mid
if arr[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1 # not foundBig-O describes how runtime grows as input size n grows. Lower is better.
| Big-O | Name | Example |
|---|---|---|
O(1) | constant | look up a dict/array index |
O(log n) | logarithmic | binary search |
O(n) | linear | one loop over the data |
O(n log n) | log-linear | good sorting (merge/quick) |
O(n²) | quadratic | nested loops |
O(2ⁿ) | exponential | naive recursion (avoid!) |
O(1) on hash maps/sets is relative to n — hashing a string key still costs O(m) for a length-m string.| Operation | Big-O |
|---|---|
| Add / remove at the end | O(1) amortized |
| Add / remove at arbitrary index | O(n) |
| Access / modify at index | O(1) |
| Check if element exists | O(n) |
| Two pointers / sliding window | O(n·k) (k = work per step) |
| Build a prefix sum | O(n) |
| Subarray sum from a prefix sum | O(1) |
| Operation | Big-O |
|---|---|
| Add / remove a character | O(n) |
| Access at index | O(1) |
| Concatenate two strings | O(n + m) |
| Create a substring | O(m) |
Build via "".join(list) | O(n) |
| Operation | Big-O |
|---|---|
| Add / remove with pointer at spot | O(1) (doubly linked) |
| Add / remove at arbitrary position | O(n) |
| Access at arbitrary position | O(n) |
| Reverse between i and j | O(j − i) |
| Detect a cycle (fast/slow) | O(n) |
| Operation | Big-O |
|---|---|
| Add / remove / look up a key | O(1) |
| Check if a value exists | O(n) |
| Iterate over keys / values | O(n) |
| Operation | Big-O |
|---|---|
| Push / pop / peek (stack) | O(1) |
| Enqueue / dequeue / peek (queue) | O(1) |
| Check if element exists | O(n) |
| Operation | Big-O |
|---|---|
| Binary tree DFS / BFS | O(n·k) (k = work per node) |
| BST add / remove / search | O(log n) avg, O(n) worst (unbalanced) |
| Heap add / remove-min | O(log n) |
| Heap find-min | O(1) |
| Heap check if exists | O(n) |
| Binary search | O(log n) |
| Operation | Big-O |
|---|---|
| Sorting | O(n log n) |
| Graph DFS / BFS (time) | O(n·k + e) (n nodes, e edges) |
| Graph DFS / BFS (space) | O(n), or O(n + e) to store the graph |
| DP (time) | O(n·k) (n states, k work/state) |
| DP (space) | O(n) (n states) |
| Constraint on n | Likely target complexity | Think… |
|---|---|---|
n ≤ 10 | O(n!) / O(n²·n!) | backtracking, brute-force recursion |
10 < n ≤ 20 | O(2ⁿ) | subsets/subsequences (take / don't take) |
20 < n ≤ 100 | O(n³) | brute force with nested loops |
100 < n ≤ 1,000 | O(n²) | nested loops, often optimal here |
1,000 < n < 100,000 | O(n log n) or O(n) | sort, heap, hash map, two pointers, monotonic stack, binary search |
100,000 < n < 1,000,000 | O(n) | almost certainly a hash map |
n > 1,000,000 (or 10⁹+) | O(log n) / O(1) | binary search, math tricks, clever hashing |
O(n). Otherwise you usually can't beat O(log n). An O(n) solution can hide a constant factor of ~40 (e.g. looping the 26 letters → O(26n)). Don't be confidently wrong about optimality — "I think this is optimal, but it may be improvable" is the safe phrasing.seen set prevents revisiting nodes / cycles").directions array instead of writing 4 near-identical blocks; use helper functions.O(n)). This is why understanding beats memorizing.CONDITION / # do logic parts). This is the single highest-leverage thing to memorize for interviews.def fn(arr):
left = ans = 0
right = len(arr) - 1
while left < right:
# do logic with left and right
if CONDITION:
left += 1
else:
right -= 1
return ansdef fn(arr1, arr2):
i = j = ans = 0
while i < len(arr1) and j < len(arr2):
# do logic
if CONDITION:
i += 1
else:
j += 1
while i < len(arr1):
# do logic
i += 1
while j < len(arr2):
# do logic
j += 1
return ansdef fn(arr):
left = ans = curr = 0
for right in range(len(arr)):
# add arr[right] to curr
while WINDOW_CONDITION_BROKEN:
# remove arr[left] from curr
left += 1
# update ans
return ansCollect chars in a list, then "".join() — building a string with += in a loop is O(n²) in Python. (In JS, benchmarks show += is actually faster than .join().)
Prefix-count with a hash map (e.g. "subarrays summing to k").
Same idea maintains a monotonic queue. For monotonic decreasing, just flip > to <.
Assume nodes 0..n-1 and an adjacency-list graph. Convert other inputs to this form first.
dp array sized by your state variables (so dp(4,6) becomes dp[4][6]); (2) set the same base cases (often just init to 0); (3) write for-loops over the state variables, iterating from the base cases toward the answer state; (4) copy the recurrence in, turning every dp(...) call into dp[...] array access; (5) return dp[...] instead of dp(...).Pattern: hash set — for each number, check if target − number was already seen. O(n) time.
def two_number_sum(nums, target):
seen = set()
for n in nums:
complement = target - n
if complement in seen:
return [complement, n]
seen.add(n)
return []
# two_number_sum([3, 5, -4, 8, 11, 1, -1, 6], 10) -> [11, -1]Pattern: two pointers — walk the main array, advance the second pointer on each match. O(n).
def is_valid_subsequence(array, sequence):
i = 0
for value in array:
if i == len(sequence):
break
if sequence[i] == value:
i += 1
return i == len(sequence)Pattern: a single pass keeping the top 3. O(n).
def three_largest(nums):
top = [None, None, None]
for n in nums:
if top[2] is None or n > top[2]:
top = [top[1], top[2], n]
elif top[1] is None or n > top[1]:
top = [top[1], n, top[2]]
elif top[0] is None or n > top[0]:
top = [n, top[1], top[2]]
return topOrder shortest jobs first so everyone waits the least. Greedy. O(n log n).
Pairs where one word is the other reversed (e.g. "diaper"/"repaid"). O(n·len).
def three_sum_classic(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
total = nums[i] + nums[lo] + nums[hi]
if total < 0:
lo += 1
elif total > 0:
hi -= 1
else:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]:
lo += 1
while lo < hi and nums[hi] == nums[hi-1]:
hi -= 1
lo += 1
hi -= 1
return resultdef max_area_classic(height):
lo, hi = 0, len(height) - 1
best = 0
while lo < hi:
best = max(best, min(height[lo], height[hi]) * (hi - lo))
if height[lo] < height[hi]:
lo += 1
else:
hi -= 1
return bestdef longest_consecutive_classic(nums):
num_set = set(nums)
best = 0
for n in num_set:
if n - 1 not in num_set:
length = 1
while n + length in num_set:
length += 1
best = max(best, length)
return bestdef maximal_square_classic(matrix):
if not matrix:
return 0
rows, cols = len(matrix), len(matrix[0])
dp = [[0] * (cols + 1) for _ in range(rows + 1)]
best = 0
for r in range(1, rows + 1):
for c in range(1, cols + 1):
if matrix[r-1][c-1] == 1:
dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
best = max(best, dp[r][c])
return best * bestdef calculate_minimum_hp(dungeon):
rows, cols = len(dungeon), len(dungeon[0])
dp = [[float('inf')] * (cols + 1) for _ in range(rows + 1)]
dp[rows][cols-1] = dp[rows-1][cols] = 1
for r in range(rows - 1, -1, -1):
for c in range(cols - 1, -1, -1):
need = min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c]
dp[r][c] = max(1, need)
return dp[0][0]def longest_increasing_path(matrix):
if not matrix:
return 0
rows, cols = len(matrix), len(matrix[0])
memo = {}
def dfs(r, c):
if (r, c) in memo:
return memo[(r, c)]
best = 1
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
best = max(best, 1 + dfs(nr, nc))
memo[(r, c)] = best
return best
return max(dfs(r, c) for r in range(rows) for c in range(cols))Square each number of a sorted array, return sorted. Two pointers from both ends (largest squares are at the ends). O(n).
class Solution:
def sorted_squared(self, arr):
res = [0] * len(arr)
lo, hi = 0, len(arr) - 1
for i in range(len(arr) - 1, -1, -1):
if abs(arr[lo]) > abs(arr[hi]):
res[i] = arr[lo] ** 2; lo += 1
else:
res[i] = arr[hi] ** 2; hi -= 1
return resMove all copies of a value to the end, in place. Two pointers. O(n).
class Solution:
def move_to_end(self, arr, target):
lo, hi = 0, len(arr) - 1
while lo < hi:
while lo < hi and arr[hi] == target: hi -= 1
if arr[lo] == target:
arr[lo], arr[hi] = arr[hi], arr[lo]
lo += 1
return arrIs the array entirely non-increasing or non-decreasing? One pass. O(n).
class Solution:
def is_monotonic(self, arr):
up = all(arr[i] <= arr[i+1] for i in range(len(arr)-1))
down = all(arr[i] >= arr[i+1] for i in range(len(arr)-1))
return up or downFind all triplets that sum to the target. Sort, then for each number use two pointers. O(n²).
class Solution:
def three_number_sum(self, nums, target):
nums.sort()
res = []
for i in range(len(nums) - 2):
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == target:
res.append([nums[i], nums[lo], nums[hi]]); lo += 1; hi -= 1
elif s < target: lo += 1
else: hi -= 1
return resPick one number from each array so their difference is smallest. Sort both, walk two pointers. O(n log n).
class Solution:
def smallest_difference(self, a, b):
a.sort(); b.sort()
i = j = 0; best = float("inf"); pair = []
while i < len(a) and j < len(b):
if abs(a[i] - b[j]) < best:
best = abs(a[i] - b[j]); pair = [a[i], b[j]]
if a[i] < b[j]: i += 1
elif a[i] > b[j]: j += 1
else: return [a[i], b[j]]
return pairEach output[i] = product of all other numbers — without division. Prefix & suffix products. O(n).
class Solution:
def array_of_products(self, arr):
n = len(arr); res = [1] * n
left = 1
for i in range(n):
res[i] = left; left *= arr[i]
right = 1
for i in range(n - 1, -1, -1):
res[i] *= right; right *= arr[i]
return resReturn the first value that appears twice. Hash set. O(n).
Combine overlapping [start, end] ranges. Sort by start, then merge. O(n log n).
Largest sum of any contiguous subarray. Track best ending here vs. restart. O(n).
Smallest subarray that, if sorted, makes the whole array sorted. O(n).
Longest run of consecutive integers (any order). Hash set. O(n).
Give each child ≥1 reward; a higher score than a neighbor needs more. Two passes. O(n).
Jumping by each value, do you visit every index exactly once and land back at the start? O(n).
Circular road of cities with fuel — find the only city you can start from and finish the loop. O(n).
The element appearing > n/2 times — in O(n) time, O(1) space.
Pair tasks for k workers (2 each) to minimize total time — pair fastest with slowest. O(n log n).
Smallest axis-aligned rectangle from a set of points. Check diagonal corner pairs. O(n²).
Largest sum of any size×size square. 2-D prefix sums. O(w·h).
Read a matrix in a spiral. Shrink four borders inward. O(n).
Length of the longest "up then down" run. Find each peak, expand both ways. O(n).
Sort an array containing three distinct values, in place, in one pass. O(n).
Fewest jumps to reach the end, where each value is the max jump length. Greedy. O(n).
Click a cell: a mine → "X"; otherwise show the mine count, and flood-fill zeros. "M"=mine, "H"=hidden.
All quadruplets summing to target. Hash pair-sums while scanning. Average O(n²).
class Solution:
def four_number_sum(self, nums, target):
pair_sums = {}; res = []
for i in range(1, len(nums) - 1):
for j in range(i + 1, len(nums)):
need = target - (nums[i] + nums[j])
for pair in pair_sums.get(need, []):
res.append(pair + [nums[i], nums[j]])
for k in range(i):
s = nums[i] + nums[k]
pair_sums.setdefault(s, []).append([nums[k], nums[i]])
return resBiggest rectangle in a histogram. Monotonic stack of increasing heights. O(n).
class Solution:
def largest_rectangle(self, heights):
stack = []; best = 0
for i, h in enumerate(heights + [0]): # sentinel flushes the stack
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
best = max(best, height * width)
stack.append(i)
return bestPick the block minimizing the max distance to every requirement. Precompute nearest each side. O(b·r).
class Solution:
def apartment_hunting(self, blocks, reqs):
n = len(blocks); dists = []
for req in reqs:
closest = [float("inf")] * n; nearest = float("inf")
for i in range(n):
if blocks[i][req]: nearest = i
closest[i] = abs(i - nearest)
for i in range(n - 1, -1, -1):
if blocks[i][req]: nearest = i
closest[i] = min(closest[i], abs(i - nearest))
dists.append(closest)
best, best_max = 0, float("inf")
for i in range(n):
worst = max(d[i] for d in dists)
if worst < best_max: best_max, best = worst, i
return bestWater trapped above each bar = min(tallest left, tallest right) − its height. O(n).
class Solution:
def is_palindrome(self, s):
lo, hi = 0, len(s) - 1
while lo < hi:
if s[lo] != s[hi]: return False
lo += 1; hi -= 1
return True
# or simply: return s == s[::-1]Shift each letter by a key (wrapping around the alphabet). O(n).
class Solution:
def caesar_cipher(self, s, key):
out = []
for ch in s:
code = (ord(ch) - ord("a") + key) % 26
out.append(chr(ord("a") + code))
return "".join(out)class Solution:
def first_non_repeating(self, s):
counts = {}
for ch in s: counts[ch] = counts.get(ch, 0) + 1
for i, ch in enumerate(s):
if counts[ch] == 1: return i
return -1Expand around every center (odd & even). O(n²).
class Solution:
def longest_palindrome(self, s):
res = ""
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1:r]
for i in range(len(s)):
for cand in (expand(i, i), expand(i, i+1)):
if len(cand) > len(res): res = cand
return resclass Solution:
def group_anagrams(self, words):
groups = {}
for w in words:
key = "".join(sorted(w))
groups.setdefault(key, []).append(w)
return list(groups.values())class Solution:
def valid_ip_addresses(self, s):
res = []
def ok(part):
return len(part) == 1 or (part[0] != "0" and int(part) <= 255)
for a in range(1, 4):
for b in range(a+1, a+4):
for c in range(b+1, b+4):
p1, p2, p3, p4 = s[:a], s[a:b], s[b:c], s[c:]
if 1 <= len(p4) <= 3 and all(ok(p) for p in (p1,p2,p3,p4)):
res.append(f"{p1}.{p2}.{p3}.{p4}")
return resAre two strings at most one insert/delete/replace apart? O(n).
Pick one negative (sweet) + one positive (savory) dish with sum closest to target without exceeding it. Two pointers. O(n log n).
Sliding window + a map of last-seen positions. O(n).
class Solution:
def longest_unique_substring(self, s):
seen = {}; start = 0; best = [0, 1]
for i, ch in enumerate(s):
if ch in seen and seen[ch] >= start:
start = seen[ch] + 1
if i + 1 - start > best[1] - best[0]:
best = [start, i + 1]
seen[ch] = i
return s[best[0]:best[1]]Wrap every occurrence of a substring with underscores, merging overlaps. O(n+m).
class Solution:
def underscorify_substring(self, string, substring):
locs = []; start = 0
while True:
i = string.find(substring, start)
if i == -1: break
locs.append([i, i + len(substring)]); start = i + 1
merged = []
for loc in locs:
if merged and loc[0] <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], loc[1])
else: merged.append(loc)
out = []; m = 0
for i in range(len(string) + 1):
if m < len(merged) and i == merged[m][0]: out.append("_")
if m < len(merged) and i == merged[m][1]: out.append("_"); m += 1
if i < len(string): out.append(string[i])
return "".join(out)Which small strings appear inside the big string? Build a trie of the big string's suffixes.
class Solution:
def multi_string_search(self, big, small):
trie = {}
for i in range(len(big)): # all suffixes
node = trie
for ch in big[i:]:
node = node.setdefault(ch, {})
def contains(word):
node = trie
for ch in word:
if ch not in node: return False
node = node[ch]
return True
return [contains(w) for w in small]Pattern: halve the search range each step. O(log n).
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1def binary_search_searchsort(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1def bubble_sort_searchsort(nums):
a = list(nums)
for i in range(len(a) - 1):
swapped = False
for j in range(len(a) - 1 - i):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
swapped = True
if not swapped:
break
return aFirst and last index of a target in a sorted array. Two binary searches. O(log n).
class Solution:
def search_range(self, arr, target):
def bound(left):
lo, hi, res = 0, len(arr) - 1, -1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
res = mid
if left: hi = mid - 1
else: lo = mid + 1
elif arr[mid] < target: lo = mid + 1
else: hi = mid - 1
return res
return [bound(True), bound(False)]Rows & columns both sorted. Start top-right, move left/down. O(n+m).
class Solution:
def search_matrix(self, matrix, target):
row, col = 0, len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
if matrix[row][col] == target: return [row, col]
elif matrix[row][col] > target: col -= 1
else: row += 1
return [-1, -1]class Solution:
def bubble_sort(self, a):
for i in range(len(a)):
for j in range(len(a) - 1 - i):
if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j]
return a
def insertion_sort(self, a):
for i in range(1, len(a)):
j = i
while j > 0 and a[j] < a[j-1]:
a[j], a[j-1] = a[j-1], a[j]; j -= 1
return a
def selection_sort(self, a):
for i in range(len(a)):
m = i
for j in range(i+1, len(a)):
if a[j] < a[m]: m = j
a[i], a[m] = a[m], a[i]
return aBinary search in a rotated sorted array. Decide which half is sorted each step. O(log n).
class Solution:
def shifted_binary_search(self, arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target: return mid
if arr[lo] <= arr[mid]: # left half sorted
if arr[lo] <= target < arr[mid]: hi = mid - 1
else: lo = mid + 1
else: # right half sorted
if arr[mid] < target <= arr[hi]: lo = mid + 1
else: hi = mid - 1
return -1Like quicksort but only recurse into the side with the answer. Average O(n).
class Solution:
def quickselect(self, arr, k): # k is 1-indexed position
lo, hi = 0, len(arr) - 1
while True:
pivot = arr[hi]; p = lo
for i in range(lo, hi):
if arr[i] < pivot:
arr[i], arr[p] = arr[p], arr[i]; p += 1
arr[p], arr[hi] = arr[hi], arr[p]
if p == k - 1: return arr[p]
elif p < k - 1: lo = p + 1
else: hi = p - 1Non-comparison sort for non-negative ints — bucket by each digit. O(d·n).
class Solution:
def radix_sort(self, arr):
if not arr: return arr
max_val = max(arr); exp = 1
while max_val // exp > 0:
buckets = [[] for _ in range(10)]
for num in arr:
buckets[(num // exp) % 10].append(num)
arr = [num for bucket in buckets for num in bucket]
exp *= 10
return arrHow many pairs are out of order? Piggyback on merge sort. O(n log n).
def max_sum_subarray_k(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = max(best, window)
return bestdef min_sum_subarray_k(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = min(best, window)
return bestdef average_of_subarrays_k(nums, k):
out, window = [], sum(nums[:k])
out.append(window / k)
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
out.append(window / k)
return outk consecutive numbers.Pattern: keep a running window sum; slide it instead of recomputing. O(n).
def max_subarray_sum(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k] # add new, drop old
best = max(best, window)
return bestdef length_of_longest_substring_window(s):
seen, left, best = {}, 0, 0
for right, c in enumerate(s):
if c in seen and seen[c] >= left:
left = seen[c] + 1
seen[c] = right
best = max(best, right - left + 1)
return bestdef longest_substring_k_distinct(s, k):
from collections import defaultdict
count, left, best = defaultdict(int), 0, 0
for right, c in enumerate(s):
count[c] += 1
while len(count) > k:
count[s[left]] -= 1
if count[s[left]] == 0:
del count[s[left]]
left += 1
best = max(best, right - left + 1)
return bestSmallest window of big that contains every char of small (minimum window substring). O(n).
from collections import Counter
class Solution:
def smallest_substring(self, big, small):
need = Counter(small); missing = len(small)
left = 0; best = ""
for right, ch in enumerate(big):
if need[ch] > 0: missing -= 1
need[ch] -= 1
while missing == 0: # window has everything
if not best or right - left + 1 < len(best):
best = big[left:right + 1]
need[big[left]] += 1
if need[big[left]] > 0: missing += 1
left += 1
return bestdef min_window_window(s, t):
from collections import Counter
if not t or not s:
return ""
need = Counter(t)
missing = len(t)
left = start = end = 0
for right, c in enumerate(s, 1):
if need[c] > 0:
missing -= 1
need[c] -= 1
if missing == 0:
while need[s[left]] < 0:
need[s[left]] += 1
left += 1
if end == 0 or right - left < end - start:
start, end = left, right
need[s[left]] += 1
missing += 1
left += 1
return s[start:end]def max_sliding_window(nums, k):
from collections import deque
dq, out = deque(), []
for i, n in enumerate(nums):
while dq and nums[dq[-1]] <= n:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
out.append(nums[dq[0]])
return outclass Solution:
def merge_two_lists(self, l1, l2):
dummy = Node(0); tail = dummy
while l1 and l2:
if l1.value <= l2.value: tail.next = l1; l1 = l1.next
else: tail.next = l2; l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.nextclass Solution:
def middle_node(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next; fast = fast.next.next
return slow(sorted list — drop consecutive equal nodes). O(n).
class Solution:
def dedup_sorted_list(self, head):
node = head
while node:
while node.next and node.next.value == node.value:
node.next = node.next.next
node = node.next
return headPattern: walk the list, flipping each next pointer. O(n) time, O(1) space.
def reverse_list(head):
prev = None
while head:
nxt = head.next # save the next node
head.next = prev # flip the pointer
prev = head # move prev forward
head = nxt # move head forward
return prev # new headTwo pointers k apart; when the fast one ends, slow is at the node before the target. O(n).
class Solution:
def remove_kth_from_end(self, head, k):
fast = slow = head
for _ in range(k): fast = fast.next
if fast is None: return head.next # removing the head
while fast.next:
fast = fast.next; slow = slow.next
slow.next = slow.next.next
return headTwo numbers stored as digit lists (ones digit first) — add them. O(n).
class Solution:
def sum_lists(self, l1, l2):
dummy = Node(0); cur = dummy; carry = 0
while l1 or l2 or carry:
total = carry
if l1: total += l1.value; l1 = l1.next
if l2: total += l2.value; l2 = l2.next
carry, digit = divmod(total, 10)
cur.next = Node(digit); cur = cur.next
return dummy.nextDetect where a linked list loops back. Slow/fast pointers, then reset one to the head. O(n), O(1).
Find the middle, reverse the second half, compare. O(n) time, O(1) space.
class Solution:
def is_palindrome_list(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next; fast = fast.next.next
prev = None # reverse second half
while slow:
slow.next, prev, slow = prev, slow, slow.next
left, right = head, prev
while right:
if left.value != right.value: return False
left = left.next; right = right.next
return True1→2→3→4→5 becomes 1→5→2→4→3. Split, reverse the back half, interleave. O(n).
class Solution:
def zip_linked_list(self, head):
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next; fast = fast.next.next
second = slow.next; slow.next = None
prev = None
while second:
second.next, prev, second = prev, second, second.next
first, second = head, prev
while second:
f_next, s_next = first.next, second.next
first.next = second; second.next = f_next
first, second = f_next, s_next
return headdef reverse_in_k_groups(head, k):
node = head
count = 0
while node and count < k:
node = node.next
count += 1
if count < k:
return head
prev = reverse_in_k_groups(node, k)
cur = head
for _ in range(k):
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prevdef valid_parentheses(s):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for c in s:
if c in pairs:
if not stack or stack.pop() != pairs[c]:
return False
else:
stack.append(c)
return not stackdef reverse_with_stack(s):
stack = list(s)
out = []
while stack:
out.append(stack.pop())
return ''.join(out)def baseball_game(ops):
stack = []
for op in ops:
if op == '+':
stack.append(stack[-1] + stack[-2])
elif op == 'D':
stack.append(stack[-1] * 2)
elif op == 'C':
stack.pop()
else:
stack.append(int(op))
return sum(stack)Are all brackets ()[]{} properly matched? Push opens, match on closes. O(n).
class Solution:
def balanced_brackets(self, s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stackBuildings that can see the sunset (taller than all buildings toward the direction). O(n).
class Solution:
def sunset_views(self, buildings, direction):
res, tallest = [], 0
rng = range(len(buildings)) if direction == "WEST" else range(len(buildings)-1, -1, -1)
for i in rng:
if buildings[i] > tallest:
res.append(i); tallest = buildings[i]
return res if direction == "WEST" else res[::-1]For each item, the next larger one to its right (wrapping around). Monotonic stack. O(n).
class Solution:
def next_greater(self, arr):
n = len(arr); res = [-1] * n; stack = []
for i in range(2 * n):
idx = i % n
while stack and arr[stack[-1]] < arr[idx]:
res[stack.pop()] = arr[idx]
if i < n: stack.append(idx)
return resA stack that also returns its current min & max in O(1) (store them at each level).
Find free slots ≥ duration in two people's calendars. Merge busy blocks, return the gaps.
Do two arrays produce identical BSTs? Compare roots, then left/right subsets recursively. O(n²).
class Solution:
def same_bsts(self, a, b):
if len(a) != len(b): return False
if not a: return True
if a[0] != b[0]: return False
left_a = [x for x in a[1:] if x < a[0]]
left_b = [x for x in b[1:] if x < b[0]]
right_a = [x for x in a[1:] if x >= a[0]]
right_b = [x for x in b[1:] if x >= b[0]]
return self.same_bsts(left_a, left_b) and self.same_bsts(right_a, right_b)def largest_rectangle_stacks(heights):
stack = []
best = 0
for i, h in enumerate(heights + [0]):
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
best = max(best, height * width)
stack.append(i)
return bestdef maximal_rectangle(matrix):
if not matrix:
return 0
heights = [0] * len(matrix[0])
best = 0
for row in matrix:
for i, v in enumerate(row):
heights[i] = heights[i] + 1 if v == 1 else 0
stack = []
for i, h in enumerate(heights + [0]):
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
best = max(best, height * width)
stack.append(i)
return bestclass Solution:
def find_closest(self, root, target):
closest = root.value; node = root
while node:
if abs(target - node.value) < abs(target - closest):
closest = node.value
node = node.left if target < node.value else node.right
return closestLeaves are numbers (≥0); internal nodes are operators (−1 add, −2 subtract, −3 divide, −4 multiply).
class Solution:
def evaluate_expression_tree(self, node):
if node.value >= 0: return node.value
left = self.evaluate_expression_tree(node.left)
right = self.evaluate_expression_tree(node.right)
if node.value == -1: return left + right
if node.value == -2: return left - right
if node.value == -3: return int(left / right)
return left * rightdef max_depth_trees(root):
if not root:
return 0
return 1 + max(max_depth_trees(root.left), max_depth_trees(root.right))DFS (depth-first) uses recursion / a stack; BFS (breadth-first, level by level) uses a queue.
def dfs(node): # depth-first (pre-order)
if node is None:
return
print(node.value)
dfs(node.left)
dfs(node.right)
from collections import deque
def bfs(root): # breadth-first (level order)
queue = deque([root])
while queue:
node = queue.popleft()
print(node.value)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)class Solution:
def validate_bst(self, node, lo=float("-inf"), hi=float("inf")):
if node is None: return True
if not (lo < node.value < hi): return False
return (self.validate_bst(node.left, lo, node.value) and
self.validate_bst(node.right, node.value, hi))class Solution:
def invert_tree(self, node):
if node is None: return
node.left, node.right = node.right, node.left
self.invert_tree(node.left)
self.invert_tree(node.right)Lowest common ancestor when nodes have a .parent. Equalize depths, then climb together. O(d).
Build a balanced BST from a sorted array — recurse on the middle. O(n).
Reverse in-order (right, node, left) gives values largest-first. O(h+k).
Largest sum along any path. At each node, best = node + best-left-branch + best-right-branch. O(n).
class Solution:
def max_path_sum(self, root):
best = [float("-inf")]
def helper(node):
if not node: return 0
left = max(helper(node.left), 0)
right = max(helper(node.right), 0)
best[0] = max(best[0], node.value + left + right)
return node.value + max(left, right)
helper(root)
return best[0]Sum of node depths across every subtree. O(n) with a helper that returns sum + count.
class Solution:
def all_kinds_of_node_depths(self, root):
def helper(node):
if not node: return (0, 0) # (sum_of_depths, node_count)
ls, lc = helper(node.left)
rs, rc = helper(node.right)
depth_sum = ls + lc + rs + rc # +1 depth for each descendant
return (depth_sum, lc + rc + 1)
def total(node):
if not node: return 0
return helper(node)[0] + total(node.left) + total(node.right)
return total(root)How many tree shapes with n nodes (the Catalan numbers). DP. O(n²).
class Solution:
def number_of_binary_tree_topologies(self, n):
cache = [1]
for m in range(1, n + 1):
total = 0
for left in range(m):
total += cache[left] * cache[m - 1 - left]
cache.append(total)
return cache[n]Do two trees have the same left-to-right leaf sequence?
All nodes exactly k edges from a target. Map parents, then BFS treating the tree as a graph. O(n).
def build_adjacency_list(n, edges):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
return adjdef node_degree(adj, node):
return len(adj[node])def count_edges(adj):
total = sum(len(neighbors) for neighbors in adj)
return total // 2Detect a cycle in a directed graph (adjacency list). DFS tracking the current path. O(V+E).
class Solution:
def cycle_in_graph(self, edges):
n = len(edges)
visited = [False] * n; in_path = [False] * n
def dfs(node):
visited[node] = in_path[node] = True
for nb in edges[node]:
if not visited[nb]:
if dfs(nb): return True
elif in_path[nb]:
return True
in_path[node] = False
return False
return any(dfs(i) for i in range(n) if not visited[i])Flip any group of 1s not connected to the border to 0. Mark border-connected 1s, then clear the rest. O(w·h).
class Solution:
def remove_islands(self, matrix):
rows, cols = len(matrix), len(matrix[0])
def fill(r, c):
stack = [(r, c)]
while stack:
r, c = stack.pop()
if 0 <= r < rows and 0 <= c < cols and matrix[r][c] == 1:
matrix[r][c] = 2 # mark as safe
stack += [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]
for r in range(rows):
for c in range(cols):
if (r in (0, rows-1) or c in (0, cols-1)) and matrix[r][c] == 1:
fill(r, c)
for r in range(rows):
for c in range(cols):
matrix[r][c] = 1 if matrix[r][c] == 2 else 0
return matrixSizes of every connected group of 1s in a grid. Flood-fill each. O(w·h).
class Solution:
def river_sizes(self, matrix):
sizes = []
visited = [[False] * len(matrix[0]) for _ in matrix]
for r in range(len(matrix)):
for c in range(len(matrix[0])):
if matrix[r][c] == 1 and not visited[r][c]:
size = 0; stack = [(r, c)]
while stack:
i, j = stack.pop()
if (i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0])
or visited[i][j] or matrix[i][j] == 0):
continue
visited[i][j] = True; size += 1
stack += [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]
sizes.append(size)
return sizesTrack which items are connected. Near-O(1) with path compression.
Can the graph be 2-colored so no edge joins same colors? BFS, alternate colors. O(V+E).
Order tasks so each comes after its prerequisites. Kahn's algorithm (in-degrees + queue). O(V+E).
from collections import deque
class Solution:
def topological_sort(self, jobs, deps):
graph = {j: [] for j in jobs}
indegree = {j: 0 for j in jobs}
for a, b in deps: # a must come before b
graph[a].append(b); indegree[b] += 1
queue = deque(j for j in jobs if indegree[j] == 0)
order = []
while queue:
j = queue.popleft(); order.append(j)
for nb in graph[j]:
indegree[nb] -= 1
if indegree[nb] == 0: queue.append(nb)
return order if len(order) == len(jobs) else [] # [] means a cycleShortest distance from a start node to all others (non-negative weights). Min-heap. O(E log V).
import heapq
class Solution:
def dijkstra(self, start, edges):
# edges[i] = list of [destination, weight]
dist = [float("inf")] * len(edges); dist[start] = 0
pq = [(0, start)]
while pq:
d, node = heapq.heappop(pq)
if d > dist[node]: continue
for nb, w in edges[node]:
if d + w < dist[nb]:
dist[nb] = d + w; heapq.heappush(pq, (d + w, nb))
return [-1 if d == float("inf") else d for d in dist]Find which words appear on the board (8-directional). Trie of words + DFS.
class Solution:
def boggle_board(self, board, words):
trie = {}
for w in words: # build a trie
node = trie
for ch in w: node = node.setdefault(ch, {})
node["*"] = w
rows, cols = len(board), len(board[0])
found = set()
def dfs(r, c, node, visited):
if (r < 0 or c < 0 or r >= rows or c >= cols or (r, c) in visited
or board[r][c] not in node):
return
node = node[board[r][c]]; visited = visited | {(r, c)}
if "*" in node: found.add(node["*"])
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
dfs(r + dr, c + dc, node, visited)
for r in range(rows):
for c in range(cols):
dfs(r, c, trie, set())
return list(found)Like Dijkstra but guided by a heuristic toward the goal. Min-heap on (cost + estimate).
Is there a currency cycle that multiplies to > 1? Take −log of rates → a profitable cycle is a negative cycle (Bellman-Ford). O(n³).
Cheapest set of edges connecting every node. Sort edges, add if they join two different groups (union-find). O(E log E).
def kth_largest_element(nums, k):
import heapq
return heapq.nlargest(k, nums)[-1]def kth_smallest_element(nums, k):
import heapq
return heapq.nsmallest(k, nums)[-1]def k_smallest(nums, k):
import heapq
return sorted(heapq.nsmallest(k, nums))def top_k_frequent(nums, k):
import heapq
from collections import Counter
freq = Counter(nums)
return heapq.nlargest(k, freq.keys(), key=freq.get)def k_closest_points(points, k):
import heapq
return heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2)def kth_largest_stream(k, initial, adds):
import heapq
heap = initial[:]
heapq.heapify(heap)
while len(heap) > k:
heapq.heappop(heap)
out = []
for x in adds:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
out.append(heap[0])
return outMedian of a growing stream. Keep a max-heap of the low half & a min-heap of the high half. O(log n) per add.
import heapq
class ContinuousMedian:
def __init__(self):
self.lo = [] # max-heap (store negatives)
self.hi = [] # min-heap
def add(self, num):
heapq.heappush(self.lo, -num)
heapq.heappush(self.hi, -heapq.heappop(self.lo)) # balance
if len(self.hi) > len(self.lo):
heapq.heappush(self.lo, -heapq.heappop(self.hi))
def median(self):
if len(self.lo) > len(self.hi): return -self.lo[0]
return (-self.lo[0] + self.hi[0]) / 2import heapq
class Solution:
def heap_sort(self, arr):
heapq.heapify(arr) # O(n)
return [heapq.heappop(arr) for _ in range(len(arr))] # n × O(log n)O(log(min(m,n))) by binary-searching the partition point.
class Solution:
def median_two_sorted(self, a, b):
if len(a) > len(b): a, b = b, a
m, n = len(a), len(b)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
a_l = a[i-1] if i > 0 else float("-inf")
a_r = a[i] if i < m else float("inf")
b_l = b[j-1] if j > 0 else float("-inf")
b_r = b[j] if j < n else float("inf")
if a_l <= b_r and b_l <= a_r:
if (m + n) % 2: return max(a_l, b_l)
return (max(a_l, b_l) + min(a_r, b_r)) / 2
elif a_l > b_r: hi = i - 1
else: lo = i + 1def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)def fibonacci(n, memo=None):
if memo is None:
memo = {}
if n < 2:
return n
if n in memo:
return memo[n]
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]def sum_to_n(n):
if n <= 0:
return 0
return n + sum_to_n(n - 1)class Solution:
def permutations(self, arr):
if len(arr) <= 1: return [arr[:]]
res = []
for i in range(len(arr)):
rest = arr[:i] + arr[i+1:]
for p in self.permutations(rest):
res.append([arr[i]] + p)
return resclass Solution:
def powerset(self, arr):
subsets = [[]]
for n in arr:
subsets += [s + [n] for s in subsets]
return subsets
# [1,2] -> [[], [1], [2], [1,2]]class Solution:
def phone_mnemonics(self, digits):
keys = {"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno",
"7":"pqrs","8":"tuv","9":"wxyz","0":"0","1":"1"}
res = []
def backtrack(i, cur):
if i == len(digits):
res.append("".join(cur)); return
for ch in keys[digits[i]]:
cur.append(ch); backtrack(i+1, cur); cur.pop()
backtrack(0, [])
return resWays to climb height stairs taking 1..maxSteps at a time. DP. O(n·k).
All valid arrangements of n <div></div> pairs (same idea as "generate parentheses").
Fill the grid by trying digits and backtracking when stuck. 0 = empty.
class Solution:
def solve_sudoku(self, board):
def valid(r, c, val):
for i in range(9):
if board[r][i] == val or board[i][c] == val: return False
br, bc = 3 * (r // 3), 3 * (c // 3)
for i in range(br, br + 3):
for j in range(bc, bc + 3):
if board[i][j] == val: return False
return True
def solve():
for r in range(9):
for c in range(9):
if board[r][c] == 0:
for val in range(1, 10):
if valid(r, c, val):
board[r][c] = val
if solve(): return True
board[r][c] = 0 # backtrack
return False
return True
solve()
return boardPlace N queens so none attack each other. Backtrack column by column, tracking used columns & diagonals.
class Solution:
def non_attacking_queens(self, n):
cols = set(); diag1 = set(); diag2 = set()
def place(row):
if row == n: return 1
count = 0
for col in range(n):
if col in cols or (row+col) in diag1 or (row-col) in diag2:
continue
cols.add(col); diag1.add(row+col); diag2.add(row-col)
count += place(row + 1)
cols.discard(col); diag1.discard(row+col); diag2.discard(row-col)
return count
return place(0)def total_n_queens_recursion(n):
cols = set()
diag1 = set()
diag2 = set()
def backtrack(row):
if row == n:
return 1
count = 0
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
cols.add(col); diag1.add(row - col); diag2.add(row + col)
count += backtrack(row + 1)
cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)
return count
return backtrack(0)def climbing_stairs(n):
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return bdef fib_dp(n):
if n < 2:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return bdef tribonacci(n):
if n == 0:
return 0
if n <= 2:
return 1
a, b, c = 0, 1, 1
for _ in range(3, n + 1):
a, b, c = b, c, a + b + c
return cPattern: naive recursion is O(2ⁿ). Memoize (cache) results to make it O(n).
def fib(n, memo={}):
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]class Solution:
def min_coins(self, n, denoms):
dp = [float("inf")] * (n + 1)
dp[0] = 0
for coin in denoms:
for amount in range(coin, n + 1):
dp[amount] = min(dp[amount], dp[amount - coin] + 1)
return dp[n] if dp[n] != float("inf") else -1class Solution:
def ways_to_make_change(self, n, denoms):
dp = [0] * (n + 1)
dp[0] = 1
for coin in denoms:
for amount in range(coin, n + 1):
dp[amount] += dp[amount - coin]
return dp[n]Paths from top-left to bottom-right moving only right/down. O(w·h).
Fewest spaces to break a digit string into "known" numbers. Memoized recursion. O(n³).
class Solution:
def numbers_in_pi(self, pi, numbers):
known = set(numbers); cache = {}
def helper(idx):
if idx == len(pi): return -1 # -1 cancels the last +1
if idx in cache: return cache[idx]
best = float("inf")
for i in range(idx, len(pi)):
if pi[idx:i+1] in known:
best = min(best, 1 + helper(i + 1))
cache[idx] = best
return best
result = helper(0)
return -1 if result == float("inf") else resultclass Solution:
def max_profit_k(self, prices, k):
if not prices: return 0
dp = [0] * len(prices)
for _ in range(k):
max_diff = -prices[0]; new = [0] * len(prices)
for d in range(1, len(prices)):
new[d] = max(new[d-1], prices[d] + max_diff)
max_diff = max(max_diff, dp[d] - prices[d])
dp = new
return dp[-1]class Solution:
def dice_throws(self, num_dice, num_sides, target):
dp = [[0] * (target + 1) for _ in range(num_dice + 1)]
dp[0][0] = 1
for d in range(1, num_dice + 1):
for t in range(1, target + 1):
for s in range(1, min(t, num_sides) + 1):
dp[d][t] += dp[d-1][t-s]
return dp[num_dice][target]Tallest stack of disks where each must be strictly smaller in all 3 dimensions. DP after sorting by height. O(n²).
Is three an interleaving of one and two (keeping each one's order)? Memoized recursion. O(n·m).
Longest chain where each word becomes the next by adding one letter. Sort by length, DP. O(n·L²).
Fewest cuts so every piece is a palindrome. Precompute palindromes, then DP. O(n²).
Maximize value within a weight capacity. Classic 2-D DP. O(n·capacity).
def array_pair_sum(nums):
nums.sort()
return sum(nums[::2])def maximum_units(boxes, truck_size):
boxes.sort(key=lambda b: -b[1])
total = 0
for count, units in boxes:
take = min(count, truck_size)
total += take * units
truck_size -= take
if truck_size == 0:
break
return totaldef largest_perimeter(nums):
nums.sort(reverse=True)
for i in range(len(nums) - 2):
if nums[i] < nums[i + 1] + nums[i + 2]:
return nums[i] + nums[i + 1] + nums[i + 2]
return 0def can_jump_greedy(nums):
reach = 0
for i, n in enumerate(nums):
if i > reach:
return False
reach = max(reach, i + n)
return Truedef jump_greedy(nums):
jumps = cur_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == cur_end:
jumps += 1
cur_end = farthest
return jumpsdef can_complete_circuit_greedy(gas, cost):
if sum(gas) < sum(cost):
return -1
total = start = 0
for i in range(len(gas)):
total += gas[i] - cost[i]
if total < 0:
total = 0
start = i + 1
return startdef candy_greedy(ratings):
n = len(ratings)
give = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
give[i] = give[i - 1] + 1
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
give[i] = max(give[i], give[i + 1] + 1)
return sum(give)def remove_k_digits(num, k):
stack = []
for d in num:
while k and stack and stack[-1] > d:
stack.pop(); k -= 1
stack.append(d)
stack = stack[:len(stack) - k] if k else stack
return ''.join(stack).lstrip('0') or '0'def reorganize_string(s):
import heapq
from collections import Counter
heap = [(-c, ch) for ch, c in Counter(s).items()]
heapq.heapify(heap)
prev = None
out = []
while heap:
cnt, ch = heapq.heappop(heap)
out.append(ch)
if prev and prev[0] < 0:
heapq.heappush(heap, prev)
prev = (cnt + 1, ch)
result = ''.join(out)
return result if len(result) == len(s) else ''class MinStack:
def __init__(self):
self.stack = []
self.mins = []
def push(self, x):
self.stack.append(x)
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.mins.pop()
return self.stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.mins[-1]
def min_stack_ops(ops):
obj = MinStack()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] in ('top', 'getMin') else None)
return outclass MyQueue:
def __init__(self):
self.a = []
self.b = []
def push(self, x):
self.a.append(x)
def _shift(self):
if not self.b:
while self.a:
self.b.append(self.a.pop())
def pop(self):
self._shift()
return self.b.pop()
def peek(self):
self._shift()
return self.b[-1]
def empty(self):
return not self.a and not self.b
def queue_using_stacks(ops):
obj = MyQueue()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] in ('pop', 'peek', 'empty') else None)
return outfrom collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x):
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return not self.q
def stack_using_queues(ops):
obj = MyStack()
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] in ('pop', 'top', 'empty') else None)
return outclass BST:
def __init__(self, value):
self.value = value; self.left = None; self.right = None
def insert(self, value):
node = self
while True:
if value < node.value:
if node.left is None: node.left = BST(value); break
node = node.left
else:
if node.right is None: node.right = BST(value); break
node = node.right
return self
def contains(self, value):
node = self
while node:
if value < node.value: node = node.left
elif value > node.value: node = node.right
else: return True
return Falseimport heapq
nums = [5, 2, 8, 1]
heapq.heapify(nums) # O(n) -> smallest is always nums[0]
heapq.heappush(nums, 3) # O(log n)
smallest = heapq.heappop(nums) # remove + return the min, O(log n)
# Max-heap trick: push/pop the NEGATIVE of each valueclass SuffixTrie:
def __init__(self, string):
self.root = {}; self.end = "*"
for i in range(len(string)):
self._insert(string[i:])
def _insert(self, s):
node = self.root
for ch in s: node = node.setdefault(ch, {})
node[self.end] = True
def contains(self, s):
node = self.root
for ch in s:
if ch not in node: return False
node = node[ch]
return self.end in nodeGet/put in O(1), evicting the least-recently-used item. An OrderedDict does the heavy lifting.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict(); self.capacity = capacity
def get(self, key):
if key not in self.cache: return -1
self.cache.move_to_end(key) # mark most-recently-used
return self.cache[key]
def put(self, key, value):
if key in self.cache: self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # evict least-recently-usedFind a pattern in text in O(n+m) using a precomputed "failure" table.
class Solution:
def kmp_search(self, text, pattern):
lps = [0] * len(pattern) # longest prefix = suffix table
k = 0
for i in range(1, len(pattern)):
while k > 0 and pattern[i] != pattern[k]: k = lps[k-1]
if pattern[i] == pattern[k]: k += 1
lps[i] = k
j = 0
for i in range(len(text)):
while j > 0 and text[i] != pattern[j]: j = lps[j-1]
if text[i] == pattern[j]: j += 1
if j == len(pattern): return i - j + 1 # start index of match
return -1from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity):
self.cap = capacity
self.vals = {}
self.freq = {}
self.groups = defaultdict(OrderedDict)
self.min_freq = 0
def _bump(self, key):
f = self.freq[key]
del self.groups[f][key]
if not self.groups[f]:
del self.groups[f]
if self.min_freq == f:
self.min_freq += 1
self.freq[key] = f + 1
self.groups[f + 1][key] = None
def get(self, key):
if key not in self.vals:
return -1
self._bump(key)
return self.vals[key]
def put(self, key, value):
if self.cap == 0:
return
if key in self.vals:
self.vals[key] = value
self._bump(key)
return
if len(self.vals) >= self.cap:
evict, _ = self.groups[self.min_freq].popitem(last=False)
del self.vals[evict]
del self.freq[evict]
self.vals[key] = value
self.freq[key] = 1
self.groups[1][key] = None
self.min_freq = 1
def lfu_cache_ops(capacity, ops):
obj = LFUCache(capacity)
out = []
for op in ops:
r = getattr(obj, op[0])(*op[1:])
out.append(r if op[0] == 'get' else None)
return outIterative binary search with the overflow-safe midpoint. O(log n) time, O(1) space.
public static int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoids (lo+hi) overflow
if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // not found
} static void reverse(int[] a) {
int lo = 0, hi = a.length - 1;
while (lo < hi) {
int tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp;
lo++; hi--;
}
} static List<String> fizzBuzz(int n) {
List<String> res = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (i % 15 == 0) res.add("FizzBuzz");
else if (i % 3 == 0) res.add("Fizz");
else if (i % 5 == 0) res.add("Buzz");
else res.add(String.valueOf(i));
}
return res;
}Queue-based BFS over an adjacency map. Mark nodes seen at enqueue time so cycles can't loop. O(V+E).
import java.util.*;
public static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
List<Integer> order = new ArrayList<>();
Set<Integer> seen = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(start); seen.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int next : graph.getOrDefault(node, List.of())) {
if (!seen.contains(next)) { // seen-before-enqueue stops cycles
seen.add(next);
queue.add(next);
}
}
}
return order;
}Bottom-up DP — the plagiarism-detector algorithm in Java. O(n·m) time and space.
public static int lcs(String a, String b) {
int n = a.length(), m = b.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1))
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n][m];
} static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) return new int[]{seen.get(need), i};
seen.put(nums[i], i);
}
return new int[]{-1, -1};
}Levenshtein distance, bottom-up. O(n·m).
public static int editDistance(String a, String b) {
int n = a.length(), m = b.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) dp[i][0] = i; // delete all of a[:i]
for (int j = 0; j <= m; j++) dp[0][j] = j; // insert all of b[:j]
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
return dp[n][m];
}The same design as the Python version, in idiomatic Java with a HashMap collection.
import java.util.*;
class Book {
int id; String title; List<String> content; int lastPage = 0;
Book(int id, String title, List<String> content) {
this.id = id; this.title = title; this.content = content;
}
String displayPage() { return content.get(lastPage); }
String turnPage() {
if (lastPage < content.size() - 1) lastPage++;
return displayPage();
}
}
class Library {
private Map<Integer, Book> collection = new HashMap<>();
private Integer activeId = null;
private int nextId = 0;
int addBook(String title, List<String> content) {
Book b = new Book(nextId++, title, content);
collection.put(b.id, b);
return b.id;
}
void removeBook(int id) {
collection.remove(id);
if (activeId != null && activeId == id) activeId = null;
}
void setActive(int id) { if (collection.containsKey(id)) activeId = id; }
String displayPage() { return activeId == null ? null : collection.get(activeId).displayPage(); }
String turnPage() { return activeId == null ? null : collection.get(activeId).turnPage(); }
} static int[] dijkstra(int[][] graph, int src) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
boolean[] done = new boolean[n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.add(new int[]{src, 0});
while (!pq.isEmpty()) {
int u = pq.poll()[0];
if (done[u]) continue;
done[u] = true;
for (int v = 0; v < n; v++) {
if (graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
pq.add(new int[]{v, dist[v]});
}
}
}
return dist;
}Integration roles live on this: call a REST endpoint that returns a JSON list of orders and aggregate revenue per product, highest first. Standard library only — no external packages.
import json, urllib.request
from collections import defaultdict
def revenue_by_product(url):
with urllib.request.urlopen(url, timeout=10) as resp:
orders = json.load(resp) # [{"product": "...", "price": 9.99, "qty": 2}, ...]
totals = defaultdict(float)
for o in orders:
totals[o["product"]] += o["price"] * o["qty"]
# highest-grossing first
return sorted(totals.items(), key=lambda kv: kv[1], reverse=True)From Orders(id, customer_id, amount), list customers with more than 3 orders plus their total spend, biggest spenders first. Tests GROUP BY / HAVING / ORDER BY.
SELECT customer_id,
COUNT(*) AS order_count,
SUM(amount) AS total_spent
FROM Orders
GROUP BY customer_id
HAVING COUNT(*) > 3
ORDER BY total_spent DESC;Every listing wants tests, code reviews and Agile. Given is_valid_email, write tests that cover the happy path and the edge cases (missing @, empty, double @). Interviewers love when you test before you trust the code.
import unittest
def is_valid_email(s):
return s.count("@") == 1 and "." in s.split("@")[1]
class TestEmail(unittest.TestCase):
def test_valid(self): self.assertTrue(is_valid_email("[email protected]"))
def test_no_at(self): self.assertFalse(is_valid_email("abc.com"))
def test_empty(self): self.assertFalse(is_valid_email(""))
def test_two_ats(self): self.assertFalse(is_valid_email("a@@b.com"))
if __name__ == "__main__":
unittest.main()To flag plagiarism between two stories, find the length of their longest shared subsequence of characters (same order, but gaps allowed). The naive "try every substring" approach is exponential; memoized recursion is O(n·m). Then run it over every pair of books to surface the most-likely match.
from functools import lru_cache
def longest_common_subsequence(a, b):
@lru_cache(maxsize=None)
def lcs(i, j):
if i == len(a) or j == len(b):
return 0
if a[i] == b[j]:
return 1 + lcs(i + 1, j + 1) # match -> advance both
return max(lcs(i + 1, j), lcs(i, j + 1)) # else skip one side
return lcs(0, 0)
def most_likely_plagiarism(books): # books: list[(title, text)]
best = (0, None, None)
for i in range(len(books)):
for j in range(i + 1, len(books)):
score = longest_common_subsequence(books[i][1], books[j][1])
if score > best[0]:
best = (score, books[i][0], books[j][0])
return best # (shared_chars, titleA, titleB)SQL was the single most-requested hard skill across the listings. From Employee(id, name, salary), return the second-highest distinct salary (return NULL if there isn't one). Know both the sub-query and the window-function answer.
-- Classic sub-query
SELECT MAX(salary) AS second_highest
FROM Employee
WHERE salary < (SELECT MAX(salary) FROM Employee);
-- Modern, scales to "Nth highest" (window function)
SELECT DISTINCT salary AS second_highest
FROM (
SELECT salary,
DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
FROM Employee
) ranked
WHERE rnk = 2;Join + correlated sub-query, a daily-driver pattern for data roles. List each department and the employee(s) earning the most within that department.
SELECT d.name AS department,
e.name AS employee,
e.salary
FROM Employee e
JOIN Department d ON e.dept_id = d.id
WHERE e.salary = (
SELECT MAX(e2.salary)
FROM Employee e2
WHERE e2.dept_id = e.dept_id
)
ORDER BY d.name;Design the core classes for an online cloud reading app (think Kindle, but for indie short stories). Requirements: a user has a library of books they can add to / remove from; they can set one book active; the app remembers where they left off in each book; and it shows one page at a time of the active book. Keep the Book and Library responsibilities separate so the storage format can change later.
class Book:
"""One story. content = list of page-strings; remembers the reader's spot."""
def __init__(self, book_id, title, content):
self.id = book_id
self.title = title
self.content = content # list[str], one entry per page
self.last_page = 0 # index into content
def display_page(self):
return self.content[self.last_page]
def turn_page(self):
if self.last_page < len(self.content) - 1:
self.last_page += 1
return self.display_page()
class Library:
"""A reader's collection of books + which one is open right now."""
def __init__(self):
self.collection = {} # id -> Book (dict = O(1) lookup)
self.active_id = None
self._next_id = 0 # simple unique-id generator
def add_book(self, title, content):
book = Book(self._next_id, title, content)
self.collection[book.id] = book
self._next_id += 1
return book.id
def remove_book(self, book_id):
self.collection.pop(book_id, None)
if self.active_id == book_id:
self.active_id = None
def set_active(self, book_id):
if book_id in self.collection:
self.active_id = book_id
def display_page(self):
if self.active_id is None: return None
return self.collection[self.active_id].display_page()
def turn_page(self):
if self.active_id is None: return None
return self.collection[self.active_id].turn_page()
# Follow-ups the interviewer will ask:
# • Bigger font? Store content as ONE string + a Display class that computes
# chars_per_page from font_size, then page n = content[n*cpp : (n+1)*cpp].
# • Many users sharing books? Store each Book ONCE (e.g. a SQL table keyed by a
# global id); keep per-user state (active_id, last_page) in a separate UserState.The other DP every fuzzy-matching/plagiarism system uses: minimum single-character insert / delete / replace edits to turn string a into b. Bottom-up table, O(n·m).
def edit_distance(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1): dp[i][0] = i # delete all of a[:i]
for j in range(m + 1): dp[0][j] = j # insert all of b[:j]
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] # chars match -> free
else:
dp[i][j] = 1 + min(dp[i-1][j], # delete
dp[i][j-1], # insert
dp[i-1][j-1]) # replace
return dp[n][m]def compare_versions(a, b):
pa = [int(x) for x in a.split('.')]
pb = [int(x) for x in b.split('.')]
length = max(len(pa), len(pb))
pa += [0] * (length - len(pa))
pb += [0] * (length - len(pb))
for x, y in zip(pa, pb):
if x < y:
return -1
if x > y:
return 1
return 0Pulled straight from what 2026 job listings actually ask for — across data, finance, cloud and full-stack roles the recurring hard skills are SQL, OOP/system design, dynamic programming, APIs/JSON and unit testing. These are worked end-to-end, the way a real 45-minute interview runs (design first, then an algorithm). The two headline problems below are the exact format of a full-length mock interview: an open-ended OOP design, then a DP algorithm.
Max profit picking jobs (1 day each) by their deadlines within a 7-day week. Greedy by pay.
class Solution:
def optimal_freelancing(self, jobs):
LIMIT = 7
jobs.sort(key=lambda j: j["payment"], reverse=True)
taken = [False] * LIMIT; profit = 0
for job in jobs:
for day in range(min(job["deadline"], LIMIT) - 1, -1, -1):
if not taken[day]:
taken[day] = True; profit += job["payment"]; break
return profitMin total moves for two knights to land on the same square. BFS from one; they move alternately.
from collections import deque
class Solution:
def knight_connection(self, a, b):
moves = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]
q = deque([(a[0], a[1], 0)]); seen = {tuple(a)}
while q:
r, c, d = q.popleft()
if [r, c] == b: return (d + 1) // 2
for dr, dc in moves:
nxt = (r + dr, c + dc)
if nxt not in seen:
seen.add(nxt); q.append((nxt[0], nxt[1], d + 1))Can one cut split the tree into two equal-sum halves? Returns that half-sum or 0.
class Solution:
def split_binary_tree(self, tree):
def total(node):
return 0 if not node else node.value + total(node.left) + total(node.right)
whole = total(tree)
if whole % 2: return 0
found = [False]
def helper(node):
if not node: return 0
s = node.value + helper(node.left) + helper(node.right)
if s == whole // 2: found[0] = True
return s
helper(tree)
return whole // 2 if found[0] else 0Where two lists join. Swap each pointer to the other list's head when it ends — they meet at the join. O(n).
class Solution:
def merging_linked_lists(self, l1, l2):
a, b = l1, l2
while a != b:
a = a.next if a else l2
b = b.next if b else l1
return a # the shared node (or None)Split N liters into bottle sizes to maximize total price (like rod-cutting), returning the split. O(n²).
Does any subarray sum to 0? If a running sum repeats, the slice between is 0. O(n).
Each pass, positives convert their negative neighbors. How many passes to flip all? Multi-source BFS. O(w·h).
Positive = moving right, negative = left. Use a stack; resolve collisions. O(n).
Longest run of valid () parentheses. Stack of indices. O(n).
class Solution:
def longest_balanced(self, s):
stack = [-1]; longest = 0
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
else:
stack.pop()
if not stack: stack.append(i)
else: longest = max(longest, i - stack[-1])
return longestFor each element, how many to its right are smaller. Insert into a sorted list from the right. O(n²) (O(n log n) with a BIT).
import bisect
class Solution:
def right_smaller_than(self, arr):
res = [0] * len(arr); sorted_seen = []
for i in range(len(arr) - 1, -1, -1):
pos = bisect.bisect_left(sorted_seen, arr[i])
res[i] = pos
sorted_seen.insert(pos, arr[i])
return resMaximize a[i]−a[j]+a[k]−a[l] for i<j<k<l. Build four running-best arrays. O(n).
class Solution:
def maximize_expression(self, arr):
n = len(arr)
if n < 4: return 0
maxA = [arr[0]] * n
for i in range(1, n): maxA[i] = max(maxA[i-1], arr[i])
maxAB = [float("-inf")] * n
for i in range(1, n): maxAB[i] = max(maxAB[i-1], maxA[i-1] - arr[i])
maxABC = [float("-inf")] * n
for i in range(2, n): maxABC[i] = max(maxABC[i-1], maxAB[i-1] + arr[i])
maxABCD = [float("-inf")] * n
for i in range(3, n): maxABCD[i] = max(maxABCD[i-1], maxABC[i-1] - arr[i])
return maxABCD[n-1]An in-order walk of a BST is sorted — the two out-of-order nodes are the swapped pair. O(n).
Is the middle node a descendant of one outer node and an ancestor of the other? O(h).
Max points on a single straight line. Group by reduced slope (use gcd to normalize). O(n²).
Match interns ↔ teams so no pair would both rather swap. The classic stable-matching algorithm.
Shortest prefix of each word that no other word shares. Trie with counts. O(total chars).
Is there a square whose border is all 0s? Precompute consecutive zeros right/down, then check each square. O(n³).
Min possible max-station-time when splitting ordered steps across k stations. Binary-search the answer. O(n log(sum)).
Given a pattern of x's & y's, find strings for x and y that rebuild s. Try every length of x. O(n²).
Rewire every node's right to point to its sibling on the same level. Recurse left before mutating right.
Fewest new routes so every airport is reachable from the start. Score unreachable airports by how many other unreachable ones they unlock; add greedily.
Biggest rectangle of empty land (0s) in a grid. Row-by-row histogram + largest-rectangle. O(rows·cols).
Chance the dealer busts (goes over the target). Dealer draws (cards 1–10) until within 4 of target. Memoized.
Is the graph connected with no "bridge" edges (every edge lies on a cycle)? DFS arrival/low times (Tarjan). O(V+E).
How many squares can be formed from a set of points? Check each pair as a diagonal. O(n²).
Flip one water cell to land — what's the biggest land block possible? Label regions, then test each water cell. O(w·h).
Every element is at most k spots from its sorted position. A size-(k+1) min-heap. O(n log k).
Rotate a list by k. Make it circular, then break it at the right spot. O(n).
LCA on an org chart (n-ary tree, no parent links). Count how many of the two appear in each subtree. O(n).
Can imprecise measuring cups produce a target range? Memoized recursion.
Simplify a Unix-style path (handle ., .., extra slashes). Stack. O(n).
Reorder so everything < k comes before == k before > k. Build three sublists, then stitch. O(n).
Min laptops for overlapping rental times. Sort starts & ends, sweep with two pointers. O(n log n).
Which big strings can be built by concatenating the smaller ones (word-break)? DP per string. O(n·L²).
Longest prefix shared by the most strings. Build a counting trie, then follow the most-visited path. O(total chars).
Water poured at a source flows down, splitting 50/50 around walls (1s). Return how much reaches each bottom slot. Row-by-row simulation; carry % as negatives.
Merge nums2 into nums1 in place — fill from the back to avoid overwriting. O(m+n).
class Solution:
def merge(self, nums1, m, nums2, n):
i, j, k = m - 1, n - 1, m + n - 1
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[k] = nums1[i]; i -= 1
else:
nums1[k] = nums2[j]; j -= 1
k -= 1class Solution:
def remove_element(self, nums, val):
k = 0
for n in nums:
if n != val: nums[k] = n; k += 1
return kclass Solution:
def remove_duplicates(self, nums):
if not nums: return 0
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[k-1]:
nums[k] = nums[i]; k += 1
return kclass Solution:
def remove_duplicates_ii(self, nums):
k = 0
for n in nums:
if k < 2 or n != nums[k-2]:
nums[k] = n; k += 1
return kclass Solution:
def rotate(self, nums, k):
k %= len(nums)
nums[:] = nums[-k:] + nums[:-k]Unlimited trades → grab every upward step. O(n).
class Solution:
def max_profit_ii(self, prices):
return sum(max(0, prices[i] - prices[i-1]) for i in range(1, len(prices)))Array for O(1) random + dict of value→index; on remove, swap with the last element.
Prefix products left-to-right, then multiply by suffix products right-to-left. No division. O(n).
Two passes: reward left-to-right for rising ratings, then right-to-left. O(n).
class Solution:
def candy(self, ratings):
n = len(ratings); c = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i-1]: c[i] = c[i-1] + 1
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i+1]: c[i] = max(c[i], c[i+1] + 1)
return sum(c)class Solution:
def trap(self, height):
left, right = 0, len(height) - 1
left_max = right_max = water = 0
while left < right:
if height[left] < height[right]:
left_max = max(left_max, height[left])
water += left_max - height[left]; left += 1
else:
right_max = max(right_max, height[right])
water += right_max - height[right]; right -= 1
return waterGreedily pack words per line, then distribute spaces evenly (extra spaces go to the left gaps); last line is left-justified.
class Solution:
def full_justify(self, words, max_width):
res = []; line = []; length = 0
for w in words:
if length + len(line) + len(w) > max_width:
slots = max(1, len(line) - 1)
for i in range(max_width - length):
line[i % slots] += " "
res.append("".join(line)); line = []; length = 0
line.append(w); length += len(w)
res.append(" ".join(line).ljust(max_width))
return resSort, fix one number, then two-pointer the rest. Skip duplicates. O(n²).
Expand right to cover all needed chars, then shrink left while still valid. O(n).
Pop the top row, rotate the rest counter-clockwise, repeat. O(m·n).
Encode next state in bit 2 so neighbors still read the old state (bit 1), then shift. O(m·n), O(1) space.
Put all in a set; only start counting from numbers with no left neighbor. O(n).
Sort by end, shoot at each non-overlapping end. Greedy. O(n log n).
Handle + - ( ). Push the running result & sign on (, fold back on ). O(n).
Map each old node to its clone, then wire up next/random. O(n).
An OrderedDict gives O(1) get/put with recency tracking (move_to_end).
First preorder value is the root; its index in inorder splits left/right. O(n).
Use the already-linked current level to build the next level's next chain. O(n), O(1) extra.
If left and right heights match, it's a perfect subtree → 2^h − 1. Otherwise recurse. O(log²n).
In-order visits values sorted → the min gap is between adjacent values. O(n).
Any 'O' connected to the border survives — mark those first, flip the rest. O(m·n).
Build a weighted graph (a/b = v, b/a = 1/v); each query is a DFS multiplying edge weights.
Detect a cycle in the prereq graph via 3-color DFS. O(V+E).
Kahn's topological sort (BFS on in-degrees). O(V+E).
Put all words in a trie, then DFS the board once, pruning by trie paths.
Answer is either a normal Kadane max, or total − (minimum subarray), whichever's bigger. Guard the all-negative case.
Treat the matrix as one sorted array of length rows·cols. O(log(mn)).
One half is always sorted — check which, then decide which side to keep. O(log n).
Binary-search a partition of the smaller array so left halves ≤ right halves. O(log(min(m,n))).
Greedy: among all affordable projects, always take the most profitable. Max-heap of profits. O(n log n).
Two heaps: a max-heap for the lower half, a min-heap for the upper. Median is the top(s). O(log n) per add.
The result is the common binary prefix of left & right. Shift both right until equal. O(log n).
Count factors of 5 in n! (each pairs with a 2 to make a trailing zero). O(log n).
Patience sorting: keep the smallest tail for each length. O(n log n).
Expand around each center (odd and even length). O(n²).
dp[r][c] = side of the largest all-1 square ending at (r,c) = 1 + min of its top/left/diagonal. O(m·n).
Coding is only half the interview. A typical CS interview runs intro → resume/projects → coding → behavioral → your questions. These parts are free here because they win (or lose) you offers just as often as the algorithm does.
Situation → Task → Action → Result. Set the scene in a sentence, say what you were responsible for, explain what you specifically did, then finish with a concrete (ideally measurable) result. Aim for ~90 seconds.
"What does success look like in the first 90 days?" · "How does the team handle code review and testing?" · "What's the biggest technical challenge the team is facing right now?" · "How do you support growth for early-career engineers?" Asking nothing signals low interest — always ask at least two.
Crisp, correct answers to the conceptual questions that come up constantly (languages, OOP, memory/OS, databases, architecture & process). Free to read — tap any question.
InputStream/OutputStream vs Reader/Writer.free() manually (Java, Python, C#). The GC tracks references and frees unreachable objects; the trade-off is occasional pauses and less control. In manual languages (C/C++) you allocate (malloc/new) and must deallocate (free/delete) yourself, or you leak memory.JOIN tables when you need the combined view.(distance, node), repeatedly pop the closest unvisited node and relax its edges (update neighbor distances). O((V+E) log V). For graphs with negative weights use Bellman-Ford; for an unweighted graph plain BFS already gives the shortest path. (Dijkstra skeleton is in the Code templates section.)