Appendix: Practice problems

Seventeen short problems of the kind you meet in coding interviews and programming challenges. Each one gives a statement, examples, a hint, and a solution with its complexity and tests. Try each problem before you read the hint, and the hint before the solution. The solutions favour clear, idiomatic Python over tricks; where a library function does the job, they use it and say what it does underneath.

Complexity describes how the cost of an algorithm grows with the size n of its input. O(n) time means the work grows in proportion to n; O(1) space means the extra memory stays the same however large the input is. "Average" marks costs that hold on average, such as dictionary and set lookups, which can degrade in rare cases.

You will be able to:

• Recognise the standard techniques: hashing, two pointers, running totals, binary search, divide and conquer, and dynamic programming
• State the time and space complexity of your solution and explain why
• Test a solution with edge cases: empty input, duplicates, a single item, large input

1. Pair with a target sum

Problem. Given a list of integers and a target, return the positions (i, j) with i < j of two entries that add up to the target, or None if there are none. If several pairs work, return the one whose second position j is smallest, and among those the smallest i.

Examples. [4, 9, 1, 6] with target 7 gives (2, 3), because 1 + 6 = 7. [5, 5] with target 10 gives (0, 1). [1, 2] with target 7 gives None.

Hint. Checking every pair is O(n²). Instead, scan once and remember where you saw each value: at position j, the partner you need is target - numbers[j].

Complexity. O(n) time on average and O(n) space for the dictionary. Looking up the partner before storing the current value stops an entry from pairing with itself.

2. Rotate a list

Problem. Rotate a list to the right by k places, in place: every item moves k positions towards the end, and items that fall off the end reappear at the front. k can be larger than the list. An empty list stays empty.

Examples. [1, 2, 3, 4, 5] rotated by 2 becomes [4, 5, 1, 2, 3]. Rotating by 7 gives the same result, and rotating by 0 or 5 changes nothing.

Hint. Only k % len(items) matters. Slice assignment, items[:] = ..., replaces the contents of the same list object, so every other name for that list sees the change.

Complexity. Both are O(n) time. The slice version builds a temporary list, so it uses O(n) extra space; the three reversal version uses O(1). Rotating by 0 works in the slice version because items[-0:] is the whole list and items[:-0] is empty. In real code, collections.deque has a rotate() method.

3. Any duplicates?

Problem. Return True if any value occurs more than once in a list, otherwise False. Do not change the list.

Examples. [3, 1, 4, 1] gives True; [3, 1, 4] gives False; [] gives False.

Hint. A set answers "have I seen this before?" in constant time on average.

Complexity. O(n) time on average and O(n) space; the loop stops at the first repeat. Sorting and then comparing neighbours takes O(n log n), and calling items.sort() would reorder the caller's list, a side effect nobody asked for.

4. The lone number

Problem. In a nonempty list of integers every value appears exactly twice, except one value that appears once. Find it in linear time using constant extra memory.

Examples. [7, 3, 7] gives 3; [2, 9, 4, 9, 2] gives 4; [-5] gives -5.

Hint. Exclusive or (^) has three useful properties: x ^ x == 0, x ^ 0 == x, and the order of the operations does not matter.

Complexity. O(n) time and O(1) space. Every pair cancels to 0, leaving the lone value. A Counter also works, but it needs O(n) memory, which the problem rules out.

5. Common items, with repeats

Problem. Given two lists, return the values they have in common, each repeated as many times as it appears in both lists (the smaller of its two counts). List the values in the order they first appear in the first list.

Examples. [3, 1, 3, 2, 3] and [3, 3, 4, 1] give [3, 3, 1]. [1, 2] and [3] give [].

Hint. The & operator on two Counter objects keeps each value with the smaller of its two counts.

Complexity. O(n + m) time on average and O(n + m) space. & walks the first counter in insertion order, and elements() repeats each value by its count, which together give the required order. Calling second.count(value) for each value instead would make it O(n·m).

6. Add one to a digit list

Problem. A nonnegative integer is stored as a list of decimal digits, most significant first, with no leading zeros (zero itself is [0]). Return a new list holding the number plus one. Do not convert the digits to an int.

Examples. [4, 0, 9] gives [4, 1, 0]; [9, 9] gives [1, 0, 0]; [0] gives [1].

Hint. Work from the right. A digit below 9 goes up by one and you are done; a 9 becomes 0 and the one carries left.

Complexity. O(n) time in the worst case (all nines), and O(n) space for the copy. Converting with int("".join(...)) defeats the exercise and also fails for long inputs: by default, CPython refuses to convert a string of more than 4,300 digits to an int, as a safeguard against very slow conversions.

7. Move zeros to the end

Problem. Move every 0 in a list of integers to the end, in place, keeping the other values in their original order.

Examples. [0, 4, 0, 2, 7] becomes [4, 2, 7, 0, 0]. [1, 2] and [0, 0] stay as they are.

Hint. Keep a write position: copy each nonzero value to it and move it on, then fill the rest with zeros.

Complexity. O(n) time and O(1) extra space. The write position never overtakes the read position, so no value is overwritten before it has been read. If you do not need to work in place, [v for v in numbers if v != 0] + [0] * numbers.count(0) is shorter.

8. Validate a sudoku grid

Problem. A sudoku grid is 9 rows of 9 characters, each a digit from "1" to "9" or "." for an empty cell. The grid is valid if no digit repeats within a row, a column, or one of the nine 3×3 boxes. Empty cells are ignored, and a valid grid does not have to be solvable.

Examples. The grid in the block below is valid. Adding a second 5 to its first row, a second 2 to its last column, or a second 8 to its bottom left box makes it invalid.

Hint. Give each filled cell three keys, one each for its row, column and box. Cell (r, c) lies in box (r // 3, c // 3). A repeated key means a repeated digit.

Complexity. The grid has a fixed 81 cells, so this is O(1). For an n×n puzzle it is O(n²) time and space, one visit per cell. Each invalid test changes one cell so that exactly one rule breaks, which proves that each of the three checks works on its own.

9. Climbing stairs

Problem. You climb a staircase of n steps, taking either 1 or 2 steps at a time. In how many different sequences of moves can you reach the top? For n = 0 there is exactly one way: do nothing.

Examples. n = 1 gives 1; n = 3 gives 3 (1+1+1, 1+2, 2+1); n = 4 gives 5; n = 10 gives 89.

Hint. Your last move was either 1 step or 2, so ways(n) = ways(n - 1) + ways(n - 2). Build up from the bottom instead of recursing from the top.

Complexity. O(n) time and O(1) space. This is dynamic programming: you solve small cases once and build larger answers from them. The counts are the Fibonacci numbers shifted by one. A naive recursive version without a cache repeats the same work exponentially often; adding @functools.cache fixes that but keeps O(n) recursion depth.

10. Buying and selling

Problem. You know a share's price for each of the coming days.

• (a) One trade. Buy on one day and sell on a later day. Return the largest possible profit, or 0 if no trade makes money.
• (b) Many trades. You may hold at most one share at a time, but you can buy and sell as often as you like, including selling and buying again on the same day. Return the largest total profit.

Examples. For prices [8, 3, 6, 1, 5], (a) gives 4 (buy at 1, sell at 5) and (b) gives 7 (3 to 6, then 1 to 5). For [9, 7, 4] both give 0.

Hint. (a) Keep the lowest price seen so far and ask what selling today would earn. (b) Any profitable holding period's gain is the sum of its day to day changes, so collect every rise and skip every fall.

Complexity. Both are O(n) time and O(1) space. In (a), the order of the two updates matters: updating lowest first means a price can only be compared with an earlier or equal day, never a later one. itertools.pairwise (since 3.10) yields each pair of neighbouring days.

11. Roman numerals

Problem. Convert a Roman numeral to an integer. The symbols are I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000. Values normally add up from largest to smallest, but a symbol written directly before a larger one is subtracted: IV = 4, XC = 90, CM = 900. Assume a correctly written numeral; raise ValueError for an empty string or an unknown character.

Examples. "XII" gives 12; "CDXLIV" gives 444; "MMXXVI" gives 2026.

Hint. Compare each symbol's value with the value of the symbol after it.

Complexity. O(n) time and O(n) space for the list of values. This converts correct numerals; it does not reject malformed ones such as "IIII" or "IC". A simple validity check is to convert the result back to a numeral and compare.

12. Binary search

Problem. Given a list sorted in ascending order and a target, return the position of the first occurrence of the target, or -1 if it is absent. The function must not sort or change the list: being sorted is a precondition, something the caller guarantees.

Examples. In [2, 4, 4, 4, 9], target 4 gives 1, target 9 gives 4 and target 5 gives -1. An empty list gives -1.

Hint. bisect.bisect_left(items, target) returns the leftmost position where target could be inserted while keeping the list sorted. The target is present exactly when that position holds it.

Complexity. O(log n) time and O(1) space: each step halves the range that can hold the answer. The precondition is what makes this possible. A search function that sorts its input first costs O(n log n), reorders the caller's list, and returns a position in the sorted order rather than the original one. The seeded random test compares both versions with list.index on 200 lists.

13. Quicksort

Problem. Implement quicksort, returning a new sorted list. Choose each pivot at random so that already sorted input does not trigger the worst case, and make sure a list with many equal values still sorts quickly.

Examples. [3, 1, 2] gives [1, 2, 3], and [5, 1, 5, 2, 5] gives [1, 2, 5, 5, 5]. An empty list gives an empty list. The list you pass in is left unchanged.

Hint. Split the items into three groups: less than the pivot, equal to it, and greater. Sort the outer two recursively; the middle group is already in place.

Complexity. O(n log n) time on average and O(n²) in the worst case, which a random pivot makes vanishingly unlikely. The three way split matters too: 5,000 equal values finish in one step. A simpler version that always takes the first item as pivot recurses once per item on already sorted input (and, with some partition schemes, on many equal values), so it hits Python's default recursion limit of 1,000 levels on lists of only a little over a thousand items. This version builds new lists, so it uses O(n) extra memory. In real code, call sorted() or list.sort(): they are implemented in C, stable, and O(n log n) in the worst case.

14. Run length encoding

Problem. Compress a string by replacing each run of a repeated character with the character followed by the length of the run, and write the matching decoder. The input contains no digits, which keeps the encoding unambiguous; reject a digit with ValueError.

Examples. "wwwxyyzzzz" encodes to "w3x1y2z4". "aab" encodes to "a2b1". The empty string encodes to "".

Hint. itertools.groupby yields each run of equal consecutive items as a key and an iterator over the run.

Complexity. O(n) time for both functions, and O(n) space for the output. sum(1 for _ in run) counts a run without building a list. The round trip test, decoding what you encoded, is a cheap and powerful check for any pair of inverse functions. Runs of ten or more are the case a handwritten decoder most often gets wrong, so the tests include them.

15. Second largest

Problem. Return the second largest distinct value in a list using one pass, or None if there are fewer than two distinct values. Then explain why no algorithm can do better than O(n).

Examples. [4, 9, 2, 9, 7] gives 7; [5, 5] and [3] give None; [-1, -3] gives -3.

Hint. Track the largest and second largest values seen so far, and decide where each new value fits.

Complexity. O(n) time and O(1) space, and that is optimal: any value you skip could have been the answer, so every algorithm must read all n values. Sorting first costs O(n log n), not O(log n). heapq.nlargest(2, set(numbers)) is a reasonable one liner, at the cost of building a set.

16. Prefix suggestions

Problem. A shop has a catalogue of product names in lower case. As a customer types a search term, after each character show up to three catalogue names that start with what has been typed so far, in alphabetical order. Return one list of suggestions per character typed. Ignore the case of the search term.

Examples. With the catalogue lamp, laptop, lantern, ladder, label, lemon and the search term "lap", the result is [["label", "ladder", "lamp"], ["label", "ladder", "lamp"], ["laptop"]]. With the catalogue lemon, mop and the term "mo", the result is [["mop"], ["mop"]]: "lemon" contains "mo" but does not start with it.

Hint. Sort the catalogue once. All names with a given prefix then sit next to each other, starting at the position bisect_left returns for the prefix.

Complexity. O(n log n) to sort, then O(log n) per typed character to find the start, plus the cost of comparing at most three names. Three mistakes are easy to make here: matching anywhere in the name (prefix in name) instead of at the start, taking the first three matches before sorting them, and sorting only when there are more than three matches. Each one passes some examples and fails others, which is why the tests include "lemon".

17. Ordered motifs

Problem. A song is a list of notes, and a pattern is a list of motifs, each a short list of notes in which "*" stands for exactly one note of any kind. A song contains the pattern if the motifs appear in the song in the given order, each as a run of consecutive notes, without overlapping one another. Any number of notes, including none, may come between two motifs. An empty pattern is contained in every song.

Examples. Take the pattern [["C", "E"], ["G", "*", "G"]].

• D C E A G B G contains it: C E at positions 1 to 2, then G B G at 4 to 6.
• C E G E G contains it: the motifs may touch.
• G A G C E does not: the motifs appear in the wrong order.
• C E G G does not: "*" must match exactly one note.

With the pattern [["C", "C"], ["C", "C", "D"]], the song C C C D does not contain it, because the second motif would have to reuse a note of the first.

Hint. Use two pointers: one for your position in the song and one for the current motif. Find the earliest place where the motif fits, then continue searching after it. Taking the earliest match is always safe, because it leaves the most room for the motifs that follow.

Complexity. O(n·m) time, where n is the length of the song and m the length of the longest motif, because each starting position compares up to m notes; O(m) extra space for the window. A tempting alternative joins the notes into one string and builds a regular expression from the pattern. It is easy to get wrong: without word boundaries, a motif can match part of a longer note name, special characters in note names must go through re.escape, and a careless .* between groups can backtrack badly on long input (Regular expressions). Working on the list directly avoids all three.