Python Coding Challenges

Before writing code, answer every question the problem statement leaves open. For "return the characters that appear more than once in a badge text":

• Are upper- and lower-case letters the same character?
• Do spaces and punctuation count?
• What order should results be in, and should each character appear once?
• What happens for an empty string?

Write the decisions down as a docstring:

def repeated_symbols(text):
    """Return each character that appears more than once in text,
    case-sensitive, spaces included, sorted, each listed once.
    An empty string returns []."""

Ambiguous rules make correctness impossible to judge: two people can write "correct" solutions that disagree. In an interview, asking these questions out loud is part of what's being assessed. On practice sites, the examples usually settle them, so read every example before coding.

Good tests cover three kinds of input:

• Ordinary: a typical case from the problem statement.
• Boundaries: empty input, one element, everything identical, the largest allowed size.
• Adversarial: cases designed to break a tempting shortcut.

For balanced brackets, the tempting shortcut is "count opening and closing brackets and check the counts match". The adversarial test ")(" has matching counts but isn't balanced, and "([)]" has every pair present but in the wrong nesting order:

cases = {
    "": True, "()": True, "([]{})": True,       # ordinary and boundary
    ")(": False, "([)]": False, "((": False,    # adversarial
}

Write these before the solution, so you're testing the specification, not the code you happened to write. Then a failing case tells you precisely which part of the reasoning is wrong.

Start with the clearest solution you're confident is correct, verify it against the tests, and only then optimise if the constraints require it. For merging overlapping intervals:

def merge(intervals):
    merged = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Sorting first is the key insight: once intervals are ordered by start time, each one can only overlap the most recent merged interval. That turns an O(n²) "compare everything with everything" approach into O(n log n).

Optimising before the contract and tests are clear causes avoidable mistakes, such as treating [9, 11] and [11, 12] as overlapping or not. Decide that in the contract first (here, touching intervals merge because the comparison is <=), then write code that follows it.

A finished solution includes a short explanation of why it's correct and what it costs. For repeated characters with a dictionary:

• Invariant: after processing the first i characters, counts[c] equals the number of times c appears among them.
• Correctness: at the end, the invariant covers the whole string, so filtering counts above 1 gives exactly the repeated characters.
• Cost: O(n) time for one pass, plus O(k log k) to sort the k distinct characters; O(k) extra space.

An invariant is a statement that's true before the loop, stays true after each iteration, and gives the answer when the loop ends. For balanced brackets the invariant is "the stack holds exactly the opening brackets not yet closed, in order". Passing the examples shows the code works on those inputs; the invariant explains why it works on all of them.

Task: solve repeated symbols, balanced brackets, merged intervals and shortest unweighted routes, documenting contracts and costs. Use this harness to test your own versions:

def check(func, cases):
    failures = [(given, expected, func(*given)) for given, expected in cases
                if func(*given) != expected]
    for given, expected, got in failures:
        print(f"FAIL {func.__name__}{given}: expected {expected}, got {got}")
    print(f"{func.__name__}: {len(cases) - len(failures)}/{len(cases)} passed")

def repeated_symbols(text):
    counts = {}
    for ch in text:
        counts[ch] = counts.get(ch, 0) + 1
    return sorted(ch for ch, n in counts.items() if n > 1)

check(repeated_symbols, [(("",), []), (("abc",), []), (("aAa",), ["a"]), (("a a",), ["a"])])

This prints repeated_symbols: 4/4 passed. Note that "a a" contains one space, so only "a" repeats. Write each function's contract and complexity in its docstring. For the worked check, a challenge should include boundary and adversarial cases besides an ordinary example.

The collections and bisect modules provide building blocks used in many challenge solutions. Continue with practice problems and revisit interview questions and complexity. Practise with the Python exercises and Python quiz.