DSA: problem contracts and complexity

Start before the cluster

Data structures and algorithms (DSA) help you reason about automation as its inputs grow. System design then asks how that automation behaves across processes, storage, and failures. This opening module bridges the Python work in DevOps Foundations and the Kubernetes operations that follow.

Use Python 3.11 or later and its standard library. No running containers, cloud account, extra packages, or new VM are needed for the algorithm exercises. From your MicroBank checkout, create .local/advanced-design/ and keep the exercise files there. Retain the existing ignore rule for .local/.

For each problem, write the input, output, invalid-input policy, ordering rules, and resource limits before choosing an algorithm. Include empty files, repeated events, and equal timestamps in that contract from the start.

Count work and retained data

Let n be the number of records and u the number of distinct event types. Big-O describes growth under a stated model, not elapsed seconds on your laptop. Expected, worst-case, and amortized bounds answer different questions.

Save this small exercise as complexity.py:

def unique_in_order(values):
    seen = set()
    result = []
    for value in values:
        if value not in seen:
            seen.add(value)
            result.append(value)
    return result


assert unique_in_order(["ledger", "accounts", "ledger"]) == ["ledger", "accounts"]
assert unique_in_order([]) == []

For hashable, bounded-size keys, this makes one pass with expected O(n) work and O(u) retained data. Using value not in result instead can require quadratic comparisons when most values are distinct. Reading a file line by line avoids retaining all lines, but an ever-growing seen set can still exhaust memory.

Trace the structures before timing them

For ['ledger', 'accounts', 'ledger'], the first value is absent from seen, so add it to both seen and result. The second is new too. The third is already in seen, so neither structure grows. seen answers membership; result keeps first-appearance order. The invariant is: after each input, the result contains exactly the distinct values seen so far, in that order.

From .local/advanced-design/, run python3 complexity.py. Success produces no output because the assertions did not fail. Then try unique_in_order([[1]]) in a separate scratch test. A list is unhashable, so a TypeError is expected. The function's contract accepts hashable values; converting arbitrary nested data to a key needs an explicit policy, not an accidental catch-all exception.

Practise and explain

Compare list membership and set membership on labelled synthetic inputs with increasing sizes. Check that both produce the same answer before timing them. Record input sizes and repeated timings. Use the timings to explore the behavior, and the algorithm’s operations to explain its complexity.

Interview formats vary by role and employer. Ask for the actual assessment format and permitted language. This module is an operations-oriented starting point, not a claim about which questions a company will ask. Trees, weighted shortest paths, and dynamic programming remain useful further study when your goals require them.

Checkpoint and revision

Explain why ordered output and membership lookup use different structures here. State the key-size assumption and the memory bound. Reimplement the function without looking, then test empty input, repeated values, and unhashable input; decide whether rejection of the last case matches your contract.

Checkpoint answer: the set speeds membership while the list preserves output order. A million distinct values can still require roughly a million retained keys; streaming the input does not remove that state. Keep this distinction when the next bite separates delivery counts from distinct business events.

Sources

MIT 6.006: introduction and algorithm reasoning↗, Python data structures↗, and MIT hashing notes↗.