Coding Interview Concepts

Skeleton code for three patterns

Here are the three basic patterns in a few lines each. Notice that every one of them walks the input only once.

Two pointers on a sorted array, checking whether two numbers add up to the target. If the sum is too small, move the left pointer; if it is too large, move the right one.

def has_pair_with_sum(sorted_nums: list[int], target: int) -> bool:
    lo, hi = 0, len(sorted_nums) - 1
    while lo < hi:
        total = sorted_nums[lo] + sorted_nums[hi]
        if total == target:
            return True
        if total < target:
            lo += 1
        else:
            hi -= 1
    return False


print(has_pair_with_sum([1, 3, 4, 6, 9], 10))  # True (1 + 9)
print(has_pair_with_sum([1, 3, 4, 6, 9], 2))   # False

A fixed-size sliding window that finds the largest sum of k consecutive elements. Each time the window slides by one, add the value coming in and subtract the value going out.

def max_window_sum(nums: list[int], k: int) -> int:
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]
        best = max(best, window)
    return best


print(max_window_sum([2, 1, 5, 1, 3, 2], 3))  # 9 (5 + 1 + 3)

A hash set that finds the first value to appear twice. Membership tests are O(n) on a list but O(1) on average for a set.

def first_repeat(items: list[str]) -> str | None:
    seen: set[str] = set()
    for item in items:
        if item in seen:
            return item
        seen.add(item)
    return None


print(first_repeat(["a", "b", "c", "b", "a"]))  # b

Vocabulary

• Brute force: the simplest solution that tries every possibility. Slow, but a great reference answer for testing.
• Edge case: an input where bugs like to hide, such as an empty input, a single element, all-equal values or numbers near the limits.
• Time and space complexity: how running time and extra memory grow as the input size n grows.
• Invariant: a property that stays true on every iteration of a loop, for example "the window contains no repeated character".
• Trade-off: a deliberate choice, such as spending memory to save time or giving up a little speed for simpler code.

Summary

Coding interviews grade understanding, problem solving, code quality, verification and communication alongside correctness. Practice spotting the clues that point to hash maps, two pointers and sliding windows, and build the habit of thinking out loud: with the same skills, you will come across far better. The next chapter walks through solving one problem from start to finish.