Deep dive

Coding interview playbook

Getting the optimal solution is only part of the score. Interviewers grade how you get there: clarifying, reasoning out loud, writing clean code, and testing it yourself.

The formats you'll meet

What you're scored on

How to spend 45 minutes

1. 0–5 · Clarify. Restate the problem. Ask about input size, ranges, duplicates, negatives, empty input, and the output format. Write down one example and one edge case.
2. 5–12 · Brute force, then improve. Say the naive approach and its Big-O. Name the bottleneck ("the inner loop searches for the complement"). Match it to a pattern ("a hash map makes that lookup O(1)").
3. 12–15 · Agree on the plan. "I'll use X, giving O(n) time and O(n) space. Sound good?" Only code once the interviewer agrees.
4. 15–35 · Code while narrating. Use helper functions for clarity. If you're unsure about a detail, say so and leave a # TODO instead of stalling.
5. 35–42 · Test. Trace your example line by line, then the edge cases. Fix bugs calmly. Finding your own bug is a positive signal.
6. 42–45 · Wrap up. Restate the complexity, mention possible improvements, and answer follow-ups.

Clarifying questions checklist

Phrases that show your thinking

"Let me restate it to make sure I understand: ..."
"The brute force checks every pair, O(n²). With n up to 10^5 that's too slow."
"The repeated work is searching for the complement, so I'll store what I've seen in a hash map."
"This is a 'longest substring with a constraint' problem, so I'm thinking sliding window."
"Let me trace through [2, 7, 11] with target 9 to check the indexes."
"Edge cases: empty array, one element, and no valid pair. Let me check each."
"Time is O(n): one pass, with O(1) hash operations. Space is O(n) for the map."

When you're stuck

• Solve a tiny example by hand, then ask yourself what your brain just did.
• Ask: would sorting help? A hash map? Two pointers? Thinking in reverse? A heap?
• Go through the cheat sheet in the crash course toolkit, from top to bottom.
• Say what you're considering out loud. Interviewers often hint when they can see where you are. Taking a hint costs far less than staying silent.

Common ways to fail

• Starting to code before agreeing on an approach.
• Ignoring the constraints and writing O(n²) for n = 10⁵.
• Not knowing your language: sort with a key, heapq, deque, Counter, bisect, string methods.
• Never testing, or testing only the happy path.
• Getting defensive about hints or bugs.

An 8-week study plan

• 2–3 new problems a day, plus re-solving one from a few days ago (spaced repetition beats volume).
• Stuck for 25 minutes? Read the solution, understand it, close it, and re-code it two days later without looking.
• Keep a log: problem, pattern, the key insight in one line, and mistakes made. Review it before interviews.
• Do at least 3–5 mock interviews with another person. Talking while coding is a separate skill.

Deep dive

Complexity analysis

Big-O describes how the work grows as the input grows. It ignores the machine and the constants and keeps only the shape of the growth. It is how you know a solution will pass before you run it.

Five rules for counting

1. Steps in sequence add. A loop over n followed by another loop over n is O(n + n) = O(n).
2. Nested steps multiply. A loop over n inside a loop over m is O(n · m).
3. Keep the biggest term and drop constants. O(3n² + 10n + 7) is O(n²). For large n the biggest term dominates everything else.
4. Different inputs get different letters. Looping over string a and, inside it, string b is O(a · b), not O(n²).
5. Halving gives a log. If each step cuts the remaining work in half, you need about log₂(n) steps. log₂(1,000,000) ≈ 20, so O(log n) is almost free.

Common complexities, fastest to slowest

Cost of recursion: count the call tree

Total time = number of calls × work per call. When a function calls itself twice and goes n levels deep, the calls form a tree with about 2ⁿ nodes. The tree below is plain recursive Fibonacci. The yellow nodes are the same call computed again. Remembering those answers is exactly what dynamic programming does.

• Two branches, depth n: O(2ⁿ). With memoization each distinct call runs once: O(n).
• Merge sort: depth log n, and each level does O(n) total work: O(n log n).
• Binary search: one branch, depth log n: O(log n).

Space complexity

• Count the extra memory you create: a set of n items is O(n), a few variables are O(1).
• Recursion uses memory. Each pending call sits on the call stack, so DFS on a tree of height h uses O(h). For a tree that's one long chain, h = n.
• The output you must return is usually not counted.
• Python's default recursion limit is about 1000 calls. For deeper recursion, use sys.setrecursionlimit or an explicit stack.

Amortized O(1)

A Python list reserves extra capacity. When it fills, it copies everything into a block about twice as big. That copy is O(n), but it happens so rarely that n appends cost O(n) in total, so each append is O(1) amortized (on average across many calls).

Hidden costs in Python

One problem, three trade-offs

def has_dup(a):            # O(n²) time, O(1) space: compare every pair
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] == a[j]: return True
    return False

def has_dup(a):            # O(n) time, O(n) space: spend memory to save time
    return len(set(a)) != len(a)

def has_dup(a):            # O(n log n) time, O(1) extra: sort, then compare neighbours
    a.sort()
    return any(a[i] == a[i + 1] for i in range(len(a) - 1))

All three are correct. Choosing between them by time and memory is what interviewers want to hear you discuss.

Check yourself

i = 1
while i < n:
    i *= 2

for i in range(n):
    for j in range(i, n):
        print(i, j)

for x in a:            # len(a) = n
    if x in b_set:     # set of size m
        count += 1

Deep dive

Arrays & strings

An array stores items in one continuous block of memory. That's why reading any index is instant and inserting in the middle is slow.

How it works

• The address of item i is start + i × item_size. One multiplication, so a[i] is O(1).
• Inserting or deleting in the middle forces every later item to shift by one slot: O(n).
• A Python list is a dynamic array. It grows automatically, and append/pop at the end are O(1).
• Strings are arrays of characters, but immutable in Python. Every "change" builds a new string.

Technique 1 · Prefix sums

Precompute running totals once in O(n). After that, the sum of any range is one subtraction: sum(a[l..r]) = pre[r+1] − pre[l]. Use it whenever a problem asks for many range sums, or for "subarray sum equals k" together with a hash map.

pre = [0]
for x in nums:
    pre.append(pre[-1] + x)      # pre[i] = sum of nums[0..i-1]

def range_sum(l, r):             # inclusive l..r, O(1)
    return pre[r + 1] - pre[l]

Technique 2 · Kadane's algorithm (maximum subarray)

Walk left to right, keeping the best sum of a subarray that ends here. If the running sum goes negative, it can only hurt what comes next, so start fresh.

def maxSubArray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)    # extend the old subarray or start a new one at x
        best = max(best, cur)
    return best

Technique 3 · In-place with a write pointer

def moveZeroes(nums):
    w = 0                        # next position to write a kept item
    for x in nums:
        if x != 0:
            nums[w] = x; w += 1
    for i in range(w, len(nums)):
        nums[i] = 0

Technique 4 · Counting letters with a fixed array

cnt = [0] * 26
for ch in s:
    cnt[ord(ch) - ord('a')] += 1   # 'a' -> 0, 'b' -> 1, ...
# tuple(cnt) is hashable, so it can be a dict key (useful for anagram grouping)

2D arrays (matrices and grids)

R, C = len(grid), len(grid[0])
grid = [[0] * C for _ in range(R)]   # correct
bad  = [[0] * C] * R                 # WRONG: R references to the SAME row
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dr, dc in DIRS:
    nr, nc = r + dr, c + dc
    if 0 <= nr < R and 0 <= nc < C: ...

Common mistakes

• Off-by-one errors: is the end index inclusive or exclusive? Decide and write it down.
• Removing items from a list while looping over it. Build a new list or use a write pointer.
• Forgetting empty input, a single item, or all-equal items.
• Building strings with += in a loop (O(n²)).

Problem ladder

Deep dive

Hash maps & sets

A hash map turns a key into an array index with a hash function, so it can jump straight to the data instead of searching for it.

How it works

1. A hash function turns the key (a word, a number, a tuple) into a big integer.
2. hash % number_of_buckets picks a bucket, which is just an array slot.
3. Two keys can land in the same bucket. That's a collision. The bucket keeps a small list (chaining), or the table probes the next free slot (open addressing, which Python's dict uses).
4. When the table gets too full, it doubles its size and re-inserts everything. That keeps buckets short, so operations stay O(1) on average.

Python tools

from collections import Counter, defaultdict
seen = set();  seen.add(x);  x in seen          # membership
d = {};  d[k] = d.get(k, 0) + 1                 # count without KeyError
cnt = Counter(nums);  cnt.most_common(2)        # [(value, count), ...]
groups = defaultdict(list);  groups[key].append(x)   # missing key auto-creates []

Pattern 1 · Count frequencies

def isAnagram(s, t):
    return Counter(s) == Counter(t)

Pattern 2 · Look up the complement

Two Sum. For each x, check whether target − x was already stored. The animation is in the crash course.

Pattern 3 · Group by a canonical key

Give every item a "signature" that's equal for items that belong together, then group by it.

def groupAnagrams(strs):
    groups = defaultdict(list)
    for w in strs:
        groups[''.join(sorted(w))].append(w)   # "eat", "tea", "ate" -> key "aet"
    return list(groups.values())

Pattern 4 · Prefix sum + hash map

Count subarrays that sum to k, even with negative numbers. If pre[j] − pre[i] = k, then subarray i..j−1 sums to k. So at each position, ask how many earlier prefixes equal current − k.

def subarraySum(nums, k):
    count, cur = 0, 0
    seen = {0: 1}                   # prefix sum -> how many times seen
    for x in nums:
        cur += x
        count += seen.get(cur - k, 0)
        seen[cur] = seen.get(cur, 0) + 1
    return count

Pattern 5 · Smart starting points

Longest consecutive sequence in O(n): put all numbers in a set, and only start counting from x when x − 1 is not in the set. Each sequence is then walked once.

def longestConsecutive(nums):
    s, best = set(nums), 0
    for x in s:
        if x - 1 not in s:              # x starts a sequence
            y = x
            while y + 1 in s: y += 1
            best = max(best, y - x + 1)
    return best

Common mistakes

• KeyError from d[k] += 1 on a new key. Use .get(k, 0), defaultdict(int) or Counter.
• Changing a dict's size while looping over it. Loop over list(d) instead.
• Forgetting that sets and dicts don't keep a sorted order.
• Worst case is O(n) per operation if everything collides. This is rare in practice and ignored in interviews.

Problem ladder

Deep dive

Two pointers

Use two indexes so that every step safely rules out part of the input. Most nested-loop solutions on sorted data become a single pass.

Why it's correct (the part most tutorials skip)

In sorted Two Sum, if a[l] + a[r] is too small, then a[l] plus any remaining number is also too small, because a[r] is the biggest one left. So a[l] can never be part of the answer, and moving l right loses nothing. The same argument works in reverse for r. Every move throws away a whole row of pairs, which is why n steps are enough to cover all n² pairs.

Shape 1 · Opposite ends, moving inward

For sorted pair sums, palindromes, reversing in place and "container" problems.

def maxArea(height):                  # Container With Most Water
    l, r, best = 0, len(height) - 1, 0
    while l < r:
        best = max(best, (r - l) * min(height[l], height[r]))
        if height[l] < height[r]: l += 1   # the shorter wall limits the area, so move it
        else: r -= 1
    return best

Shape 2 · Same direction (reader and writer)

def removeDuplicates(nums):           # sorted input; keep one of each
    w = 1
    for r in range(1, len(nums)):
        if nums[r] != nums[w - 1]:
            nums[w] = nums[r]; w += 1
    return w

Shape 3 · One pointer in each of two arrays

def merge(a, b):                      # merge two sorted lists
    i = j = 0; out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]: out.append(a[i]); i += 1
        else: out.append(b[j]); j += 1
    return out + a[i:] + b[j:]

Shape 4 · Fast and slow

One pointer moves twice as fast. Use it to find the middle of a linked list or to detect a cycle. It's covered in Linked lists.

Worked example · 3Sum

Find all unique triplets that sum to 0. Sort first. Fix the first number, then run sorted Two Sum on the rest. Skip equal values so you don't repeat triplets. Total: O(n²), which beats O(n³).

def threeSum(nums):
    nums.sort(); res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]: continue    # skip duplicate first number
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0: l += 1
            elif s > 0: r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                l += 1
                while l < r and nums[l] == nums[l - 1]: l += 1   # skip duplicate second number
    return res

Common mistakes

• Using converging pointers on unsorted data. The "safe to discard" argument needs sorted order.
• l < r vs l <= r. Ask whether one item can pair with itself.
• A branch that doesn't move either pointer, causing an infinite loop.
• Duplicate answers in 3Sum or 4Sum because equal values weren't skipped.

Problem ladder

Deep dive

Sliding window

Keep a running summary of a contiguous range. Update it when an item enters on the right or leaves on the left, instead of recomputing the whole range.

Fixed-size window (size k)

def findMaxAverage(nums, k):
    s = sum(nums[:k]); best = s
    for r in range(k, len(nums)):
        s += nums[r] - nums[r - k]      # one item enters, one leaves
        best = max(best, s)
    return best / k

Variable-size window: the universal template

l = 0
for r in range(len(a)):
    add(a[r])                   # 1. expand: include a[r]
    while window_is_invalid():  # 2. shrink until valid again
        remove(a[l]); l += 1
    best = max(best, r - l + 1) # 3. record (for "longest")

def minSubArrayLen(target, nums):       # shortest subarray with sum >= target
    l, s, best = 0, 0, float('inf')
    for r, x in enumerate(nums):
        s += x
        while s >= target:              # valid -> record, then try smaller
            best = min(best, r - l + 1)
            s -= nums[l]; l += 1
    return 0 if best == float('inf') else best

Windows that track counts

Longest Repeating Character Replacement: a window is valid when length − count of its most common letter ≤ k, meaning the other letters fit within k replacements.

def characterReplacement(s, k):
    cnt, l, maxf, best = {}, 0, 0, 0
    for r, ch in enumerate(s):
        cnt[ch] = cnt.get(ch, 0) + 1
        maxf = max(maxf, cnt[ch])
        while (r - l + 1) - maxf > k:
            cnt[s[l]] -= 1; l += 1
        best = max(best, r - l + 1)
    return best

Trick · "exactly K" = atMost(K) − atMost(K − 1)

Windows with exactly K distinct values are hard to slide directly, because adding an item can make the window invalid in either direction. Counting windows with at most K is easy. Subtract two of those counts.

When sliding window fails

• The rule must be monotonic: shrinking a valid window keeps it valid (or growing an invalid one keeps it invalid).
• With negative numbers, a sum can drop as the window grows, so "sum ≥ target" isn't monotonic. Use prefix sums + hash map instead.
• For the max or min inside each window, use a monotonic deque (see Stacks & queues).

Problem ladder

Deep dive

Stacks, queues & monotonic stacks

A stack gives back the most recent item first. A queue gives back the oldest item first. Choosing the right one sets the order your algorithm processes things in.

The operations

• Recursion is a stack. Every function call is pushed on the call stack and popped when it returns. Any recursive DFS can be rewritten with an explicit stack.
• BFS is a queue. Nodes are processed in the order they were discovered.
• Stacks are good at anything nested or "most recent unmatched": brackets, undo, HTML tags, expression evaluation.

Monotonic stack: "next greater element" in O(n)

Keep the stack in decreasing order. When a bigger value arrives, it is the answer for every smaller value it pops. Each index is pushed once and popped once, so the total is O(n) even though there's a loop inside a loop.

def dailyTemperatures(t):              # days until a warmer day
    ans, st = [0] * len(t), []         # st holds indexes, temps decreasing
    for i, x in enumerate(t):
        while st and t[st[-1]] < x:
            j = st.pop()
            ans[j] = i - j             # found the next warmer day for j
        st.append(i)
    return ans

Variations: "next smaller" uses an increasing stack. "Previous greater" reads the top before pushing. "Circular array" loops through the array twice.

Evaluating expressions

def evalRPN(tokens):                   # ["2","1","+","3","*"] -> 9
    st = []
    for t in tokens:
        if t in "+-*/":
            b, a = st.pop(), st.pop()
            st.append(a + b if t == '+' else a - b if t == '-' else a * b if t == '*' else int(a / b))
        else:
            st.append(int(t))
    return st[0]

Monotonic deque: max of every window

from collections import deque
def maxSlidingWindow(nums, k):
    dq, out = deque(), []              # indexes, values decreasing front to back
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] < x: dq.pop()  # smaller values can never be the max again
        dq.append(i)
        if dq[0] == i - k: dq.popleft()           # front fell out of the window
        if i >= k - 1: out.append(nums[dq[0]])
    return out

Common mistakes

• Calling pop() or st[-1] on an empty stack. Always check if st first.
• Using list.pop(0) as a queue: O(n) per call.
• Storing values on a monotonic stack when you need distances. Store indexes instead.

Problem ladder

Deep dive

Binary search

Binary search works on anything that splits into "no, no, no, yes, yes, yes". Each check halves the region that can still hold the first yes.

The real idea: find the boundary

A sorted array is one example. The general version: you have a condition ok(x) that is false for small x and true for large x. Binary search finds the first true in O(log range) checks. That handles "first position ≥ target", "first bad version", "smallest speed that works" and many more.

Template A · exact match

lo, hi = 0, len(a) - 1
while lo <= hi:                     # the range [lo, hi] is still unchecked
    mid = (lo + hi) // 2
    if a[mid] == x: return mid
    if a[mid] < x: lo = mid + 1
    else: hi = mid - 1
return -1

Template B · first true (lower bound) — learn this one well

def first_true(lo, hi, ok):         # answer is in [lo, hi]; ok is F..F T..T
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid): hi = mid        # mid might be the answer, so keep it
        else: lo = mid + 1          # mid is definitely not the answer
    return lo

# first index with a[i] >= x  (same as bisect.bisect_left(a, x))
first_true(0, len(a), lambda i: i == len(a) or a[i] >= x)

Binary search on the answer

When the question is "what is the minimum X such that…", and checking one X is easy, binary search over the possible values of X.

def minEatingSpeed(piles, h):
    def ok(k):                       # can she finish at speed k?
        return sum((p + k - 1) // k for p in piles) <= h   # ceil(p / k) hours per pile
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid): hi = mid
        else: lo = mid + 1
    return lo

Rotated sorted array

[4,5,6,7,0,1,2]: split at any mid, and at least one half is still sorted. Check whether the target lies inside the sorted half's range. If so, search there; otherwise, search the other half.

def search(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x: return mid
        if a[lo] <= a[mid]:                       # left half is sorted
            if a[lo] <= x < a[mid]: hi = mid - 1
            else: lo = mid + 1
        else:                                     # right half is sorted
            if a[mid] < x <= a[hi]: lo = mid + 1
            else: hi = mid - 1
    return -1

Common mistakes

• Mixing the two templates (using lo <= hi with hi = mid, for example).
• A search range that doesn't include the answer. For lower bound, hi = len(a), not len(a) − 1.
• Not checking that the condition really is monotonic.
• Not using bisect when it already does what you need.

Problem ladder

Deep dive

Linked lists

Nodes scattered in memory, each pointing to the next. Inserting is cheap once you're at the right spot. Getting there means walking.

Array vs linked list

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next

Technique 1 · Dummy head

When the head itself might change (it gets deleted, or you're building a new list), start from a fake node in front of it. Then the head needs no special case. Return dummy.next.

def mergeTwoLists(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val: tail.next, a = a, a.next
        else: tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

Technique 2 · Fast and slow pointers

def middleNode(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

def hasCycle(head):                  # Floyd's algorithm
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast: return True # inside a loop, fast gains 1 node per step, so it must catch slow
    return False

Technique 3 · A gap of n

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n + 1): fast = fast.next   # fast is now n+1 ahead
    while fast:
        fast, slow = fast.next, slow.next
    slow.next = slow.next.next                # slow stops just before the target
    return dummy.next

Technique 4 · Combine the basics

Many medium problems are 2–3 easy ones glued together. Reorder List = find the middle, reverse the second half, weave the halves together. Palindrome Linked List = find the middle, reverse the second half, compare. LRU Cache = hash map (key → node) + doubly linked list (order of use).

Common mistakes

• Overwriting node.next before saving it, which loses the rest of the list.
• fast.next.next when fast.next is None. Check fast and fast.next.
• Returning dummy instead of dummy.next.
• Not drawing it. Two minutes of boxes and arrows on paper prevents most bugs here.

Problem ladder

Deep dive

Trees & binary search trees

A tree is a recursive structure: each node is a smaller tree's root. So most tree solutions are "solve it for the children, then combine".

Vocabulary

• Root = top node. Leaf = no children. Depth of a node = edges from the root. Height of a tree = longest root-to-leaf path.
• Balanced: height is about log n, so operations are fast. Skewed: basically a linked list, height n.
• Complete: every level full except possibly the last, filled left to right. Heaps are stored this way.
• BST: every value in the left subtree < node < every value in the right subtree. That's the whole subtree, not just the direct children.

The three depth-first orders

def dfs(node):
    if not node: return
    # pre-order: work here (top-down, e.g. copy/serialize a tree)
    dfs(node.left)
    # in-order: work here (on a BST this visits values in sorted order)
    dfs(node.right)
    # post-order: work here (children are done, e.g. heights, deleting)

Two recursion styles

Bottom-up (return information up). Each call returns something about its subtree, and the parent combines the results. Heights, sizes, "is it balanced", diameter.

def diameterOfBinaryTree(root):
    best = 0
    def height(n):
        nonlocal best
        if not n: return 0
        l, r = height(n.left), height(n.right)
        best = max(best, l + r)      # longest path that bends at n
        return 1 + max(l, r)         # tell the parent my height
    height(root)
    return best

Top-down (pass information down). Each call receives what it needs from its ancestors as parameters. Path sums, allowed value ranges, current depth.

def isValidBST(root):
    def ok(n, low, high):            # every value here must be in (low, high)
        if not n: return True
        if not (low < n.val < high): return False
        return ok(n.left, low, n.val) and ok(n.right, n.val, high)
    return ok(root, float('-inf'), float('inf'))

BST operations

• Search, insert, delete: go left if smaller, right if bigger. O(h), which is O(log n) if balanced and O(n) if skewed.
• In-order traversal gives sorted order, so the "kth smallest" is the kth node visited in-order.
• Lowest common ancestor in a BST: walk down from the root. The first node whose value lies between p and q is the answer.

def kthSmallest(root, k):            # iterative in-order with a stack
    st, n = [], root
    while st or n:
        while n: st.append(n); n = n.left   # go as far left as possible
        n = st.pop(); k -= 1
        if k == 0: return n.val
        n = n.right

Common mistakes

• Validating a BST by comparing only parent and children. The range must hold for the whole subtree.
• Forgetting the if not node base case.
• Mixing up depth (counted from the top) and height (counted from the bottom).
• Recursion depth on a skewed tree with 10⁵ nodes. Use an iterative version or raise the limit.

Problem ladder

Deep dive

Heaps (priority queues)

A heap always hands you the smallest (or largest) item in O(log n), without keeping everything fully sorted.

How it works

• A complete binary tree stored in a plain array. For index i: parent = (i − 1) // 2, children = 2i + 1 and 2i + 2.
• Min-heap rule: every parent ≤ its children, so the minimum is always at index 0.
• Push: add at the end, then sift up (swap with the parent while smaller). Pop: take index 0, move the last item to the top, then sift down (swap with the smaller child). Both are O(log n).

Pattern 1 · Top-k with a heap of size k

To get the k largest, keep a min-heap of size k. Its top is the smallest of your current top k, so anything bigger replaces it. That's O(n log k), better than sorting when k is small.

import heapq
def findKthLargest(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k: heapq.heappop(h)   # drop the smallest
    return h[0]                            # smallest of the k largest

Pattern 2 · Merge k sorted lists

def mergeKLists(lists):
    h = [(node.val, i, node) for i, node in enumerate(lists) if node]
    heapq.heapify(h)
    dummy = tail = ListNode()
    while h:
        _, i, node = heapq.heappop(h)      # i breaks ties so nodes are never compared
        tail.next = tail = node
        if node.next: heapq.heappush(h, (node.next.val, i, node.next))
    return dummy.next

Pattern 3 · Two heaps for a running median

Keep the smaller half in a max-heap and the larger half in a min-heap, with sizes differing by at most 1. The median is at the top of one or both heaps.

Pattern 4 · Always take the best next item

Dijkstra's shortest path, task scheduling, and repeatedly combining the two smallest items all pop the current best choice from a heap.

Problem ladder

Deep dive

Graphs

Graphs model anything with connections: maps, networks, course prerequisites, grids, word puzzles. Many problems are just BFS or DFS once you see the graph in them.

Vocabulary

• Vertices (nodes) and edges. V = number of nodes, E = number of edges.
• Directed (one-way, like prerequisites) vs undirected (two-way, like friendships). Weighted edges have costs.
• Connected component: a group of nodes that can all reach each other. Cycle: a path that returns to its start. DAG: a directed graph with no cycles.

Representations

from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)        # leave this out for a directed graph

BFS: shortest path when every edge costs 1

from collections import deque
def bfs(start, target):
    dist = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        if u == target: return dist[u]
        for v in graph[u]:
            if v not in dist:           # mark when ADDING, not when popping
                dist[v] = dist[u] + 1
                q.append(v)
    return -1

Multi-source BFS: put all starting points in the queue at step 0 (for example, all rotten oranges at once). The levels then spread from every source at the same time.

DFS: explore everything reachable

def dfs(u, seen):
    seen.add(u)
    for v in graph[u]:
        if v not in seen:
            dfs(v, seen)

# count connected components
seen, comps = set(), 0
for node in range(n):
    if node not in seen:
        dfs(node, seen); comps += 1

Topological sort: order tasks with prerequisites

Kahn's algorithm: repeatedly take a node with no remaining prerequisites (in-degree 0), output it, and remove its outgoing edges. If some nodes are never output, the graph has a cycle, so no valid order exists. That's exactly the Course Schedule problem.

def topoSort(n, edges):                  # edge (a, b) means a must come before b
    graph, indeg = defaultdict(list), [0] * n
    for a, b in edges:
        graph[a].append(b); indeg[b] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft(); order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return order if len(order) == n else []   # [] means there's a cycle

Union-Find (disjoint set): "are these connected?"

Keeps groups of nodes and merges them quickly. With path compression, each operation is almost O(1). Use it for counting components, finding the edge that creates a cycle, or connectivity that changes as edges are added.

parent = list(range(n))
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]    # path compression: point closer to the root
        x = parent[x]
    return x
def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb: return False            # already connected, so this edge makes a cycle
    parent[ra] = rb
    return True

Dijkstra: shortest path with non-negative weights

import heapq
def dijkstra(src):                       # graph[u] = [(v, w), ...]
    dist = {src: 0}
    h = [(0, src)]
    while h:
        d, u = heapq.heappop(h)
        if d > dist.get(u, float('inf')): continue   # stale heap entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(h, (nd, v))
    return dist                          # O((V + E) log V)

Which algorithm?

Common mistakes

• No visited set, which loops forever on cycles.
• In BFS, marking nodes visited when popped instead of when added. Nodes get queued many times.
• Forgetting nodes with no edges (they still count as components).
• Building only one direction of an undirected edge.

Problem ladder

Deep dive

Backtracking

Backtracking is DFS over a tree of decisions. Make a choice, explore everything that follows from it, undo it, then try the next choice.

The decision tree

For subsets, each level decides about one number: take it or skip it. The leaves are all 2ⁿ answers. Backtracking walks this tree depth-first and keeps only the current path in memory.

The universal template

def backtrack(path, choices):
    if is_complete(path):
        res.append(path[:])          # COPY: path keeps changing after this
        return
    for c in choices:
        if not valid(c, path): continue   # pruning: skip dead branches early
        path.append(c)               # choose
        backtrack(path, next_choices)  # explore
        path.pop()                   # un-choose

Subsets vs combinations vs permutations

def permute(nums):
    res, path, used = [], [], [False] * len(nums)
    def bt():
        if len(path) == len(nums): res.append(path[:]); return
        for i, x in enumerate(nums):
            if used[i]: continue
            used[i] = True; path.append(x)
            bt()
            used[i] = False; path.pop()
    bt(); return res

def combinationSum(cands, target):
    res = []
    def bt(start, path, total):
        if total == target: res.append(path[:]); return
        for j in range(start, len(cands)):
            if total + cands[j] > target: continue   # prune
            path.append(cands[j])
            bt(j, path, total + cands[j])            # j, not j+1: reuse allowed
            path.pop()
    bt(0, [], 0); return res

Handling duplicate inputs

With input like [1, 2, 2], sort first. Then at each level skip a value equal to the previous one: if j > start and nums[j] == nums[j-1]: continue. Equal values are then only picked in order, so the same subset can't be built twice.

Backtracking on a grid (Word Search)

def exist(board, word):
    R, C = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word): return True
        if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[i]: return False
        tmp, board[r][c] = board[r][c], '#'          # mark as used (choose)
        found = any(dfs(r+dr, c+dc, i+1) for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)))
        board[r][c] = tmp                            # restore (un-choose)
        return found
    return any(dfs(r, c, 0) for r in range(R) for c in range(C))

Common mistakes

• res.append(path) instead of path[:]. Every result ends up as the same (empty) list.
• Forgetting to undo (pop, unmark, restore).
• No pruning, so the search explores branches that can't work.

Problem ladder

Deep dive

Dynamic programming

DP solves a problem from answers to smaller versions of the same problem, and stores each answer so it's computed only once.

When is it DP?

• Overlapping subproblems: plain recursion solves the same subproblem again and again (see the fib(4) tree in Complexity).
• Optimal substructure: the best answer is built from best answers to smaller parts.
• Wording: "number of ways", "minimum / maximum", "is it possible", "longest", over sequences, grids or amounts.

The 5-step recipe

1. State: define dp[i] (or dp[i][j]) in one English sentence. This is the hardest and most important step.
2. Transition: how does dp[i] follow from smaller states? Think about the last choice made.
3. Base cases: the smallest states you know directly.
4. Order: fill states so everything a state needs is already computed.
5. Answer: which cell holds it (dp[n], max(dp), the bottom-right…).

Top-down vs bottom-up

from functools import cache
def rob(nums):                       # House Robber, top-down
    @cache
    def best(i):                     # max money from houses i..end
        if i >= len(nums): return 0
        return max(best(i + 1), nums[i] + best(i + 2))   # skip it, or rob it
    return best(0)

def rob(nums):                       # bottom-up with O(1) space
    prev2 = prev1 = 0                # best up to i-2, best up to i-1
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

1D DP · Coin Change

def coinChange(coins, amount):
    dp = [0] + [float('inf')] * amount      # dp[a] = fewest coins to make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)   # last coin used was c
    return dp[amount] if dp[amount] != float('inf') else -1

2D DP · Longest Common Subsequence

dp[i][j] = LCS of the first i letters of one string and the first j letters of the other. If the letters match, extend the diagonal. Otherwise, take the better of dropping a letter from either string.

def longestCommonSubsequence(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1
            else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[-1][-1]

0/1 knapsack · Partition Equal Subset Sum

Each item can be used at most once. Loop the capacity backwards so an item isn't counted twice in the same pass.

def canPartition(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    dp = [True] + [False] * target           # dp[s] = can some items sum to s?
    for x in nums:
        for s in range(target, x - 1, -1):   # backwards!
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

Common state shapes

Common mistakes

• A vague state. If you can't say what dp[i] means in one sentence, stop and define it.
• Wrong base case (dp[0] for "empty" is often 1 for counting problems and 0 for sums).
• Filling in the wrong order, or looping forwards in 0/1 knapsack.
• Returning infinity instead of the −1 the problem asks for.

Problem ladder

Deep dive

Sorting, greedy & intervals

Sorting is the most common first step in a solution. Once data is sorted, greedy choices and interval sweeps often become obvious.

Sorting algorithms you should recognize

def mergeSort(a):
    if len(a) <= 1: return a
    mid = len(a) // 2
    L, R = mergeSort(a[:mid]), mergeSort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]: out.append(L[i]); i += 1
        else: out.append(R[j]); j += 1
    return out + L[i:] + R[j:]

Custom sort keys

people.sort(key=lambda p: (-p.age, p.name))   # age descending, then name ascending
intervals.sort(key=lambda x: x[0])           # by start
words.sort(key=len)                          # by length

from functools import cmp_to_key             # when the order depends on pairs
nums.sort(key=cmp_to_key(lambda a, b: -1 if a + b > b + a else 1))   # Largest Number (on strings)

Quickselect finds the kth smallest in average O(n) by partitioning like quicksort but recursing into only one side.

Greedy

A greedy algorithm makes the choice that looks best right now and never revisits it. It's fast and short, but correct only when you can argue that a locally best choice never blocks the overall best answer. If you can't argue it, try DP.

def canJump(nums):                   # Jump Game
    far = 0                          # farthest index reachable so far
    for i, x in enumerate(nums):
        if i > far: return False     # stuck before reaching i
        far = max(far, i + x)
    return True

Intervals

• Two intervals [a, b] and [c, d] overlap when a <= d and c <= b.
• Merge overlapping intervals: sort by start, then extend the last merged interval or start a new one.
• Keep as many non-overlapping intervals as possible: sort by end and greedily keep the one that finishes first. It leaves the most room for the rest.
• Most overlapping at once (meeting rooms): sort start and end times separately and sweep, or use a min-heap of end times.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    out = [intervals[0]]
    for s, e in intervals[1:]:
        if s <= out[-1][1]: out[-1][1] = max(out[-1][1], e)   # overlap, so extend
        else: out.append([s, e])
    return out

Problem ladder

Deep dive

Tries & bit manipulation

Two smaller topics that show up regularly: a tree for prefix lookups, and tricks with the binary form of numbers.

Trie (prefix tree)

Each edge is a letter. Words that share a prefix share the same path. A flag marks nodes where a word ends. Insert and search cost O(length of word), no matter how many words are stored.

class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})   # walk, creating children as needed
        node['$'] = True                     # end-of-word marker
    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node: return None
            node = node[ch]
        return node
    def search(self, word):
        node = self._walk(word); return bool(node) and '$' in node
    def startsWith(self, prefix):
        return self._walk(prefix) is not None

Use a trie for autocomplete, "does any word start with…", and searching many words in a grid at once (Word Search II).

Bit manipulation cheat sheet

def singleNumber(nums):              # every number appears twice except one
    x = 0
    for n in nums: x ^= n            # pairs cancel out
    return x

Problem ladder

Deep dive

Interview rounds playbook

A typical loop has 4–6 rounds, and each one looks for different evidence. Knowing what each round wants tells you what to practise.

The rounds

Behavioral answers with STAR

• Situation: one or two sentences of context.
• Task: what you were responsible for.
• Action: what you did, step by step. This is most of the answer. Say "I", not "we".
• Result: a measurable outcome, plus what you learned.

Q: "Tell me about a time you disagreed with a teammate."

S: Our team was choosing between two queue systems for a new notifications service.
T: I owned the design doc, and a senior engineer strongly preferred Kafka.
A: I wrote down our actual requirements (2k msgs/s, no replay needed, small team),
   built a one-day prototype with each option, and compared the operational cost.
   I shared the data in a 30-minute review instead of arguing in comments.
R: We chose SQS. It shipped 3 weeks earlier with no on-call burden, and the
   senior engineer later reused the comparison template for another decision.
   Lesson: turn opinions into criteria and data early.

Your story bank

Prepare 6–8 stories. Each can be reused for several questions.

Object-oriented design round: the approach

1. Clarify scope: which features, which actors, which constraints? ("Multiple floors? Spot sizes? Payment?")
2. Find the nouns (candidate classes) and verbs (methods) in the requirements.
3. Assign responsibilities so each class has one reason to change. Draw the relationships (has-a, is-a).
4. Write the key interfaces and classes in code, not every getter.
5. Walk through a use case end to end (a car enters, parks, pays, leaves).
6. Discuss extension and edge cases: new vehicle types (open/closed), concurrency on spot allocation, a full lot.

from enum import Enum
from abc import ABC, abstractmethod

class Size(Enum): SMALL = 1; MEDIUM = 2; LARGE = 3

class Vehicle(ABC):
    size: Size
class Motorcycle(Vehicle): size = Size.SMALL
class Car(Vehicle):        size = Size.MEDIUM
class Truck(Vehicle):      size = Size.LARGE

class Spot:
    def __init__(self, spot_id, size): self.id, self.size, self.vehicle = spot_id, size, None
    def fits(self, v): return self.vehicle is None and v.size.value <= self.size.value

class SpotStrategy(ABC):                      # Strategy pattern: swap the allocation rule
    @abstractmethod
    def choose(self, spots, vehicle): ...
class NearestFirst(SpotStrategy):
    def choose(self, spots, vehicle):
        return next((s for s in spots if s.fits(vehicle)), None)

class ParkingLot:
    def __init__(self, spots, strategy: SpotStrategy, pricing):
        self.spots, self.strategy, self.pricing = spots, strategy, pricing
        self.lock = threading.Lock()          # two cars must not get the same spot
    def park(self, vehicle):
        with self.lock:
            spot = self.strategy.choose(self.spots, vehicle)
            if spot is None: raise LotFull()
            spot.vehicle = vehicle
        return Ticket(spot, vehicle, entered=time.time())
    def leave(self, ticket):
        ticket.spot.vehicle = None
        return self.pricing.price(ticket)     # pricing is injected too

Other common OOD questions: elevator system, library management, vending machine, chess, LRU cache, rate limiter class, file system, splitwise.

Questions to ask your interviewers

• "What does a successful first 6 months look like in this role?"
• "How do code review and deployment work on your team?"
• "What's the hardest technical problem the team is working on right now?"
• "How are on-call and incidents handled?"

Résumé tips that lead to better interviews

• Use the format: action verb + what you built + measurable impact. "Cut checkout p95 latency from 900 to 250 ms by adding a Redis cache and fixing an N+1 query."
• Everything on your résumé is fair game. Be ready to go two levels deep on each bullet.

Deep dive

How code runs

Knowing what the machine does with your code explains most performance surprises, most "why did my variable change?" bugs, and most crash messages.

From source code to execution

import dis
dis.dis(lambda x: x + 1)       # show the bytecode CPython actually runs
#   LOAD_FAST   x
#   LOAD_CONST  1
#   BINARY_OP   +
#   RETURN_VALUE

Stack vs heap

Python names are references

A variable in Python is a name tag attached to an object, not a box that holds a value. Two names can point at the same object, and changing a mutable object through one name is visible through the other.

a = [1, 2]
b = a              # same list, two names
b.append(3)
print(a)           # [1, 2, 3]

c = a[:]           # shallow copy: a new outer list
import copy
d = copy.deepcopy(nested)   # copies the inner lists too

def add_item(x, items=[]):  # BUG: the default list is created once and shared
    items.append(x)
    return items
def add_item(x, items=None):  # fix
    items = [] if items is None else items
    items.append(x)
    return items

Mutable (can change in place): list, dict, set, most objects. Immutable: int, float, str, tuple, frozenset. Only immutable objects can be dict keys.

Garbage collection

• Python counts references to each object and frees it when the count hits zero. A separate cycle collector handles objects that point at each other.
• Java, JavaScript, Go, C# use tracing collectors: they periodically find everything still reachable and free the rest.
• C/C++: you free memory yourself. Rust: the compiler proves when memory can be freed (ownership).

Processes, threads and coroutines

Latency numbers every engineer should know

Approximate times on log scale. If an L1 cache read took 1 second, reading RAM would take about 2 minutes, an SSD read about a day, and a round trip across the world about 5 years.

Numbers are not exact

0.1 + 0.2 == 0.3          # False: floats are binary approximations
abs((0.1 + 0.2) - 0.3) < 1e-9   # compare floats with a tolerance
from decimal import Decimal     # use Decimal (or integer cents) for money
2 ** 100                  # Python ints never overflow; Java/C ints wrap around at 2^31 or 2^63

Text is stored as numbers too. Unicode gives every character a number, and UTF-8 stores it in 1–4 bytes. len("é") is 1 character but len("é".encode()) is 2 bytes.

Try it

1. Paste the aliasing example into Python Tutor and watch the arrows.
2. Write a recursive function with no base case. Read the RecursionError traceback from bottom to top.
3. Time x in big_list vs x in big_set with timeit for a million items.
4. Run dis.dis on one of your LeetCode solutions.

Deep dive

Git in depth

Git becomes easy once you see it as a graph of snapshots with movable labels on it. Every command either adds nodes to the graph or moves labels.

The mental model

• Commit = a full snapshot of the project + author + message + a pointer to its parent(s). Its ID is a hash of all that, such as a1b2c3d.
• Branch = a label pointing at one commit. Committing moves the current branch's label forward.
• HEAD = "you are here", usually pointing at a branch.
• Remote (origin) = another copy of the repo, such as on GitHub. origin/main is your last-known position of its main branch.

Merge vs rebase

Both bring the work of two branches together. Merge keeps the true history and adds a merge commit. Rebase replays your commits on top of the latest main, giving a straight line of history, but it creates new commits (new IDs).

Daily workflow

git switch main && git pull          # start from the latest main
git switch -c fix/cart-total         # one branch per change
# ...edit, test...
git add -p                           # review and stage changes piece by piece
git commit -m "Fix rounding in cart total"
git push -u origin fix/cart-total    # then open a pull request on GitHub
git switch main && git pull && git branch -d fix/cart-total   # after merge

Merge conflicts

A conflict happens when both branches changed the same lines. Git stops and marks the spot. Edit the file to the version you want, delete the markers, then git add and git commit.

<<<<<<< HEAD
greeting = "Hello"
=======
greeting = "Hi there"
>>>>>>> feature/greeting

Undoing things

Good commit messages

Fix rounding error in cart total          # imperative, ≤ 50 chars

Totals were summed as floats, so 0.1 + 0.2 showed 0.30000000000000004.
Store prices as integer cents and format only for display.   # body: WHY

• One logical change per commit, so reverting it reverts exactly one thing.
• Keep a .gitignore for build output, .venv/, node_modules/, .env. Never commit secrets. If you do, rotate them, because history keeps them.
• Trunk-based (short branches, merged daily) is the common modern workflow. GitFlow (long-lived develop and release branches) suits scheduled releases.

Try it

1. Finish the "Introduction" and "Ramping Up" levels of Learn Git Branching.
2. Create a repo, make a conflict on purpose between two branches, and resolve it.
3. Commit 10 small changes with one bug hidden in the middle, then find it with git bisect.

Deep dive

Clean code & refactoring

Clean code is code that's cheap to change. Every rule below is a way to reduce the time the next reader needs to understand it safely.

Naming

Functions

• Do one thing at one level of detail. If you need "and" to describe it, split it.
• Keep them short enough to see on one screen. Extract well-named helpers.
• Few parameters. Group related ones into an object, and avoid boolean "mode" flags: render(page, True) → render_preview(page).
• Either change something or return something, not both in surprising ways (command-query separation).

Guard clauses remove nesting: handle the special cases first and return early.

# before: the main logic is buried 3 levels deep
def ship(order):
    if order:
        if order.paid:
            if order.items:
                return create_shipment(order)
    return None

# after: exits first, main path at the left margin
def ship(order):
    if not order or not order.paid or not order.items:
        return None
    return create_shipment(order)

Comments

• Explain why (a business rule, a workaround, a non-obvious decision). If a comment explains what, rename things until it isn't needed.
• Docstrings for public functions and modules: what it does, the inputs, the output, the errors it raises.
• Delete commented-out code. Git remembers it.

Principles

• DRY: one source of truth for each piece of knowledge. Rule of three: duplicate once, and abstract on the third copy, so you don't abstract too early.
• KISS: the simplest solution that works. Clever code costs more to read than it saves.
• YAGNI: don't build for imagined future needs.
• Separation of concerns: keep I/O (files, network, DB) apart from logic. Pure logic is easy to test.
• Least surprise: a function should do what its name suggests and nothing more.

Code smells and their fixes

Errors

try:
    charge(card)
except Exception:
    pass                          # BAD: hides every bug, including typos

try:
    charge(card)
except CardDeclined as e:         # GOOD: catch only what you can handle
    log.warning("declined: %s", e)
    notify_user(e)
# Let unexpected errors crash loudly; fail fast, close to the cause.

Let tools do the boring part

• Formatter (ruff format or black, prettier): ends all style debates.
• Linter (ruff, eslint): catches unused variables, shadowing, likely bugs.
• Type hints + checker (mypy, pyright, TypeScript): catch wrong types before running.

Try it

1. Take one of your old LeetCode solutions. Rename every variable and extract helpers until it reads like English.
2. Run ruff check . on a project and fix every warning.
3. Read a popular open-source file (for example, Python's requests) and notice its naming.

Deep dive

Object-oriented design & SOLID

OOP bundles data with the code that's allowed to change it. Good OO design keeps each piece small, focused and replaceable.

Classes and objects

from dataclasses import dataclass

@dataclass
class Account:
    owner: str
    balance: float = 0.0

    def deposit(self, amount: float) -> None:
        if amount <= 0:
            raise ValueError("amount must be positive")
        self.balance += amount

acc = Account("Mona")       # an object (instance) of the class
acc.deposit(50)             # method call; self is acc

The four pillars, with code

# Encapsulation: control access to internal state
class Thermostat:
    def __init__(self): self._celsius = 20      # _ means "internal"
    @property
    def celsius(self): return self._celsius
    @celsius.setter
    def celsius(self, v):
        if not 5 <= v <= 30: raise ValueError("out of range")
        self._celsius = v

# Abstraction: callers know WHAT, not HOW
class Notifier(ABC):
    @abstractmethod
    def send(self, to: str, msg: str) -> None: ...

# Inheritance: reuse and extend a parent
class EmailNotifier(Notifier):
    def send(self, to, msg): smtp_send(to, msg)

class SmsNotifier(Notifier):
    def send(self, to, msg): sms_api.post(to, msg)

# Polymorphism: same call, right behaviour per type
for n in [EmailNotifier(), SmsNotifier()]:
    n.send("user", "Your order shipped")

Composition over inheritance

Inheritance locks in an "is-a" tree early. When behaviours mix (a duck that flies, a robot duck that doesn't, a rubber duck that squeaks), the tree explodes. Composition gives an object parts it can swap.

class Duck:
    def __init__(self, flyer, sound):
        self.flyer, self.sound = flyer, sound    # has-a, swappable
    def fly(self): return self.flyer.fly()
    def speak(self): return self.sound.make()

mallard = Duck(WingFlyer(), Quack())
toy     = Duck(NoFly(), Squeak())

SOLID, one by one

# Dependency inversion + injection: easy to test, easy to swap
class OrderService:
    def __init__(self, repo, notifier):     # abstractions passed in
        self.repo, self.notifier = repo, notifier
    def place(self, order):
        self.repo.save(order)
        self.notifier.send(order.email, "Order received")

service = OrderService(PostgresRepo(), EmailNotifier())   # production
test_service = OrderService(InMemoryRepo(), FakeNotifier()) # tests

Coupling and cohesion

• Low coupling: modules know little about each other's internals, so changes don't ripple.
• High cohesion: everything inside a module belongs to the same job.
• Python also supports plain functions and modules. Don't force everything into classes. Use a class when data and behaviour truly belong together.

Try it

1. Model a library: Book, Member, Loan. What does each one own? Which methods go where?
2. Find an if isinstance(...) chain in your code and replace it with polymorphism.
3. Rewrite a function that opens a database itself so the database is passed in, then test it with a fake.

Deep dive

Design patterns & architecture

Patterns are named, proven shapes for common design problems. Their biggest value is vocabulary: "use a strategy here" says a whole design in three words.

The three families

Strategy: swap an algorithm at runtime

def no_discount(total): return total
def student(total):     return total * 0.8
def black_friday(total): return total * 0.5

PRICING = {"none": no_discount, "student": student, "bf": black_friday}

def checkout(total, rule="none"):
    return PRICING[rule](total)        # new rule = new function, no edits here

Factory: one place decides which class to build

def make_notifier(kind: str) -> Notifier:
    if kind == "email": return EmailNotifier()
    if kind == "sms":   return SmsNotifier()
    raise ValueError(f"unknown notifier {kind}")

Observer: notify many listeners when something happens

class EventBus:
    def __init__(self): self.subs = {}
    def on(self, event, fn): self.subs.setdefault(event, []).append(fn)
    def emit(self, event, data):
        for fn in self.subs.get(event, []): fn(data)

bus = EventBus()
bus.on("order_paid", send_receipt)
bus.on("order_paid", update_stock)     # the publisher doesn't know who listens
bus.emit("order_paid", order)

Decorator: wrap behaviour around a function or object

import time, functools
def timed(fn):
    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        start = time.perf_counter()
        result = fn(*args, **kwargs)
        print(f"{fn.__name__} took {time.perf_counter() - start:.3f}s")
        return result
    return wrapper

@timed
def build_report(): ...

Adapter: make an incompatible interface fit

class LegacyPayments:                      # old API you can't change
    def make_payment(self, cents, card_no): ...

class PaymentAdapter:                      # the interface your code expects
    def __init__(self, legacy): self.legacy = legacy
    def charge(self, amount, card):
        return self.legacy.make_payment(int(amount * 100), card.number)

Architecture patterns

Anti-patterns to recognize

• God object: one class that knows and does everything.
• Golden hammer: forcing your favourite tool or pattern onto every problem.
• Premature optimization: making code complex for speed before measuring.
• Pattern overuse: a factory of factories for two classes. Patterns should remove complexity, not add it.

Try it

1. Replace a long if/elif on a "type" string with a dict of strategy functions.
2. Write a @retry(times=3) decorator.
3. Add an event bus to your to-do app: "task_completed" triggers a log line and a counter update.

Deep dive

Testing in depth

Tests turn "I think it works" into "I know it works, and I'll know the moment it stops working".

Kinds of tests

What makes a good test (FIRST)

• Fast enough to run on every save. Independent of other tests and their order. Repeatable: same result every run, with no real time, randomness or network. Self-validating: pass or fail, no reading logs. Timely: written with the code, not months later.
• Test behaviour, not implementation details, so refactoring doesn't break tests.
• One behaviour per test, with a name that reads like a spec: test_expired_coupon_is_rejected.

pytest essentials

import pytest
from shop import apply_coupon, CouponExpired

@pytest.fixture
def cart():                               # reusable setup, fresh for each test
    return {"items": [("book", 20, 2)], "total": 40}

@pytest.mark.parametrize("code, expected", [
    ("SAVE10", 36),
    ("HALF", 20),
    ("", 40),                             # edge case: empty code
])
def test_apply_coupon(cart, code, expected):
    assert apply_coupon(cart, code) == expected

def test_expired_coupon_raises(cart):
    with pytest.raises(CouponExpired):
        apply_coupon(cart, "SUMMER2019")

Test doubles: replacing real dependencies

from unittest.mock import patch

def test_signup_sends_welcome_email():
    with patch("app.email.send") as send:       # replace the real sender
        signup("mona@example.com")
        send.assert_called_once_with("mona@example.com", "Welcome!")

What to test first

• Business rules (prices, permissions, dates). Bugs there cost money.
• Boundaries: 0, 1, many, empty, max, negative, duplicates, unicode, time zones.
• Error paths: invalid input, timeouts, missing records.
• Every bug you fix: write the failing test first, then fix.

Try it

1. Take a LeetCode solution and write pytest tests for its examples plus 5 edge cases.
2. Build a tiny function with TDD: write the test first, watch it fail, then pass.
3. Run pytest --cov and add tests for one uncovered branch.

Deep dive

The web & HTTP in depth

Every web feature you build rides on a few layers of protocols. Knowing them makes debugging network problems ordinary instead of mysterious.

The network layers

TCP vs UDP: TCP guarantees order and delivery (web pages, APIs, files). UDP accepts loss for speed (video calls, games, DNS queries). HTTP/3 runs on QUIC, which is built on UDP.

DNS: names to addresses

1. The browser and OS check their caches.
2. Otherwise they ask a resolver (your ISP, or 1.1.1.1 / 8.8.8.8).
3. The resolver asks a root server → the .com server → the domain's authoritative server, which has the answer.
4. The answer is cached for its TTL (time to live).

HTTPS / TLS

TLS gives three guarantees: encryption (nobody can read it), integrity (nobody can change it), and identity (the server's certificate is signed by a trusted authority, so you really are talking to your bank).

Anatomy of an HTTP exchange

POST /api/v1/orders HTTP/1.1          # method, path, version
Host: shop.example
Content-Type: application/json
Authorization: Bearer eyJhbGciOi...
Cookie: session=8f2a...

{"product_id": 42, "qty": 2}          # body

HTTP/1.1 201 Created                  # status line
Content-Type: application/json
Location: /api/v1/orders/9001
Set-Cookie: cart=; Max-Age=0

{"id": 9001, "status": "pending"}

Status codes you'll actually use

Headers worth knowing

State on a stateless protocol

• Session cookie: the server stores session data and gives the browser a random ID in a cookie. Easy to revoke.
• Token (JWT): the server signs a token holding user info, and the client sends it in a header. The server doesn't need to store anything, but revoking a token early is harder.
• Cookie safety flags: HttpOnly (JavaScript can't read it), Secure (HTTPS only), SameSite (limits cross-site sending).

How the browser shows a page

1. Parse HTML into the DOM tree. Parse CSS into style rules.
2. Run JavaScript, which can change the DOM and fetch more data.
3. Compute layout (sizes and positions), then paint pixels.

Server-side rendering sends ready HTML (fast first view, good for SEO). Client-side rendering sends JS that builds the page (app-like interactions). Modern frameworks such as Next.js mix both.

HTTP versions: 1.1 handles one request at a time per connection. HTTP/2 multiplexes many requests over one connection. HTTP/3 uses QUIC over UDP for faster setup and better behaviour on bad networks.

Try it

1. Open DevTools → Network on any site. Reload and click one request. Find its method, status, headers and timing breakdown.
2. Run curl -v against an API and read every line.
3. Find a request that returned 304 and explain why.

Deep dive

API design

An API is a promise to everyone who uses it. Good APIs are predictable: once you've used one endpoint, you can guess how the others work.

Resource naming

Methods: safe and idempotent

Why idempotency matters: networks fail, and clients retry. Retrying a PUT is harmless. Retrying "POST /payments" could charge twice. Fix it with an idempotency key: the client sends a unique ID with the request, and the server ignores repeats with the same ID.

Consistent responses

// list with pagination
{
  "data": [{"id": 1, "title": "Learn Git"}, {"id": 2, "title": "Write tests"}],
  "next_cursor": "eyJpZCI6Mn0",
  "has_more": true
}

// errors: same shape everywhere
{
  "error": {
    "code": "validation_failed",
    "message": "qty must be at least 1",
    "field": "qty"
  }
}

• Pagination: offset/limit (?offset=40&limit=20) is simple but slow and shifts when rows are added. Cursor pagination (?after=eyJpZCI6Mn0) is stable and fast for large data.
• Versioning: /v1/ in the path or a header. Never break existing clients. Add fields, and don't rename or remove them.
• Rate limiting: return 429 with a Retry-After header.
• Documentation: describe the API in OpenAPI (Swagger). FastAPI generates it automatically at /docs.

Authentication options

Beyond REST

Calling APIs well

import requests

def get_weather(city: str) -> dict:
    r = requests.get(
        "https://api.example.com/v1/weather",
        params={"city": city},
        headers={"Authorization": f"Bearer {API_KEY}"},
        timeout=5,                       # ALWAYS set a timeout
    )
    if r.status_code == 404:
        raise CityNotFound(city)
    r.raise_for_status()                 # turn other 4xx/5xx into exceptions
    return r.json()

Try it

1. Design the endpoints for a library app (books, members, loans) on paper: paths, methods, status codes.
2. Build two endpoints in FastAPI and open the generated /docs page.
3. Call a public API (for example, GitHub's https://api.github.com/users/<name>) with curl and with Python.

Deep dive

Databases in depth

Data usually outlives the code that wrote it. A well-designed schema and the right indexes matter more for an app's long-term health than almost any code choice.

Relational basics

• Schema: the tables, their columns and types, and the rules (NOT NULL, UNIQUE, CHECK, foreign keys).
• Relationships: one-to-many (a user has many orders: put user_id on orders). Many-to-many (students ↔ courses: a join table enrollments(student_id, course_id)).

SQL tour

INSERT INTO users (id, name, city) VALUES (1, 'Ana', 'Cairo');
UPDATE users SET city = 'Giza' WHERE id = 1;
DELETE FROM users WHERE id = 1;

SELECT city, COUNT(*) AS n            -- cities with more than 100 users
FROM users
GROUP BY city
HAVING COUNT(*) > 100                 -- HAVING filters groups; WHERE filters rows
ORDER BY n DESC;

SELECT name FROM users                -- users who never ordered
WHERE id NOT IN (SELECT user_id FROM orders);

JOINs

Indexes

• Usually a B-tree: a sorted, wide, shallow tree. Finding a row among millions takes 3–4 page reads.
• Index the columns you filter, join and sort on (WHERE, JOIN ... ON, ORDER BY). Primary keys are indexed automatically.
• Composite index (city, created_at) helps queries filtering by city, or by city and date, but not by date alone (the leftmost-prefix rule).
• Every index slows down writes and takes space. Don't index everything.
• Prefix a query with EXPLAIN to see whether it uses an index or scans the whole table.

Transactions and ACID

BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
COMMIT;            -- or ROLLBACK; if anything failed, so neither change happens

Normalization in plain words

• Store each fact once. A customer's address lives in customers, not copied into every order.
• One value per cell (no comma-separated lists), and every column depends on the row's key.
• Denormalize on purpose (copy data) only when reads are too slow, and accept the work of keeping copies in sync.

The N+1 query problem

orders = db.query("SELECT * FROM orders LIMIT 100")    # 1 query
for o in orders:
    o.user = db.query("SELECT * FROM users WHERE id = %s", o.user_id)  # +100 queries!

# fix: one JOIN (or the ORM's eager loading, e.g. select_related / joinedload)
rows = db.query("""SELECT o.*, u.name FROM orders o
                   JOIN users u ON u.id = o.user_id LIMIT 100""")

SQL vs NoSQL

Try it

1. Complete SQLBolt lessons 1–12.
2. Design a schema for a library (books, authors, members, loans), including a many-to-many.
3. Load 100,000 rows into SQLite, time a query, add an index, then time it again with EXPLAIN QUERY PLAN.

Deep dive

Concurrency in depth

Concurrency bugs are rare, timing-dependent, and hard to reproduce. The defense is design: share less, and protect what you must share.

Vocabulary

• Critical section: code that touches shared data and must not be interleaved.
• Atomic: happens as one indivisible step. count += 1 is not atomic.
• Thread-safe: correct even when called from many threads at once.
• Blocking: a call that waits (reading a file, a network request, acquiring a lock).

Synchronization tools

Deadlock

A deadlock needs all four Coffman conditions: mutual exclusion, hold-and-wait, no preemption, and circular wait. Break any one to prevent it. In practice: always acquire locks in the same global order, hold them briefly, and use timeouts.

• Starvation: a thread never gets its turn because others keep winning.
• Livelock: threads keep reacting to each other and never progress (two people stepping aside in a hallway forever).

Python: pick the right model

CPython has a GIL (global interpreter lock), so only one thread runs Python bytecode at a time. Threads still help while waiting on I/O, because waiting releases the GIL. For CPU-heavy work, use processes. (Python 3.13+ has an experimental build without the GIL.)

import asyncio, httpx

async def fetch(client, url):
    r = await client.get(url)              # while waiting, other tasks run
    return r.status_code

async def main(urls):
    async with httpx.AsyncClient(timeout=10) as client:
        return await asyncio.gather(*(fetch(client, u) for u in urls))   # all at once

asyncio.run(main(["https://example.com"] * 50))

from concurrent.futures import ProcessPoolExecutor
with ProcessPoolExecutor() as pool:                # uses every CPU core
    results = list(pool.map(heavy_compute, inputs))

Producer–consumer with a queue

import queue, threading
jobs = queue.Queue()

def worker():
    while True:
        job = jobs.get()          # blocks until a job arrives
        process(job)
        jobs.task_done()

for _ in range(4):
    threading.Thread(target=worker, daemon=True).start()
for item in items:
    jobs.put(item)                # producers just add work
jobs.join()                       # wait until every job is done

Try it

1. Run the counter example without the lock, with 8 threads and 1,000,000 iterations. Try to see a wrong total.
2. Download 20 URLs sequentially, then with a thread pool, then with asyncio. Compare the times.
3. Write a deadlock on purpose with two locks, then fix it with consistent lock ordering.

Deep dive

System design in depth

System design means choosing building blocks and trade-offs so a product stays fast, available and affordable as it grows.

A framework for any design question

1. Requirements: what must it do (functional), and how well (non-functional: users, latency, availability, consistency)?
2. Estimates: requests per second, data size per year, read/write ratio.
3. API: the main endpoints.
4. Data model: tables or documents, and which database fits.
5. High-level design: boxes and arrows, as in the diagram below.
6. Deep dive: the hardest part (hot keys, fan-out, consistency).
7. Bottlenecks and trade-offs: what breaks first at 10× load, and what you'd change.

Load balancing

A load balancer spreads requests across servers, removes unhealthy ones (health checks), and lets you add servers without clients noticing. The strategy matters when requests have very different costs.

Caching

• Eviction: LRU (least recently used), LFU (least frequently used), or TTL (expire after a set time).
• Invalidation is the hard part: when data changes, delete or update the cached copy. Short TTLs limit how stale data can get.
• Layers: browser cache → CDN → application cache (Redis) → database buffer cache.

Scaling the database

• Indexes and query fixes first. They're the cheapest wins.
• Read replicas: copies that serve reads. Writes go to the primary. Replicas can lag slightly (eventual consistency).
• Sharding: split rows across databases by a key (user_id % N, or consistent hashing). Scales writes, but cross-shard queries and joins get hard.
• Connection pooling: reuse DB connections instead of opening one per request.

Asynchronous processing

Put slow or unreliable work (emails, video encoding, reports) on a queue, and let workers process it. The user gets a fast response, and spikes are smoothed out. Consumers must be idempotent, because messages can be delivered more than once. Pub/sub sends one event to many independent subscribers.

Consistency and CAP

When the network splits a distributed system into parts that can't talk (a partition), each part must choose: keep answering with possibly stale data (availability), or refuse until it can be sure (consistency). Banking leans consistent. A social feed leans available.

Reliability patterns

• Redundancy: no single point of failure (2+ servers, replicas, multiple zones).
• Timeouts + retries with exponential backoff and jitter (wait 1s, 2s, 4s… plus randomness so clients don't retry in sync).
• Circuit breaker: stop calling a failing dependency for a while instead of piling on.
• Rate limiting protects you from abuse and runaway clients.
• Graceful degradation: if recommendations are down, show the page without them.

Back-of-the-envelope numbers

Monolith vs microservices

Worked example: a URL shortener

• API: POST /links {url} → {code: "aZ3kP9"}; GET /aZ3kP9 → 301 redirect.
• Code generation: an auto-increment ID converted to base62. 7 characters give 62⁷ ≈ 3.5 trillion codes.
• Data: one table links(code PK, url, created_at). Reads vastly outnumber writes.
• Scale: cache hot codes in Redis, put a CDN in front of redirects, add read replicas, and send click counting through a queue so redirects stay fast.

Try it

1. Design a pastebin service on paper using the 7-step framework. Time-box it to 30 minutes.
2. Add Redis caching to one slow endpoint of your API and measure before and after.
3. Read the System Design Primer's sections on caching and databases.

Deep dive

Security in depth

Most breaches don't involve clever cryptography. They exploit ordinary mistakes: trusting input, weak access checks, leaked secrets and outdated dependencies.

The goals (CIA triad)

• Confidentiality: only the right people can read the data.
• Integrity: data isn't changed without permission.
• Availability: the system stays up for legitimate users.

The OWASP Top 10 in plain words (2021 list)

Access control: the #1 risk

@app.get("/invoices/{invoice_id}")
def get_invoice(invoice_id: int, user = Depends(current_user)):
    inv = db.get_invoice(invoice_id)
    if inv is None or inv.owner_id != user.id:   # authorization, every time
        raise HTTPException(status_code=404)     # 404 hides whether it exists
    return inv

Hiding a button in the UI is not security. Anyone can send the request directly. Every check must happen on the server.

XSS and CSRF

• XSS (cross-site scripting): an attacker stores <script>steal(document.cookie)</script> as their username, and it runs in other users' browsers. Defense: frameworks escape output by default (don't bypass it with innerHTML or |safe), use HttpOnly cookies, and add a Content-Security-Policy header.
• CSRF (cross-site request forgery): a malicious site makes your browser send a request to your bank with your cookies. Defense: SameSite cookies and CSRF tokens on forms.

Passwords: hashing, not encryption

• Encryption is reversible with a key. Hashing is one-way. For passwords you never need the original, so hash them.
• A salt (random value per user) means equal passwords get different hashes, which defeats precomputed tables.
• Use deliberately slow hashes (bcrypt, argon2, scrypt). Fast hashes like SHA-256 let attackers guess billions per second.
• Better still: offer MFA, and let users sign in with passkeys or OAuth providers.

Secrets

# .env  (listed in .gitignore, never committed)
DATABASE_URL=postgres://app:...@db:5432/shop
STRIPE_SECRET_KEY=sk_live_...

# code reads it from the environment
import os
DB_URL = os.environ["DATABASE_URL"]

• In production, use a secret manager (AWS Secrets Manager, Vault, your platform's env settings).
• If a secret is ever pushed, rotate it immediately. Deleting the commit isn't enough.
• Don't log secrets, tokens or full card numbers.
• Least privilege: the app's DB user can't drop tables, and a read-only service gets a read-only key.

Security checklist for every feature

1. Who is allowed to do this, and is that checked on the server?
2. Where does input enter, and is it validated and parameterized?
3. Does output escape user content?
4. Are secrets out of the code and out of the logs?
5. What happens if someone sends this request 10,000 times?

Try it (legally)

1. Hack OWASP Juice Shop, an intentionally vulnerable app built for practice.
2. Do the SQL injection and access control labs at PortSwigger Web Security Academy (free).
3. Run pip-audit or npm audit on one of your projects.

Deep dive

Delivery, operations & teamwork

Software only has value once it reaches users and stays healthy there. This is the process around the code.

How teams organize work

• Agile: deliver in small increments, get feedback, adjust. Not a fixed process, but a set of values.
• Scrum: fixed sprints (often 2 weeks). Planning → daily stand-up (done / doing / blocked) → sprint review (demo) → retrospective (improve the process).
• Kanban: a board of To do / In progress / Review / Done, with limits on work in progress. Continuous flow, no sprints.
• User story: "As a shopper, I want to save my cart so that I can finish later", plus acceptance criteria that say when it's done.

Code review

CI/CD and deployment strategies

A pipeline runs on every push: install → lint → type-check → test → build an artifact (often a Docker image) → deploy to staging → (approval or automatic) → production.

Containers

# Dockerfile: the same environment on every laptop, CI runner and server
FROM python:3.12-slim
WORKDIR /app
COPY requirements.txt .
RUN pip install --no-cache-dir -r requirements.txt
COPY . .
CMD ["uvicorn", "main:app", "--host", "0.0.0.0", "--port", "8000"]

A container packages your app with its exact dependencies. Kubernetes and similar platforms run many containers, restart crashed ones and scale them. Keep configuration in environment variables so the same image runs in every environment (the "12-factor app" idea).

Observability

• SLI = what you measure (successful requests %). SLO = your target (99.9% over 30 days). The gap is your error budget for risky changes.
• Use structured logs (JSON with fields), not free text, so you can search and aggregate them.
• After an incident, write a blameless postmortem: timeline, root cause, what made it worse, and action items. Fix the system, not the person.

Documentation that pays off

• README: what it is, how to run it locally in under 5 minutes, how to run the tests.
• ADR (architecture decision record): a short note on why you chose X over Y, so future readers know the context.
• API docs generated from code (OpenAPI), and runbooks for on-call ("if X alerts, check Y").

Try it

1. Add the GitHub Actions workflow from the crash course to a project and make a test fail on purpose.
2. Write a Dockerfile for your API and run it with docker run -p 8000:8000.
3. Write a README that lets a friend run your project without asking you anything.

Deep dive

System design interview playbook

A system design round is a 45-minute conversation with no single right answer. You're scored on driving it in a structured way, using real numbers, and making and defending trade-offs.

What's expected at each level

How to spend 45 minutes

1. 0–5 · Requirements. Functional: the 3–4 core features (and what's out of scope). Non-functional: users, read/write ratio, latency, availability vs consistency, durability.
2. 5–10 · Estimates. QPS (average and peak), storage per year, bandwidth. Rough numbers are fine. Their purpose is to drive decisions ("100k writes/s, so one Postgres instance won't do").
3. 10–15 · API and data model. 3–5 endpoints. The main entities, their keys, and which database fits the access pattern.
4. 15–25 · High-level design. Draw the boxes: clients → LB → services → cache / DB / queue. Walk one request through it.
5. 25–40 · Deep dives. The interviewer picks, or you propose, the hardest parts: hot keys, fan-out, consistency, a component failing, scaling 10×.
6. 40–45 · Wrap up. Summarize the trade-offs, what you'd monitor, and what you'd change at 100× scale.

Estimation cheat sheet

Example: a news feed with 100M daily users
  reads:  100M × 20 feed loads/day = 2B/day ÷ 10^5 ≈ 20k QPS (peak ~100k)
  writes: 100M × 0.5 posts/day     = 50M/day ÷ 10^5 ≈ 500 QPS
  → read-heavy at about 40:1, so precompute feeds and cache them aggressively
  storage: 50M posts × 1 KB ≈ 50 GB/day ≈ 18 TB/year (+ media in object storage)

The question bank

How to talk about trade-offs

"I'd pick Cassandra here: writes outnumber reads 10 to 1, and we only ever query
 by chat_id. The cost is giving up joins and strong consistency, which we don't need
 for message history. If we later needed transactional updates, I'd revisit Postgres
 with sharding."

"Fan-out on write makes reads fast, but a celebrity post would mean 50M writes.
 So: a hybrid. Push for normal users, and pull at read time for accounts over ~100k followers."

Red flags interviewers note

• Drawing boxes before asking a single requirements question.
• Adding Kafka, microservices or Kubernetes "because it scales", with no numbers to justify them.
• No estimates, or estimates that never affect a decision.
• Single points of failure, and no answer to "what if this box dies?"
• Monologuing for 20 minutes without checking in with the interviewer.
• Using buzzwords without depth: saying "eventual consistency" but not knowing what anomaly it allows.

Practice routine

1. Pick one question from the bank. Set a 45-minute timer, talk out loud, and draw (Excalidraw works well).
2. Compare with a reference design (System Design Primer, ByteByteGo, Hello Interview). List what you missed.
3. For each component you chose, explain why it beats the alternative. Use the deep-dive topics to fill gaps.
4. Do at least 3 mock design interviews with someone senior.

Deep dive

Fundamentals & failure

A distributed system is one where a computer you didn't know existed can make your own computer unusable. Designing for failure is the whole job.

Why distribute at all?

The eight fallacies of distributed computing

False assumptions engineers new to distributed systems make (L. Peter Deutsch and colleagues, Sun Microsystems):

1. The network is reliable.
2. Latency is zero.
3. Bandwidth is infinite.
4. The network is secure.
5. Topology doesn't change.
6. There is one administrator.
7. Transport cost is zero.
8. The network is homogeneous.

Failure models

Most business systems assume crash-recovery nodes and an asynchronous network (no upper bound on delay). In that world you can never tell a slow node from a dead one. A timeout is a guess.

Timeouts, retries and idempotency

• Timeouts: always set one. Too short causes false alarms and retry storms. Too long leaves users waiting. Base them on measured p99 latency.
• Retries only for transient errors (timeouts, 503, connection reset). Use exponential backoff + jitter, a maximum number of attempts, and a retry budget so retries never exceed, say, 10% of traffic.
• Idempotency: make operations safe to repeat. Natural (SET status = 'paid'), or with an idempotency key stored with the result. Then "at-least-once" delivery becomes "effectively once".
• Deadlines propagate: if the user's request has 2s left, a downstream call shouldn't wait 5s. gRPC passes deadlines automatically.

-- idempotency table: the unique key turns a repeated request into a no-op
CREATE TABLE idempotency_keys (
  key         TEXT PRIMARY KEY,
  response    JSONB NOT NULL,
  created_at  TIMESTAMPTZ DEFAULT now()
);
-- in one transaction: INSERT the key (fails if it exists) + do the charge + store the response

Measuring availability

Dependencies multiply: a service that needs 5 others, each at 99.9%, is at most 0.999⁵ ≈ 99.5% available. Redundancy and graceful degradation are how you climb back up.

Try it

1. Add timeouts and retries with jitter to every outbound HTTP call in one of your projects.
2. Make one POST endpoint idempotent with an idempotency key table, and test it by sending the same request twice.
3. Read three public postmortems (search "AWS post-event summary" or "Cloudflare outage blog"). Write down the root cause and what made each one worse.

Deep dive

Time, clocks & ordering

There is no global "now" in a distributed system. Each machine only knows its own clock and the messages it has received.

Physical clocks and their problems

• Quartz clocks drift (roughly 10–100 ms per day). NTP syncs them over the network, typically to within a few ms on a LAN and tens of ms over the internet.
• NTP can step a clock backwards. Never measure durations with wall-clock time. Use a monotonic clock (time.monotonic(), System.nanoTime()).
• Last-write-wins by timestamp (Cassandra's default) can silently drop a write that really came later, if the writer's clock was behind.
• Google Spanner uses GPS and atomic clocks (TrueTime), which give a bounded uncertainty interval. It waits out that uncertainty before committing, to get globally ordered transactions.

Happens-before

Event A happens before B (A → B) if they're on the same process and A came first, or A is sending a message and B is receiving it, or there's a chain of these. If neither A → B nor B → A, the events are concurrent: neither could have influenced the other.

Lamport clocks vs vector clocks

def merge(a, b):                    # vector clocks as dicts {process: counter}
    return {p: max(a.get(p, 0), b.get(p, 0)) for p in a.keys() | b.keys()}

def compare(a, b):
    le = all(a.get(p, 0) <= b.get(p, 0) for p in a.keys() | b.keys())
    ge = all(a.get(p, 0) >= b.get(p, 0) for p in a.keys() | b.keys())
    if le and not ge: return "a happened before b"
    if ge and not le: return "b happened before a"
    return "equal" if le else "concurrent: a conflict to resolve"

compare({"A": 2, "B": 1}, {"A": 1, "B": 2})    # concurrent

Hybrid logical clocks (HLC)

An HLC combines physical time with a logical counter, so timestamps stay close to wall-clock time while still respecting causality. CockroachDB and YugabyteDB use them.

Ordering guarantees you'll see in tools

• Per-partition order (Kafka): messages with the same key stay ordered. There's no order across partitions.
• FIFO queues (SQS FIFO): order per message group, with lower throughput.
• Total order broadcast: everyone delivers every message in the same order. It's equivalent to consensus, and it's what Raft's log provides.

Try it

1. Simulate three processes exchanging messages in Python with Lamport clocks. Print the final order.
2. Extend it to vector clocks and detect a pair of concurrent events.
3. Find where your language's monotonic clock lives, and replace any time.time() duration measurements with it.

Deep dive

Replication in depth

Keeping copies is easy. Keeping copies in agreement while machines fail and networks lag is the hard part.

Three architectures

Quorums (leaderless)

With N replicas, a write waits for W acknowledgements, and a read queries R replicas and takes the newest version. If R + W > N, the read set and write set overlap in at least one replica, so the read sees the latest write. A common choice is N = 3, W = 2, R = 2.

• Read repair: when a read sees a stale replica, it writes the newest value back to it.
• Anti-entropy: a background process compares replicas (using Merkle trees) and fixes differences.
• Hinted handoff: if a replica is down, another node keeps its writes and hands them over when it returns.

Replication lag anomalies and fixes

Resolving write conflicts

• Last write wins (LWW): keep the highest timestamp. Simple, but it silently loses data.
• Keep all versions (siblings) and let the application or user merge them (Riak, Amazon's original shopping cart).
• CRDTs (conflict-free replicated data types): counters, sets and text structures designed so any merge order gives the same result. Used by Redis Enterprise, Riak, Automerge and Yjs (collaborative editing).

Failover hazards

• Async replication: the new leader may be missing the old leader's last writes. Those writes are lost.
• Split brain: two nodes both believe they're the leader and both accept writes. Prevent it with consensus-based election and fencing tokens (see Consensus).
• Tools that automate failover: Patroni (PostgreSQL + etcd), MySQL Group Replication / Orchestrator, MongoDB replica-set elections, Redis Sentinel.

Try it

1. Run a PostgreSQL primary and replica with Docker Compose. Write to the primary, then query the replica, and measure the lag with pg_stat_replication.
2. Start a 3-node Cassandra cluster, write at ONE, stop a node, and read at QUORUM.
3. Implement a grow-only counter CRDT and merge two replicas in different orders.

Deep dive

Partitioning in depth

Partitioning is how one logical dataset grows past one machine. The partition key you choose decides which queries are cheap and which are painful.

Strategies

Choosing a partition key

• It should have high cardinality (many distinct values) and spread traffic evenly.
• Queries should usually include it. Otherwise each query must ask every partition (scatter-gather).
• Hot keys (a celebrity's posts, a viral product) overload one partition. Fixes: add a random suffix to spread writes (post123#7) and merge on read, or cache the hot key.
• Compound keys are common: Cassandra's PRIMARY KEY ((user_id), created_at) partitions by user and sorts by time within the partition.

Consistent hashing and virtual nodes

With plain hash % N, going from 4 to 5 nodes moves about 80% of keys. With a hash ring, it moves about 20%. Virtual nodes (each physical node appears at 100+ points on the ring) even out the load and spread a dead node's keys across all survivors. Redis Cluster uses a fixed set of 16,384 hash slots that are reassigned between nodes, which has the same effect.

Secondary indexes

Rebalancing and routing

• Never rebalance with hash % N. Use a fixed number of partitions much larger than the node count, and move whole partitions (Kafka, Elasticsearch, Riak).
• Routing options: any node forwards the request (Cassandra gossip), a routing tier (mongos, Vitess vtgate), or a partition-aware client (Kafka, Redis Cluster clients).
• The cluster map usually lives in a coordination service: etcd, ZooKeeper, or the system's own Raft group.

Try it

1. Use the Ring class from the crash course with 4 nodes and 10,000 keys. Add a 5th node and count how many keys moved. Repeat with hash % N.
2. Design the partition key for a chat app's messages table, then for an IoT sensor readings table.
3. Create a 3-node Redis Cluster with Docker and look at slot ownership with CLUSTER SLOTS.

Deep dive

Consistency models & CAP

"Consistent" means different things in different contexts. Knowing the exact guarantee a database gives tells you which bugs are possible in your app.

From strongest to weakest

Transaction isolation (a different axis)

Consistency models describe replicas. Isolation levels describe concurrent transactions.

Write skew example: two doctors on call each check "at least one other doctor is on call", and both go off call at the same moment. Each transaction was valid on its own, but together they broke the rule. Only serializable isolation (or explicit locking with SELECT ... FOR UPDATE) prevents it.

CAP, precisely

• CAP is about linearizability vs availability during a network partition. Partitions will happen, so "CA" isn't a real option for a distributed system.
• Most systems let you tune per operation (Cassandra consistency levels, DynamoDB's ConsistentRead, MongoDB read and write concerns).
• PACELC: if Partitioned, choose A or C; Else, choose Latency or Consistency. DynamoDB and Cassandra are PA/EL; Spanner and etcd are PC/EC; MongoDB defaults to PA/EC.

Try it

1. Read Jepsen's consistency map, then one Jepsen analysis of a database you use.
2. In PostgreSQL, reproduce write skew with two psql sessions at REPEATABLE READ, then show that SERIALIZABLE aborts one of them.
3. Classify five systems you know as CP or AP, and describe how each behaves during a partition.

Deep dive

Consensus & coordination

Consensus turns a group of unreliable machines into one reliable decision-maker. It's slow and precious, so systems use it for small, critical data: who's the leader, what's the config, who holds the lock.

Raft in detail

• Roles: follower, candidate, leader. Time is divided into terms (1, 2, 3…), each with at most one leader.
• Election: a follower that hears nothing for a random 150–300 ms becomes a candidate, increments the term, votes for itself and requests votes. Each node votes once per term, and only for a candidate whose log is at least as up to date as its own. A majority wins.
• Log replication: clients send commands to the leader. The leader appends each one to its log and sends AppendEntries to followers. Once a majority has stored an entry, it's committed, applied to the state machine, and the client gets its answer.
• Safety: committed entries are never lost, because any future leader must have received votes from a majority, and that majority overlaps with the majority that stored the entry.

Theory you should recognize

• FLP impossibility: in a fully asynchronous network, no deterministic algorithm can guarantee consensus if even one node may crash. Real systems get around it with timeouts (partial synchrony) and randomness.
• Paxos (Lamport): the original, proven, notoriously hard to understand. Multi-Paxos is used in Chubby and Spanner. Zab powers ZooKeeper. Raft was designed to be understandable: etcd, Consul, CockroachDB, TiKV, Kafka KRaft.
• Throughput is limited by the leader and by a majority round trip per commit. Big systems run many Raft groups, one per partition (CockroachDB, TiKV).

Distributed locks, leases and fencing

A lock holder can pause (a GC pause, a VM migration) and wake up after its lease expired, still believing it holds the lock. The fix is a fencing token: an increasing number given out with each lock grant. The storage rejects writes carrying an older token.

# etcd lock with a lease (python-etcd3)
import etcd3
client = etcd3.client(host="etcd", port=2379)
with client.lock("invoice-run", ttl=30) as lock:   # lease expires if we die
    token = lock.revision                          # use as a fencing token
    storage.write(batch, fencing_token=token)      # storage rejects older tokens

Coordination tools

Try it

1. Play with the interactive Raft visualization: stop the leader, partition nodes, and watch the terms.
2. Run a 3-node etcd cluster in Docker. Kill the leader and watch etcdctl endpoint status elect a new one.
3. Do the Raft lab from MIT 6.5840 (Go), the best way to truly understand it.

Deep dive

Messaging & event streaming

Brokers decouple services in time (the receiver can be down) and in rate (the receiver can be slower). Most of the work is in delivery guarantees.

Three shapes

Delivery semantics

• At-most-once: commit before processing. A crash loses the message. Fine for metrics sampling.
• At-least-once: commit after processing. A crash causes a redelivery. This is the default, so consumers must be idempotent: deduplicate by message ID, or use upserts.
• Exactly-once: Kafka transactions give exactly-once within Kafka (read → process → write to Kafka). Side effects elsewhere still need idempotency.

Kafka essentials

• Topic → partitions (the unit of parallelism and ordering) → each partition replicated on several brokers (replication factor 3, min.insync.replicas=2, producer acks=all for durability).
• Max useful consumers in a group = number of partitions. Choose partition counts with growth in mind.
• Retention by time or size, or log compaction (keep only the latest value per key, which makes a topic usable as a changelog).
• Ecosystem: Kafka Connect (move data in and out of databases and S3), Debezium (change data capture from database logs), Schema Registry (Avro/Protobuf schemas), Kafka Streams / ksqlDB / Flink (processing).
• Consumer lag (newest offset − committed offset) is the key health metric.

Reliability patterns

• Dead-letter queue (DLQ): after N failed attempts, park the message for inspection instead of blocking the queue forever.
• Backpressure: when consumers fall behind, slow producers down or scale consumers up. Don't buffer without limit.
• Transactional outbox + CDC: write the event into an outbox table in the same DB transaction, and let Debezium stream it to Kafka.

Event-driven architecture patterns

• Event notification: "OrderPlaced {id}". Consumers fetch the details they need.
• Event-carried state transfer: the event contains all the data, so consumers keep their own copy.
• Event sourcing: store the sequence of events as the source of truth, and rebuild state by replaying them. You get an audit log for free, at the cost of complexity.
• CQRS: separate write models from read models (for example, writes to PostgreSQL, events to Kafka, reads from Elasticsearch).

Try it

1. Run Kafka (or Redpanda) with Docker. Create a 3-partition topic, produce keyed messages, and run two consumers in one group.
2. Kill a consumer mid-processing and observe the redelivery. Then make the handler idempotent.
3. Set up a RabbitMQ work queue with a dead-letter exchange.

Deep dive

Distributed transactions

Atomic changes across machines are possible but expensive. Most microservice architectures choose eventual consistency with sagas instead.

Two-phase commit (2PC)

• Phase 1 prepare: each participant writes the change durably, locks it, and votes yes or no. Phase 2 commit/abort: the coordinator decides and tells everyone.
• A participant that voted yes cannot change its mind. If the coordinator then disappears, the participant stays blocked, holding locks.
• Where it's used: inside distributed databases (Spanner and CockroachDB run 2PC on top of Raft groups, so the coordinator itself is replicated), and XA transactions between a database and a message broker.

Sagas

• Compensations are business actions, not rollbacks: "refund" and "send apology email", not "pretend it didn't happen".
• Sagas lack isolation: others can see intermediate states (an order that's "pending payment"). Model those states explicitly.
• Every step and every compensation must be idempotent and retryable.

Durable execution (Temporal)

# Temporal workflow (Python SDK): the code reads like a plain function,
# but every step is persisted, so the workflow survives crashes and redeploys
@workflow.defn
class OrderWorkflow:
    @workflow.run
    async def run(self, order):
        await workflow.execute_activity(charge_payment, order, start_to_close_timeout=timedelta(seconds=30))
        try:
            await workflow.execute_activity(reserve_stock, order, start_to_close_timeout=timedelta(seconds=30))
        except ActivityError:
            await workflow.execute_activity(refund_payment, order, start_to_close_timeout=timedelta(seconds=30))
            raise
        await workflow.execute_activity(schedule_shipping, order, start_to_close_timeout=timedelta(minutes=5))

Other patterns

• TCC (try-confirm-cancel): reserve resources first (try), then confirm or cancel. Like 2PC at the business level, with timeouts.
• Outbox + idempotent consumers: the workhorse for "update my DB and tell others" (see Messaging).
• Avoid it entirely: often the best fix is redrawing service boundaries so data that must change atomically lives in one service.

Try it

1. Implement the saga orchestrator from the crash course with fake services that fail randomly. Make sure compensations always run.
2. Run the Temporal Python samples locally and kill the worker mid-workflow.
3. Draw the state machine for an order (pending → paid → reserved → shipped, plus every failure state).

Deep dive

Distributed databases & storage

Every data store is a bundle of choices about replication, partitioning, consistency and storage engine. Knowing those choices tells you when each one fits.

Storage engines: B-tree vs LSM-tree

The landscape

Caching at scale

• Cache stampede: a hot key expires and 1,000 requests hit the database at once. Fixes: per-key locks (single-flight), early randomized refresh, or serving stale data while one request refreshes it.
• Consistency: on writes, delete the cache entry rather than updating it, to avoid race conditions. Use TTLs as a safety net.
• Redis is more than a cache: INCR + EXPIRE for rate limiting, sorted sets for leaderboards, streams for lightweight queues.

import redis
r = redis.Redis(host="redis", port=6379)

def allow(user_id, limit=100, window=60):          # fixed-window rate limiter
    key = f"rate:{user_id}:{int(time.time() // window)}"
    count = r.incr(key)
    if count == 1:
        r.expire(key, window)
    return count <= limit

r.zadd("leaderboard", {"mona": 1530, "ali": 1490})
r.zrevrange("leaderboard", 0, 9, withscores=True)  # top 10 in O(log n + 10)

Try it

1. Model the same "orders by customer" feature in PostgreSQL, DynamoDB (partition key + sort key) and MongoDB. Compare the queries.
2. Build the Redis rate limiter above and load-test it with a loop.
3. Run CockroachDB's single-command demo cluster and kill a node during a query.

Deep dive

Microservices, networking & resilience

Microservices trade in-process function calls for network calls. Everything in this topic exists to make those network calls survivable.

Communication

// orders.proto: the contract both services compile against
syntax = "proto3";
service Orders {
  rpc GetOrder (GetOrderRequest) returns (Order);
}
message GetOrderRequest { string id = 1; }
message Order { string id = 1; string status = 2; int64 total_cents = 3; }

The infrastructure around services

• Load balancers: L4 (TCP: AWS NLB, HAProxy) or L7 (HTTP-aware routing: NGINX, Envoy, AWS ALB, Traefik).
• API gateway: authentication, rate limits, routing, request aggregation (Kong, AWS API Gateway, Apigee, NGINX).
• Service discovery: Kubernetes Services + DNS, Consul, Eureka.
• Service mesh: a sidecar proxy (Envoy) next to every instance handles mTLS, retries, timeouts, traffic splitting and metrics, without code changes (Istio, Linkerd, Consul Connect).

Resilience patterns

Rate limiting: token bucket

A bucket holds up to B tokens and refills at R tokens per second. Each request takes one token, or is rejected with 429 if the bucket is empty. It allows short bursts while enforcing an average rate.

Microservice pitfalls

• Distributed monolith: services that must deploy together or call each other synchronously in long chains. You get all the costs of both styles.
• Shared database between services couples them. Each service should own its data.
• Chatty calls: 50 network calls to render one page. Batch them, or add an aggregation layer.
• Start as a modular monolith. Split out a service when a team or scaling boundary clearly calls for it.

Try it

1. Put NGINX or Envoy in front of two instances of your API, then stop one and watch traffic shift.
2. Wrap a flaky HTTP call with tenacity retries and pybreaker, and simulate failures.
3. Define a small gRPC service from a .proto file and call it from Python.

Deep dive

Containers, Kubernetes & infrastructure as code

Kubernetes is a distributed system for running distributed systems. Its core idea, declare the desired state and let controllers converge to it, shows up across modern infrastructure.

Containers

• An image is a stack of read-only layers (base OS → runtime → dependencies → your code). Order your Dockerfile from least to most frequently changing so builds reuse cached layers.
• A container is an isolated process (Linux namespaces + cgroups), not a virtual machine. It starts in milliseconds and shares the host kernel.
• Use small base images (slim, distroless), run as a non-root user, and pin versions. Use multi-stage builds to leave compilers out of the final image.
• Docker Compose runs multi-container setups locally (app + Postgres + Redis + Kafka) from one YAML file.

Kubernetes architecture

• Probes: liveness (restart if stuck), readiness (send no traffic until ready), startup (slow boots).
• Requests and limits: requests reserve CPU and memory for scheduling. Going over the memory limit gets the container killed (OOMKilled).
• The control plane's only source of truth is etcd, which is Raft (see Consensus).

kubectl get pods -o wide                     # what's running, and where
kubectl describe pod shop-api-7d9f-abcde     # events: why is it not starting?
kubectl logs -f deploy/shop-api              # stream logs
kubectl rollout status deploy/shop-api       # watch a rolling update
kubectl rollout undo deploy/shop-api         # roll back
kubectl scale deploy/shop-api --replicas=5
kubectl port-forward svc/shop-api 8080:80    # reach it from your laptop

Infrastructure as code

# main.tf: Terraform describes cloud resources; `terraform plan` shows the diff, `apply` makes it so
resource "aws_s3_bucket" "uploads" {
  bucket = "shop-uploads-prod"
}

resource "aws_sqs_queue" "emails" {
  name                      = "emails"
  message_retention_seconds = 345600
}

• Terraform / OpenTofu / Pulumi: cloud infrastructure. Ansible: configure machines. Helm / Kustomize: template K8s YAML.
• GitOps (Argo CD, Flux): the cluster continuously syncs to a Git repo, and every change is a reviewed pull request.

Cloud service cheat sheet

Try it

1. Install kind or minikube. Deploy the crash course YAML, delete a pod, and watch it come back.
2. Change the image tag and watch a rolling update with kubectl rollout status, then roll back.
3. Write a Docker Compose file for app + Postgres + Redis, and a Terraform file that creates one S3 bucket.

Deep dive

Observability & reliability engineering

You can't fix what you can't see. In a distributed system, seeing means correlating metrics, logs and traces from dozens of services.

The pipeline

Metrics

• Types: counter (only goes up: requests), gauge (up and down: queue length), histogram (latency distribution, from which you compute p50, p95 and p99).
• RED for services (Rate, Errors, Duration). USE for resources (Utilization, Saturation, Errors). Four golden signals: latency, traffic, errors, saturation.
• Watch percentiles, not averages. An average of 50 ms can hide a p99 of 3 s, and in a fan-out request, users feel the slowest call.
• Cardinality: never use user IDs as metric labels. Every label combination becomes a separate time series.

from prometheus_client import Counter, Histogram, start_http_server
REQS = Counter("http_requests_total", "Requests", ["route", "status"])
LAT  = Histogram("http_request_duration_seconds", "Latency", ["route"])

@LAT.labels(route="/checkout").time()
def checkout():
    ...
    REQS.labels(route="/checkout", status="200").inc()

start_http_server(9100)        # Prometheus scrapes http://host:9100/metrics

Logs and traces

• Use structured JSON logs with trace_id, service and user_id fields, so one search shows a request's whole journey.
• Tracing context travels in the W3C traceparent header. OpenTelemetry auto-instrumentation adds it to HTTP, gRPC, database and Kafka clients for you.
• Sampling: keep every error trace and a percentage of normal ones (tail-based sampling in the OTel Collector).

Tools

SRE practices

• SLI → SLO → error budget: "99.9% of checkout requests succeed in under 500 ms over 30 days." The remaining 0.1% is the budget. When it's spent, freeze risky launches and fix reliability.
• Alert on symptoms users feel (an SLO burn rate), not on every CPU spike. Every page should be urgent and actionable.
• Chaos engineering: inject failures on purpose (kill pods, add latency, drop a zone) to prove your resilience works. Tools: Chaos Monkey, Gremlin, LitmusChaos, Chaos Mesh, AWS FIS.
• Load testing with k6, Locust or Gatling before the big launch, not during it.
• Incidents: an incident commander, a communication channel, mitigation first (roll back) and root cause later, followed by a blameless postmortem.

Try it

1. Run Prometheus + Grafana with Docker Compose, instrument an endpoint, and build a p95 latency panel.
2. Add OpenTelemetry auto-instrumentation to two services that call each other, and view the trace in Jaeger.
3. Write an SLO for your API and an alert on its burn rate.

Deep dive

Big data & stream processing

When the data is too big for one machine to process, send the computation to the data and run it in parallel on many machines.

MapReduce: the idea behind it all

Map each input piece to key-value pairs in parallel, shuffle so every value for a key lands on the same machine, then reduce each key's values to a result. Every stage is parallel and can be retried, so a dead machine just means rerunning its piece.

Batch vs stream

# PySpark: the same word count, distributed across a cluster
from pyspark.sql import SparkSession, functions as F
spark = SparkSession.builder.appName("wordcount").getOrCreate()
lines = spark.read.text("s3://logs/2026/10/*.txt")
counts = (lines.select(F.explode(F.split(F.lower("value"), r"\W+")).alias("word"))
               .where(F.col("word") != "")
               .groupBy("word").count()             # groupBy causes the shuffle
               .orderBy(F.desc("count")))
counts.write.parquet("s3://reports/wordcount/")

Streaming concepts

• Event time vs processing time: events arrive late and out of order. Window by when they happened, and use watermarks to decide when a window is complete.
• Windows: tumbling (fixed, non-overlapping), sliding, and session windows (grouped by bursts of activity).
• State and checkpoints: Flink snapshots operator state, so after a crash it resumes exactly where it was.

Where the data lives

• Data lake: raw files in object storage (S3) in columnar formats (Parquet), with table formats (Apache Iceberg, Delta Lake, Hudi) that add transactions and schema evolution.
• Data warehouse: managed, SQL-first, columnar: Snowflake, BigQuery, Redshift, ClickHouse. Lakehouse (Databricks) merges the two.
• Orchestration: Apache Airflow, Dagster and Prefect schedule pipelines as DAGs of tasks, with retries and backfills.
• Lambda architecture runs batch and stream paths side by side. Kappa uses one streaming path, and reprocesses by replaying the Kafka log.

Try it

1. Write word count in plain Python with map, sort-and-group, then reduce. Then run the PySpark version locally.
2. Use Kafka + Flink (or Kafka Streams) to count events per user in 1-minute tumbling windows.
3. Write a two-task Airflow DAG that extracts a CSV and loads it into Postgres every hour.

Deep dive

Case study: a chat system for 50 million users

Putting every topic together: how would you design WhatsApp-style messaging with the tools from this course?

Requirements

• Functional: 1-to-1 and group chats (up to 500 members), online presence, delivery and read receipts, message history on every device.
• Non-functional: messages delivered in under 200 ms when both users are online, never lost, ordered within a chat, available during partial outages.
• Estimates: 50M daily users × 40 messages ≈ 2 billion messages/day ≈ 23k/s on average, around 100k/s at peak. At ~200 bytes each, that's ~400 GB/day, or ~150 TB/year before replication.

Architecture

Key decisions, and which topic they come from

Failure walkthrough

• A gateway dies: clients reconnect (with jitter) to another one. Redis entries expire, and pending messages are redelivered from Kafka.
• A Cassandra node dies: with replication factor 3 and QUORUM writes, writes continue. Hinted handoff and repair catch the node up.
• Kafka consumer lag grows: an alert fires on lag, and the HPA adds consumers up to the partition count.
• Redis is down: degrade by marking presence as unknown and broadcasting to every gateway for that user's region. Slower, but messages still flow.

Design review checklist

1. What happens when each component is slow, or down?
2. Where can a message be duplicated or lost, and how is that handled?
3. What is the partition key of every store and topic, and is there a hot key?
4. Which operations need strong consistency, and which can be eventual?
5. How will you know it's broken before users tell you?

Try it

1. Redesign this for a ride-sharing app (driver location updates every 4 seconds). What changes?
2. Build a tiny version: FastAPI WebSockets + Redis pub/sub + Postgres, with 2 gateway instances behind NGINX.
3. Explain your design out loud in 30 minutes, as in an interview, using the framework from Software Engineering → System design.

Deep dive

The senior rubric & how leveling works

Most loops score every round against level descriptions, and a hiring committee picks the level that the weakest consistent evidence supports. You need senior signals in every round, not just one great design.

Signals per round, mid vs senior

Levels at common companies (approximate)

Titles vary between companies, so use levels.fyi to compare scope and pay.

How to avoid being down-leveled

• Lead, don't follow. Propose the agenda in design ("I'll cover requirements, estimates, API, high-level, then deep-dive on the feed fan-out"). Silence invites the interviewer to steer, and that reads as mid-level.
• Make trade-offs explicit, every time: "Option A gives X, B gives Y. Given Z, I choose A, and the cost is W."
• Bring operations in without being asked: monitoring, rollout, failure handling, data migration.
• Behavioral stories need senior scope. If all your stories are "I fixed a bug in my service", you'll be leveled down regardless of coding.
• Calibrate depth. Breadth first, then depth where it matters. Don't spend 20 minutes on a load balancer algorithm.

Senior loop checklist

1. Coding: 2 Mediums in 45 minutes, while talking, with tests. Comfortable with one concurrency problem.
2. System design: 8–10 designs practised end to end, with failure modes and evolution for each.
3. Behavioral: 8 senior stories in STAR + T + L, each mapped to the company's values.
4. Project deep dive: one system you can present for 45 minutes, with a diagram and numbers.
5. Questions ready for the hiring manager about scope, team and expectations at this level.

Deep dive

Senior behavioral in depth

At senior level, behavioral rounds often decide the level. Interviewers probe each story with follow-ups until they find the edge of your real scope.

The eight stories to prepare

Same question, mid vs senior answer

Follow-ups to expect, and how to handle them

• "What was your role specifically?" Have the "I" parts ready. Credit the team, but be precise about your decisions.
• "What would you do differently?" Give a real, specific change, not "nothing".
• "How did you measure success?" A metric and a baseline.
• "What did the other person think?" Show you understood their position fairly.
• "Then what happened?" Know the long-term outcome.

Mapping to company values

Amazon's Leadership Principles are the best-known example (Ownership, Dive Deep, Have Backbone; Disagree and Commit, Deliver Results, Earn Trust…). Google looks for "Googleyness" and leadership, and Meta for impact, direction and people. Tag each story with 2–3 values, and make sure every value you might be asked about has a story.

Red flags

• Blaming others or the company. No failure story, or a fake one.
• Only "we" and no "I", or only "I" with no credit to others.
• Stories more than 4–5 years old, or all small-scope.
• Rambling past 3 minutes. Aim for 2 minutes, and let them ask follow-ups.

Deep dive

Preparing your project deep dive

Choose one system where you made the important decisions. Prepare it like a talk, with a diagram, numbers and a story arc.

Choosing the project

• Recent (last 2–3 years), with senior scope, technically non-trivial, and with a measurable outcome.
• You owned key decisions, not just implemented them. You know why the alternatives lost.
• Something went wrong along the way. That gives the best material.

The 10-minute presentation template

1. Context (1 min): the business problem, the users, why it mattered, the constraints (team, timeline, legacy).
2. Architecture (2 min): draw it, show the data flow, and give the numbers (QPS, data size, latency target).
3. Hard decisions (4 min): 2–3 of them. For each: the options, the criteria, the choice, and the cost you accepted.
4. Execution (1 min): rollout, migration, how you de-risked it, who you coordinated with.
5. Results (1 min): metrics before and after, incidents, adoption.
6. Reflection (1 min): what you'd do differently now, and what you'd build next.

Questions you will get

Deep dive

The design follow-up catalog

Senior rounds are won in the follow-ups. These are the common follow-up questions interviewers use, with the moves a strong answer makes.

Deep dive

Worked design: a news feed

Twitter/Instagram-style home feed for 300M daily users. The core challenge is fan-out: delivering one post to millions of followers quickly without melting the write path.

Requirements

• Functional: post (text and media), follow, view home feed (reverse-chronological or ranked), paginate.
• Non-functional: feed loads in under 200 ms at p99, a post is visible to followers within seconds, high availability (eventual consistency is fine).

Estimates

reads : 300M users × 10 feed loads/day = 3B/day ≈ 35k QPS avg, ~150k peak
writes: 300M × 0.3 posts/day          = 90M/day ≈ 1k QPS avg
fan-out: average 200 followers → 90M × 200 = 18B feed inserts/day ≈ 200k/s
storage: posts 90M × 1 KB = 90 GB/day; feed caches hold IDs only (8 bytes each)

API and data

POST /v1/posts            {text, media_ids}            → {post_id}
GET  /v1/feed?cursor=...  → {posts: [...], next_cursor}
POST /v1/users/{id}/follow

posts      (post_id PK [Snowflake], author_id, text, media, created_at)  -- sharded by post_id
follows    (follower_id, followee_id)  -- two tables, one sharded each way
feed cache (Redis list per user: newest ~800 post_ids)

Architecture

Deep dive: push, pull, or hybrid

• Push (fan-out on write): when you post, a worker appends the post ID to every follower's cached feed. Reads are O(1), but a celebrity with 50M followers creates 50M writes per post.
• Pull (fan-out on read): at read time, fetch recent posts from everyone you follow and merge them. Writes are cheap, but reads are slow when you follow 2,000 accounts.
• Hybrid (what's used in practice): push for normal authors. For authors above roughly 100k followers, don't push. At read time, merge their latest posts into the cached feed. Inactive users' feeds aren't precomputed at all; they're rebuilt on login.
• Ranking: candidate generation (the merged IDs) → feature fetch → model score → re-rank. This is cached per user for a short time.

Failure modes and operations

• Fan-out backlog (Kafka lag) delays posts. Alert on lag, autoscale workers, and give fan-out to active users priority.
• Redis node lost: the feed rebuilds from the post store and follow graph (slower, but correct). Replicate the cache.
• Deletes and privacy changes must propagate: filter at read time against a "deleted/blocked" set, because cached IDs can't be trusted alone.

Senior follow-ups

Deep dive

Worked design: a payment system

Accept card payments for an e-commerce site through an external processor (Stripe or Adyen). The core challenge is correctness: never charge twice, never lose money, and always be able to explain every cent.

Requirements

• Functional: create a payment for an order, charge through a payment service provider (PSP), handle refunds, record merchant balances.
• Non-functional: exactly-once effect, full auditability, strong consistency for money, ~1k payments/s at peak, tolerant of PSP slowness and outages.

Data model: a double-entry ledger

payments (payment_id PK, order_id UNIQUE, amount_cents, currency, status, idempotency_key UNIQUE, psp_ref)
  status: CREATED → PENDING_PSP → SUCCEEDED | FAILED → (REFUNDED)

ledger_entries (entry_id, txn_id, account, debit_cents, credit_cents, created_at)   -- append-only
  every txn's debits = its credits, e.g. charge $50:
    debit  customer_receivable  5000
    credit merchant_payable      5000
  balances are SUMs over entries; never UPDATE a balance in place

Architecture

Deep dive: never double-charge

1. The client sends an Idempotency-Key. A unique constraint means a retry returns the stored result.
2. The payment row is created as PENDING_PSP before calling the PSP, and the PSP call passes our payment_id as its idempotency key. Retrying the PSP call is then safe too.
3. A PSP timeout means the result is unknown: leave it pending. The PSP webhook, or a status poll, settles it later. Never assume failure and charge again.
4. On success, in one DB transaction: update the status, insert the ledger entries, and insert an outbox event, so "order paid" is published exactly when the money is recorded.
5. A reconciliation job compares our ledger with the PSP's settlement report every day and flags any mismatch for review.

Failure modes

• PSP down: queue the attempts with backoff, show "processing", and fail over to a second PSP for new payments if the business allows it.
• Duplicate webhooks: handle them idempotently, applying a state transition only when moving forward.
• Money-moving code changes: canary releases, plus reconciliation as a safety net.

Senior follow-ups

Deep dive

Worked design: a distributed rate limiter

Limit API requests per user and per API key across 200 gateway instances, adding less than 1–2 ms per request.

Requirements

• Rules like "100 requests/min per user, 10k/min per API key, 5 logins/min per IP". Return 429 with a Retry-After header.
• 2M requests/s across all gateways. Accurate within a few percent is acceptable. The service must keep running if the limiter store is down.

Algorithms

-- Redis Lua: token bucket, atomic per key (KEYS[1]=bucket, ARGV: rate, capacity, now_ms)
local b = redis.call("HMGET", KEYS[1], "tokens", "ts")
local tokens = tonumber(b[1]) or tonumber(ARGV[2])
local ts = tonumber(b[2]) or tonumber(ARGV[3])
tokens = math.min(tonumber(ARGV[2]), tokens + (tonumber(ARGV[3]) - ts) / 1000 * tonumber(ARGV[1]))
local allowed = tokens >= 1
if allowed then tokens = tokens - 1 end
redis.call("HSET", KEYS[1], "tokens", tokens, "ts", ARGV[3])
redis.call("PEXPIRE", KEYS[1], 60000)
return allowed and 1 or 0

Architecture

Deep dives

• Latency: one Redis round trip (~0.5 ms in the same zone). For very hot keys, use a local token cache: each gateway claims a batch of tokens from Redis and spends them locally.
• Scale: a Redis Cluster sharded by limiter key. 2M ops/s needs roughly 20–40 shards.
• Store down: decide per rule whether to fail open (allow traffic, which protects availability) or fail closed (block it, which protects security for logins). Fall back to local per-instance limits.
• Rules live in a config store (etcd or a DB) and are pushed to gateways, so they change without a deploy.

Senior follow-ups

Deep dive

Worked design: a notification system

One platform used by every product team to send push, email and SMS: 1 billion notifications a day, respecting user preferences, never spamming, and retrying failures.

Requirements

• Channels: push (APNs/FCM), email (SES/SendGrid), SMS (Twilio), in-app. Templates, user preferences, quiet hours, per-user rate caps, scheduled sends, delivery tracking.
• 1B per day ≈ 12k/s on average, with campaign peaks around 100k/s. Transactional messages (OTP codes, receipts) must jump ahead of marketing.

Architecture

Deep dives

• Priorities: separate Kafka topics (or queues) per priority and channel, so a 50M-recipient marketing blast can't delay an OTP code.
• Validation pipeline: check preferences and opt-outs, then quiet hours, then a frequency cap ("at most 3 marketing pushes a day"), then deduplicate (notification_id + user), then render the template, then send.
• Retries: exponential backoff per provider error class, a DLQ after N attempts, and a provider circuit breaker with failover to a backup provider (SMS especially).
• Idempotency: each (notification_id, user_id, channel) is sent once. Record it before sending, so a worker crash after sending causes at most a rare duplicate.
• Tracking: delivery and open events flow back through webhooks into an events table for analytics.

Senior follow-ups

Deep dive

Worked design: ticket booking for a flash sale

Sell 50,000 concert seats when 2 million fans arrive in the same minute. The core challenge is contention: no seat sold twice, a fair queue, and a system that stays up.

Requirements

• Browse the seat map, pick seats, hold them for 10 minutes while paying, confirm. No overselling, ever. Fair access. Survive a 100× traffic spike.

Architecture

Deep dives

• Virtual waiting room: users get a queue position (a token stored in Redis or at the edge) and are admitted at a rate the booking tier can handle, for example 2,000 per minute. It protects everything downstream and feels fair.
• Seat holds: SET seat:{event}:{seat} {user} NX EX 600 in Redis gives an atomic, expiring hold. The seat map reads hold keys and sold state.
• Final sale: in Postgres, UPDATE seats SET status='SOLD', order_id=$1 WHERE seat_id=$2 AND status='HELD' AND held_by=$3. A row count of 0 means you lost the race. The database is the source of truth; Redis is only for speed.
• Payment: uses the idempotent payment flow. If payment fails or the hold expires, the seat returns to the pool.
• Read path: the static seat map is served by a CDN, availability is cached for 1–2 seconds, and the response says when it's approximate.

Senior follow-ups

Deep dive

Worked design: a metrics and monitoring pipeline

Collect metrics from 100,000 hosts every 10 seconds, store them, serve dashboards in under a second, and fire alerts within a minute.

Estimates

100k hosts × 500 series × 1 sample / 10 s = 5M samples/s ingest
16 bytes per raw sample → ~7 TB/day raw; compressed TSDB (~1.5 B/sample) ≈ 650 GB/day
keep raw 15 days, 1-min rollups 13 months, 1-hour rollups forever

Architecture

Deep dives

• Ingest: agents batch and compress samples. Kafka absorbs bursts and decouples collection from storage. Partition by series ID so each series is written by one consumer, in order.
• Storage: a time-series DB with delta-of-delta timestamps and XOR float compression (as in Facebook's Gorilla paper). Hot data goes on SSD, old blocks go to object storage. Examples: Prometheus + Thanos/Mimir, VictoriaMetrics, M3.
• Cardinality is the real enemy: one label with user IDs can create millions of series. Enforce limits per tenant at ingest.
• Downsampling: a stream job (Flink) writes 1-minute and 1-hour rollups. Queries choose resolution by time range.
• Alerting: a separate rule evaluator reads from the hot tier, so alerts still work when dashboards are overloaded. Alert on SLO burn rate, and deduplicate and route alerts (Alertmanager to PagerDuty).
• Meta-monitoring: who watches the watcher? A tiny independent system checks that alerting itself is alive.

Senior follow-ups

Deep dive

Migrations & evolving running systems

"How would you get from here to there without downtime?" is the most senior question in software. These are the patterns and their risks.

Expand → migrate → contract

Schema changes on big tables

• Adding a nullable column is usually instant. Adding one with a default, changing a type, or adding an index can lock or rewrite the table.
• Use online tools: gh-ost or pt-online-schema-change (MySQL), and CREATE INDEX CONCURRENTLY (PostgreSQL).
• Renaming a column is a 5-step expand/contract (add new, dual-write, backfill, switch reads, drop old). Never just rename it in place.
• Every migration must work with both the old and new versions of the app running, because deploys are rolling.

Breaking up a monolith (strangler fig)

1. Put a routing layer (gateway or proxy) in front of the monolith.
2. Pick a seam with clear data ownership and high value (for example, notifications). Build the new service.
3. Route that path to the new service. The monolith calls the service through an interface instead of its own module.
4. Move the data: the new service owns its tables, synced through CDC during the transition.
5. Repeat, one seam at a time. Stop when the remaining monolith is healthy. Full decomposition is rarely the goal.

API evolution

• Only make additive changes within a version (new optional fields and endpoints). Clients must ignore unknown fields.
• Breaking change: a new version (/v2), run in parallel, with a deprecation timeline, usage metrics per client, and direct outreach to the biggest consumers.
• In protobuf and Avro, never reuse field numbers, and keep schemas backward and forward compatible (enforce this with a schema registry).

Senior follow-ups

Deep dive

Reliability, capacity planning & cost

Seniors are expected to talk about running a system, not just building it: how reliable it must be, how big it must get, and what it costs.

Reliability targets

• RPO (recovery point objective): how much data you can lose. RTO (recovery time objective): how long you can be down. These drive the replication and backup design.
• SLOs per critical user journey (checkout, login), with error budgets that set the pace of risky releases.
• Failure domains: spread replicas across availability zones. Use multi-region only when the RTO/RPO or latency targets require it, because it multiplies cost and complexity.

Capacity planning in five steps

1. Forecast peak load (growth trend × seasonality × launch events).
2. Measure the capacity of one unit with a load test (for example, one pod handles 800 RPS at p99 under 200 ms).
3. Units needed = peak ÷ per-unit capacity ÷ target utilization (around 60–70%), plus N+1 or N+2 redundancy.
4. Check every downstream dependency: DB connections, cache memory, third-party quotas.
5. Autoscale for daily cycles, and pre-scale for known events.

peak 24k RPS, one pod = 800 RPS at target latency, run at 65% utilization
pods = 24000 / (800 × 0.65) ≈ 46, plus one zone of headroom (3 zones) → ~70 pods
DB: 46 pods × 20 pool connections = 920 > Postgres max_connections (~500) → add PgBouncer

Incident leadership

• Roles: an incident commander (coordinates and decides; doesn't debug), operations leads, a communications lead.
• Order: stabilize and mitigate (roll back, fail over, shed load) → communicate status on a schedule → find the root cause → write the postmortem.
• Blameless postmortem: timeline, impact, contributing factors (usually several), what went well, action items with owners and dates.

Cost awareness

• The biggest wins: rightsizing idle capacity, autoscaling, storage lifecycle policies, caching to cut egress, and commitment discounts for steady load.
• In design rounds, one sentence on cost ("this adds ~$X/month; worth it because…") is a strong senior signal.

Senior follow-ups

Deep dive

Concurrency coding problems

Four problems cover most of what senior loops ask. For each, know the code, the invariant, and the follow-ups.

1 · Thread-safe rate limiter class

import threading, time

class TokenBucket:
    def __init__(self, rate, capacity):
        self.rate, self.cap = rate, capacity
        self.tokens, self.ts = capacity, time.monotonic()   # monotonic: never jumps back
        self.lock = threading.Lock()

    def allow(self) -> bool:
        with self.lock:
            now = time.monotonic()
            self.tokens = min(self.cap, self.tokens + (now - self.ts) * self.rate)
            self.ts = now
            if self.tokens >= 1:
                self.tokens -= 1
                return True
            return False
# follow-ups: per-user buckets (dict + striped locks), distributed (Redis Lua), blocking acquire()

2 · Multithreaded web crawler

from concurrent.futures import ThreadPoolExecutor
from urllib.parse import urlparse

def crawl(start, fetch_links, workers=8):
    host = urlparse(start).netloc
    seen, lock = {start}, threading.Lock()
    with ThreadPoolExecutor(workers) as pool:
        pending = {pool.submit(fetch_links, start)}
        while pending:
            done = next(iter(pending)); pending.remove(done)
            for url in done.result():
                if urlparse(url).netloc != host: continue
                with lock:
                    if url in seen: continue
                    seen.add(url)
                pending.add(pool.submit(fetch_links, url))
    return seen
# follow-ups: politeness (per-host rate limit), robots.txt, depth limit, distributed (queue + Bloom filter)

3 · Delayed task scheduler

import heapq, itertools

class Scheduler:
    def __init__(self):
        self.h, self.cv, self.seq = [], threading.Condition(), itertools.count()
        threading.Thread(target=self._run, daemon=True).start()

    def schedule(self, delay_s, fn):
        with self.cv:
            heapq.heappush(self.h, (time.monotonic() + delay_s, next(self.seq), fn))
            self.cv.notify()                     # an earlier task may now be first

    def _run(self):
        while True:
            with self.cv:
                while not self.h:
                    self.cv.wait()
                due, _, fn = self.h[0]
                wait = due - time.monotonic()
                if wait > 0:
                    self.cv.wait(timeout=wait)   # wake early if a sooner task arrives
                    continue
                heapq.heappop(self.h)
            fn()                                 # run outside the lock

4 · Read-write lock (many readers or one writer)

class RWLock:
    def __init__(self):
        self.cv, self.readers, self.writer, self.waiting_writers = threading.Condition(), 0, False, 0
    def acquire_read(self):
        with self.cv:
            while self.writer or self.waiting_writers:   # writer preference: no starvation
                self.cv.wait()
            self.readers += 1
    def release_read(self):
        with self.cv:
            self.readers -= 1
            if self.readers == 0: self.cv.notify_all()
    def acquire_write(self):
        with self.cv:
            self.waiting_writers += 1
            while self.writer or self.readers: self.cv.wait()
            self.waiting_writers -= 1; self.writer = True
    def release_write(self):
        with self.cv:
            self.writer = False; self.cv.notify_all()

What interviewers listen for

• Always while, never if, around wait(). Never call user code while holding a lock. Lock ordering to avoid deadlock.
• Granularity: one global lock (simple) vs lock striping (scales) vs lock-free structures.
• Testing concurrency: stress tests with many threads, deliberate random sleeps, and invariant checks.

Deep dive

Senior coding: the follow-ups

The first problem is usually a standard Medium. What decides the senior bar is how you handle "now make it work for…".

import random
def reservoir(stream, k):
    sample = []
    for i, x in enumerate(stream, 1):
        if i <= k: sample.append(x)
        else:
            j = random.randint(1, i)
            if j <= k: sample[j - 1] = x      # keep x with probability k/i
    return sample

Code quality at senior bar

• Good names, small helpers, no dead code, guard clauses, and constants instead of magic numbers, all while still finishing on time.
• Write a quick test harness or assert statements for your examples without being asked.
• Discuss production concerns briefly: input validation, error handling, logging.

Senior follow-ups

Deep dive

Code review & debugging rounds

Both rounds simulate the job directly. They reward a systematic method and calm, clear communication.

Code review checklist (in priority order)

1. Does it do what the PR says? Read the description and tests first.
2. Correctness: edge cases (empty, null, large), off-by-one, error paths, races, time zones, float money.
3. Security: injection, missing authorization checks, secrets in code, logging sensitive data, unvalidated input.
4. Reliability: timeouts on network calls, retries without idempotency, swallowed exceptions, resource leaks.
5. Performance: N+1 queries, unbounded memory, missing pagination, work inside loops that could move out.
6. Design: responsibilities, coupling, naming, duplication, testability.
7. Tests: do they cover the change and the failure cases? Would they catch a regression?

Phrasing comments

blocking:   "This builds SQL from user input (line 12). An attacker can read every row.
             Could we use a parameterized query? cursor.execute(sql, (name,))"
suggestion: "This loop queries the DB per order (N+1). A JOIN or a batch fetch would
             make it one query. Fine as a follow-up if this list is always small."
nit:        "Optional: 'data2' could be 'pending_orders' to say what it holds."
praise:     "Nice: the retry wrapper with jitter is exactly right here."

Debugging method

1. Reproduce reliably, with the smallest input or the narrowest scope.
2. Read the error fully: stack trace bottom-up, logs around the timestamp.
3. Hypothesize 2–3 causes, ranked by likelihood × ease of testing.
4. Test cheaply: a print or log, a breakpoint, a unit test, toggling a flag.
5. Bisect: git bisect over commits, commenting out halves of the code, or halving the input.
6. Fix the root cause, add a regression test, and consider where else the same bug pattern exists.

Deep dive

Technical strategy & leadership questions

These questions have no code, but they separate senior from mid-level more clearly than any algorithm.

Frameworks to use out loud

• Impact × effort (and risk) for prioritization. Do quick wins first, plan big bets carefully, and avoid money pits.
• One-way vs two-way doors (Amazon): move fast on reversible decisions, and slow down on irreversible ones (data models, public APIs, vendor lock-in).
• Build vs buy: is it core to your differentiation? Weigh total cost (build + operate + opportunity) against licence + integration + lock-in.
• Design docs / RFCs: problem, goals and non-goals, options with trade-offs, recommendation, rollout, risks. Write first, then get alignment asynchronously.

Tech debt: a model answer

1. Make it visible: list debt items with their cost today (incidents, slow builds,
   days lost per feature) — measured, not felt.
2. Prioritize by impact × effort; tie the top items to business goals
   ("checkout changes take 3× longer because of X").
3. Agree on capacity with product: e.g. ~20% per sprint, plus folding fixes into
   features that touch the same code ("boy-scout rule").
4. Prevent new debt: lint rules, review standards, ADRs for shortcuts with an expiry.
5. Report outcomes: lead time, incident count, build time — before and after.

Common questions

Senior follow-ups

Deep dive

AI engineering interview playbook

"AI engineer" covers several roles. Know which one you're interviewing for, because the rounds differ.

What strong candidates do

• Start from the evaluation: "How will we know it works?" before choosing models or architecture.
• Begin simple (one prompt, one model) and add retrieval, tools or fine-tuning only with a measured reason.
• Quantify: tokens per request, cost per 1k requests, latency budget split (retrieval 150 ms, TTFT 600 ms, streaming…).
• Plan for failure: model timeouts, refusals, invalid JSON, hallucinations, injection, a provider outage.
• Show you've shipped: concrete stories about an eval set you built, a regression you caught, a cost you cut.

Question bank

Deep dive

Transformers & LLM training in depth

You won't be asked to derive back-propagation, but you will be asked to explain what happens inside the model at the level of tokens, attention, layers and training stages.

The pipeline inside one forward pass

1. Tokenize: byte-pair encoding (BPE) splits text into subword pieces from a fixed vocabulary (~50k–200k tokens).
2. Embed: each token ID becomes a learned vector. Position information is added (today usually rotary embeddings, RoPE).
3. Transformer blocks ×N: each block is multi-head self-attention, then a feed-forward network (MLP), with residual connections and layer normalization.
4. Output: the final vector of the last position is projected to vocabulary logits, then sampled.

Training stages

Why LLMs hallucinate

• The model is trained to produce plausible continuations, not to look things up. When it lacks the knowledge, a fluent guess often scores better than "I don't know".
• Mitigations: grounding with retrieval, instructions to abstain, citations checked against sources, lower temperature for factual tasks, and verification steps or tools.

Key numbers

• Attention cost is O(n²) in sequence length, and memory for the KV cache is O(n × layers × hidden size), so long contexts cost real money and latency.
• Parameter memory: 7B at fp16 ≈ 14 GB, 70B ≈ 140 GB. At 4-bit, 70B ≈ 35–40 GB.
• Mixture-of-experts models activate only some parameters per token: lots of knowledge capacity at lower compute per token.

Deep dive

Prompting & structured outputs in depth

Prompting is interface design for a very capable, very literal colleague who has zero context about your situation.

Techniques that reliably help

Prompt operations

• Keep prompts in version control with an ID and version, and log which version produced each output.
• Put long static instructions first so prompt caching can reuse the prefix, and variable content last.
• Every prompt change runs the eval suite before shipping.
• Pin model versions in production, and re-run evals before upgrading.

Deep dive

RAG & retrieval in depth

Retrieval quality caps answer quality. Most RAG improvements come from better chunking, hybrid search, reranking and evaluation, not from a bigger model.

Chunking

• Split on structure (headings, sections, functions in code) before falling back to fixed sizes. Use 10–20% overlap so ideas aren't cut in half.
• Too small, and chunks lack context. Too big, and similarity gets diluted and tokens are wasted. Tune the size with retrieval evals.
• Contextual chunks: prepend a short summary of where the chunk sits ("From the 2025 refund policy, section 3…") before embedding. This improves retrieval noticeably.
• Store metadata (source, date, author, permissions) for filtering and citations.

Retrieval

def rrf(rankings, k=60):                     # reciprocal rank fusion
    score = {}
    for ranking in rankings:                 # e.g. [bm25_ids, vector_ids]
        for rank, doc_id in enumerate(ranking):
            score[doc_id] = score.get(doc_id, 0) + 1 / (k + rank + 1)
    return sorted(score, key=score.get, reverse=True)

Evaluating RAG

Debugging wrong answers

1. Was the right chunk in the corpus at all? If not, it's ingestion.
2. Was it retrieved in the top k? If not, look at chunking, embeddings, hybrid search, or the query.
3. Was it ranked into the prompt? If not, look at reranking and the context budget.
4. Did the model use it correctly? If not, look at the prompt, conflicting chunks, or the model choice.

Deep dive

Agents in depth

Agents trade predictability for flexibility. The engineering is in constraining them: good tools, clear stopping conditions, budgets, and observability.

Patterns, simplest first

Tool design checklist

• A few well-named tools that each do one clear job, rather than dozens of overlapping ones.
• Return what the model needs, compactly (summaries, IDs), with errors that suggest a fix ("no user named 'Jon'; did you mean 'John'?").
• Make actions idempotent where possible, and separate read tools from write tools. Write tools require confirmation or a policy check.

Failure modes and controls

Evaluating agents: measure the final outcome (task success in a sandboxed environment), plus the trajectory (steps, cost, policy violations), over many runs, because results vary run to run.

Deep dive

Evals in depth

Teams that ship reliable AI products are the ones with good evals. In interviews, a thoughtful eval plan is often the deciding signal.

Building the golden set

1. Collect real inputs (logs, support tickets), not ones you invented.
2. Cover slices: common cases, hard cases, edge cases, adversarial inputs, each language, each customer tier.
3. Write the expected outcome or a rubric. Have two people label a sample and check that they agree.
4. Start with 50–100 cases, then grow it with every production failure.

Graders

Process

• Look at actual outputs first (error analysis), group the failures into categories, and only then write graders for those failure modes.
• Run evals in CI on every prompt, model or retrieval change. Track results per slice and block releases on regressions.
• Online: log everything with trace IDs, sample real traffic for review, and A/B test significant changes.

Deep dive

Fine-tuning & adaptation in depth

Fine-tuning is a powerful but slow-moving tool. Reach for it after prompting and RAG plateau on a measured eval.

Doing it right

• Data quality beats quantity: hundreds of excellent examples beat thousands of noisy ones. Deduplicate, and balance the classes.
• Hold out an eval set from the same distribution, and also test general ability for catastrophic forgetting.
• Compare against a strong prompted baseline on the same eval. Fine-tuning has to beat that, not a weak prompt.
• Plan for retraining when the base model or the data changes, and version the datasets and adapters.

Deep dive

Inference, latency & cost in depth

LLM calls are often the slowest and most expensive part of a request. Knowing the levers is a strong senior AI signal.

Latency anatomy

Cost levers, biggest first

1. Model routing: a small, cheap model handles most requests, and hard ones escalate (with a classifier or a confidence check).
2. Prompt caching of the long, static prefix (system prompt, tools, documents).
3. Trim context: fewer, better chunks after reranking, and summarized conversation history.
4. Response caching for repeated questions: exact-match first, semantic caching carefully.
5. Batch APIs for offline jobs (often about half price), and output length limits.

Self-hosting basics

• Throughput comes from continuous batching (new requests join the batch as others finish) and paged KV cache (vLLM, TGI, SGLang, TensorRT-LLM).
• Quantization (int8, int4, FP8) cuts memory and raises speed for a small quality loss, so measure it on your evals.
• Speculative decoding: a small draft model proposes tokens, and the large model verifies several at once.
• Self-hosting only beats APIs at sustained high utilization, or when you need privacy or customization. Include the cost of GPUs and the people to run them.

Deep dive

AI safety & security in depth

The model can't reliably tell your instructions apart from instructions hidden in its inputs. Security comes from the system design around the model.

Threats

The "lethal trifecta" rule of thumb

An agent with access to private data, exposure to untrusted content and a way to communicate externally can be tricked into leaking that data. Remove at least one of the three for any workflow that handles sensitive data.

Deep dive

ML fundamentals refresher

Even LLM-focused roles ask classic ML questions. These are the ones that come up most.

Precision vs recall, interactively

Deep dive

Case study: an AI customer-support assistant

"Design an AI assistant that answers customer questions from our help center and can process simple refunds." This is the most common LLM system design question.

Requirements and numbers

• Answers grounded in about 5,000 help-center articles, with citations. It can look up orders and issue refunds up to $50 with user confirmation, and escalates to a human otherwise.
• 200k conversations a month, about 4 turns each. Target: first token in under 1.5 s, at least 60% resolved without a human, no harmful or unauthorized actions.
• Rough tokens per turn: 2k system + tools (cached), 2k retrieved context, 500 history, 300 output → estimate cost with the calculator in the crash course.

Architecture

Key decisions

• Retrieval: hybrid search over the chunked articles, with contextual chunk headers, plus a reranker, filtered by product and locale.
• Tools: lookup_order (read-only, scoped to the authenticated customer) and issue_refund (the amount is validated in code against order and policy, and the customer must confirm in the UI).
• Routing: a small model classifies intent and urgency, and a stronger model handles complex answers. Escalate to a human on low confidence, an angry user, legal topics, or a repeated failure.
• Guardrails: an input moderation and injection classifier, output checks (citations present, no promises outside policy), and PII redaction in logs.
• Evals: 300 real historical tickets with resolutions, graded for faithfulness, policy compliance and correct escalation. Run on every change, and check weekly samples of production traffic.
• Rollout: internal agents first, then 5% of customers, tracking resolution rate, CSAT, escalation quality and cost per conversation.

Senior follow-ups