Coding Fundamentals

How to approach a coding problem in an interview

A consistent framework matters more than language fluency. For every problem:

1. Restate the problem. "Just to make sure I understand — you want me to..."
2. Ask about constraints. Input size? Memory limits? Are inputs sorted? Can there be duplicates? Empty input?
3. Walk through an example. Pick a small one. Trace it on paper / shared doc.
4. Talk through the brute-force first. Even if you'll discard it. Shows you can think; gives you a fallback.
5. Identify the pattern. Hash map? Two pointers? Sliding window? DFS? (See pattern menu below.)
6. State complexity. "Brute force is O(n²). I think we can do O(n) with a hash map."
7. Code it. Talk while you type. Don't go silent.
8. Test with examples. Walk your code against the example. Find the bug before they do.
9. Discuss tradeoffs. Time, space, edge cases, what you'd add for production.

That sequence applied consistently looks senior. Skipping straight to coding looks junior even when the code is right.

The pattern menu — recognize before solving

This mental checklist is what you actually use in real interviews. Memorize it.

Arrays

The everyday data structure. Python list. Properties:

• Random access: O(1) by index.
• Append: amortized O(1).
• Insert/delete in middle: O(n) — full shift.
• Search: O(n) unsorted, O(log n) sorted (binary search).
• In-place vs copy: "in place" = don't allocate a new array.

Two pointers (sorted array)

Use when you have a sorted array and need to find pairs/triplets meeting a property.

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        if s < target:
            left += 1
        else:
            right -= 1
    return []

Time O(n), space O(1). The "if smaller, move left up; if bigger, move right down" insight only works because the array is sorted.

Sliding window

Use when looking for a contiguous subarray/substring with some property.

def longest_substring_at_most_k_distinct(s, k):
    counts = {}
    left = 0
    best = 0
    for right in range(len(s)):
        counts[s[right]] = counts.get(s[right], 0) + 1
        while len(counts) > k:
            counts[s[left]] -= 1
            if counts[s[left]] == 0:
                del counts[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

Time O(n), space O(k). The window grows by moving right, shrinks by moving left.

Prefix sum

Use when asked about subarray sums, range queries.

def prefix_sums(nums):
    prefix = [0]
    for n in nums:
        prefix.append(prefix[-1] + n)
    return prefix

# Sum of nums[i..j] (inclusive) = prefix[j+1] - prefix[i]

Time O(n) preprocess, O(1) per query. Combined with a hash map, this is the foundation for Subarray Sum Equals K.

Kadane's max subarray

def max_subarray(nums):
    best = current = nums[0]
    for n in nums[1:]:
        current = max(n, current + n)
        best = max(best, current)
    return best

Time O(n), space O(1).

Hash Tables (dicts and sets)

The most useful data structure in interviews. Python dict and set.

• Insert / lookup / delete: average O(1), worst O(n) (collisions; rarely matters).
• Use a dict for key→value mapping.
• Use a set for "have I seen this?".
• collections.Counter: dict subclass for counting; collections.defaultdict(int/list/set) for grouping.

Signals that hash tables solve it

• "Find pairs" → look up complement.
• "Find duplicates" → set membership.
• "Group by" → dict from group → list.
• "Frequency" → Counter.
• "Cache results" → memoize.

Two Sum — the canonical hash-map problem

def two_sum(nums, target):
    seen = {}  # value → index
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []

Time O(n), space O(n). This pattern — "look for the complement in a hash map as you iterate" — appears in dozens of variations.

Counter pattern

from collections import Counter
counts = Counter("anagram")  # Counter({'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1})
counts1 == counts2  # True iff same multiset of chars (anagram check)

defaultdict pattern (grouping)

from collections import defaultdict
groups = defaultdict(list)
for word in words:
    key = ''.join(sorted(word))
    groups[key].append(word)

Group anagrams in one pass. Default value of empty list lets you .append without checking existence.

String Manipulation

In Python, strings are immutable sequences. Common moves:

• Indexing & slicing: s[0], s[-1], s[i:j]. Slicing is O(j-i).
• Concatenation: ''.join(parts) is O(total length); s += t in a loop is O(n²) — never do this.
• Splitting: s.split(), s.split(',').
• Char ↔ ASCII: ord('a') → 97; chr(97) → 'a'.
• Lower/upper: s.lower(), s.upper().

Anagram / palindrome family

• Valid anagram → compare Counters (or sorted strings).
• Palindrome check → two pointers from both ends.
• Longest palindrome substring → expand-around-center, O(n²).

Common string patterns

• Frequency map for anagrams, character counts.
• Sliding window for substring problems with constraints.
• Two pointers for palindromes, reversal in place.
• Vertical scan for prefix problems (Longest Common Prefix).
• Stack for matching brackets, undo operations.

Sorting

You almost never implement a sort in an interview — you call sorted() or list.sort(). But you must know:

• Time: Python uses Timsort, O(n log n) average and worst, O(n) on already-sorted.
• Space: O(n) extra for sorted; O(1) extra-ish for in-place list.sort().
• Stable: yes, Timsort is stable.
• Custom keys: sorted(items, key=lambda x: (x.priority, x.created_at)). Tuple keys give you multi-level sort.

When you'd choose a different sort

Sort-then-X is often the unlock

• Merge intervals: sort by start, then sweep.
• Find duplicates: sort, then look for adjacent duplicates.
• Group anagrams: sort each word's chars, group by key.

If you're stuck, ask: "would sorting first make this easier?" — surprisingly often, yes.

Implement merge sort (if asked)

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Time O(n log n), space O(n). Stable. Comfortable to derive on the fly.

Quicksort is also worth knowing — average O(n log n), worst O(n²) on already-sorted unless randomized; in-place; not stable.

Depth-First Search (DFS)

DFS is for trees and graphs. The shape:

def dfs(node, visited):
    if node is None or node in visited:
        return
    visited.add(node)
    process(node)
    for neighbor in neighbors(node):
        dfs(neighbor, visited)

Recursive vs iterative

Recursive is shorter; iterative (with explicit stack) avoids Python's recursion limit and gives you control.

def dfs_iter(start):
    stack = [start]
    visited = set()
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        process(node)
        for neighbor in neighbors(node):
            if neighbor not in visited:
                stack.append(neighbor)

Trees: pre-order / in-order / post-order

def preorder(node):  # root, left, right
    if not node: return
    visit(node)
    preorder(node.left)
    preorder(node.right)

def inorder(node):   # left, root, right — yields sorted order in a BST
    if not node: return
    inorder(node.left)
    visit(node)
    inorder(node.right)

def postorder(node): # left, right, root — useful for deletion, height
    if not node: return
    postorder(node.left)
    postorder(node.right)
    visit(node)

Common DFS problems

• Number of Islands (count connected components in grid)
• Path Sum (does any root→leaf path equal target?)
• Max Depth of Tree
• Validate BST
• Course Schedule (cycle detection — DFS with three colors)
• All Permutations / Combinations (backtracking is DFS over a state tree)

Backtracking — the DFS variant

def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i, n in enumerate(remaining):
            path.append(n)
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()  # undo
    backtrack([], nums)
    return result

The "do, recurse, undo" shape is the heart of backtracking.

When DFS, when BFS?

• DFS: any-path / all-paths / cycle detection / topological sort / tree traversal.
• BFS: shortest path in unweighted graph / level-order traversal / minimum-step problems.

If they say "shortest" or "fewest steps," default to BFS. Otherwise DFS is usually simpler.

Breadth-First Search (BFS) — the companion

from collections import deque

def bfs(start):
    queue = deque([start])
    visited = {start}
    while queue:
        node = queue.popleft()
        process(node)
        for neighbor in neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Big-O cheat sheet

What every senior candidate states unprompted:

Time complexity classes (sense of speed):

• O(1): constant — instant.
• O(log n): logarithmic — binary search.
• O(n): linear — single pass.
• O(n log n): comparison sort, divide-and-conquer.
• O(n²): nested loops, brute force pairs.
• O(2ⁿ): exponential, brute-force subsets.
• O(n!): factorial, permutations.

Interviewers expect you to state complexity at the end of every solution.

Common Python tools to have at your fingertips

# Iteration
enumerate(items)           # (index, item) pairs
zip(a, b)                  # parallel iteration
reversed(items)            # reverse iterator

# Collections
from collections import Counter, defaultdict, deque, OrderedDict

# Heap (priority queue)
import heapq
heapq.heappush(heap, item)
smallest = heapq.heappop(heap)
heapq.nsmallest(k, items)
heapq.nlargest(k, items)

# Sorting
sorted(items, key=lambda x: x.priority, reverse=True)
items.sort(key=...)        # in-place

# String
s.startswith(prefix)
s.find(needle)             # -1 if not found
'-'.join(parts)
s.split(',')

# Math
abs(x), min(a, b), max(a, b), sum(items)
import math; math.inf, -math.inf

# Set operations
a | b   # union
a & b   # intersection
a - b   # difference

# functools.cache for memoization
from functools import cache
@cache
def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

A clean coding-interview answer template

What to say while you code:

Practiced once, that template gets you through 80% of coding interviews looking composed.

What to drill

The three commonly named — Longest Common Prefix, Valid Anagram, Subarray Sum Equals K — are walked through in 11-coding-problems. Beyond those, drill these LeetCode classics by topic:

• Array: Two Sum, Best Time to Buy/Sell Stock, Maximum Subarray
• Hash table: Group Anagrams, Top K Frequent Elements, Contains Duplicate
• String: Valid Palindrome, Longest Substring Without Repeating Characters, Reverse Words in a String
• Sorting: Merge Intervals, Sort Colors, Kth Largest Element
• DFS: Number of Islands, Path Sum, Validate BST, Clone Graph

Two-three problems per topic, fully solved out loud, is enough.

✓ Check yourself

Answer from memory before opening each one.

1. You must count the contiguous subarrays of a list that sum to k, and the list may hold negative numbers. Which pattern solves it, and why does a sliding window not?

   Show answer

   Prefix sums with a hash map of how often each prefix has appeared; at each position add the count of the prefix equal to the current sum minus k. A window needs the running sum to move one way when you extend or shrink it, and negative numbers break that. See arrays.

2. In the sorted two-sum solution with two pointers, why is it safe to move a pointer, and what does it cost in space?

   Show answer

   If the sum is too small, no pair using the left element and anything at or left of the right pointer can reach the target, so the left pointer moves up; the mirror case moves the right pointer down. That only holds because the array is sorted. It uses constant extra space and one pass. See arrays.

3. You need the ten largest transactions from fifty million streaming records. Full sort or something else, and what are the costs?

   Show answer

   Keep a heap of size ten. Time is proportional to n log k and space to k, whereas a full sort costs n log n time and needs all records in memory. See sorting.

4. Find the fewest hops between two accounts in a transfer graph. DFS or BFS, why, and which data structure mistake slows a BFS?

   Show answer

   BFS, because in an unweighted graph the first time it reaches a node is by a shortest path. Use a deque and popleft; popping from the front of a list costs linear time per pop. See breadth-first search.

5. A loop builds a long string with s += t. What is the cost, and what is the fix?

   Show answer

   Each append copies the string, so the total is quadratic. Collect the pieces in a list and join them once, which costs time proportional to the total length. See string manipulation.

6. Your brute force is quadratic and passes on the interviewer's ten-element example. Do you stop there?

   Show answer

   No. State the brute force and its cost, ask the input size, then name the pattern that beats it. At a hundred thousand elements a quadratic solution fails, and showing the step from brute force to pattern is the point of the exercise. See how to approach a problem.

Takeaway

• Work every problem the same way: restate it, ask about constraints, trace an example, state the brute force, name the pattern, state complexity, code, then test.
• Recognize the pattern from the wording: pairs and counts suggest a hash map, contiguous ranges suggest a window or prefix sums, shortest path suggests BFS, and all paths suggest DFS.
• Two pointers need sorted input, and a sliding window needs a sum that moves in one direction.
• Prefix sums with a hash map solve subarray-sum questions even with negative numbers.
• Sorting first often unlocks a problem, and a heap beats a full sort for top K.
• Know the Python costs: list append is amortized constant, a middle insert is linear, dict and set lookups are constant, string += in a loop is quadratic, and a deque suits queues.
• State time and space at the end of every solution.

The patterns are only useful if you can run them, so the next chapter works eleven problems with several approaches each. → Coding Problems Worked Out

Further reading

• collections: Container datatypes — Python Software Foundation, accessed 2026. Counter, defaultdict and deque, the structures most solutions here use.
• heapq: Heap queue algorithm — Python Software Foundation, accessed 2026. Heap operations and the n-smallest and n-largest helpers.
• Sorting Techniques — Python Software Foundation, accessed 2026. Key functions, stability and multi-level sorts.
• TimeComplexity — Python Wiki, accessed 2026. The cost of operations on built-in types.
• Timsort notes (listsort.txt) — Peters, CPython source, accessed 2026. Why Python's sort is stable and fast on partly ordered data.