Combining structures

How do you choose an approach?

Choosing an approach means connecting the problem’s required operations to the structures and algorithms you have learned. Start with the input, the requested output, and the constraints. Build a simple correct solution, identify its expensive work, and look for a structure that avoids repeating it.

Example: If a solution repeatedly scans earlier values to ask “have I seen this before?”, consider a set. If it repeatedly sums fixed ranges in unchanged data, consider prefix sums. Explain why the chosen approach fits before writing code.

Understand the idea

Combined structures should have separate responsibilities and a shared consistency rule. A map locates state, a list orders it, a heap prioritizes it, and a graph represents transitions. Add only what the workload requires.

Work through an example

An LRU cache uses map+linked list; streaming median uses two heaps; target-sum counting uses prefix+frequency map. Each component contributes something the other lacks.

Time and space complexity

Analyze each operation across all components; include output and storage costs.

Why it works

All views agree after every update: cached keys match list nodes; prefix frequencies describe earlier boundaries.

Common mistakes

Redundant structures add synchronization bugs.
A stale heap entry needs a deliberate validity check.

Chapter lab · Python implementation

Interview readiness means selecting an approach without a chapter label. The lab compares an obvious quadratic subarray-sum baseline with prefix hashing on exhaustive small inputs. Work from a contract, articulate why the optimized state is sufficient, then use counterexamples and delayed review to expose fragile reasoning.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

from itertools import product

def brute_count(values,target):
    count=0
    for left in range(len(values)):
        total=0
        for right in range(left,len(values)):
            total+=values[right]
            count+=total==target
    return count

def fast_count(values,target):
    frequencies={0:1}; prefix=answer=0
    for x in values:
        prefix+=x
        answer+=frequencies.get(prefix-target,0)
        frequencies[prefix]=frequencies.get(prefix,0)+1
    return answer

def verify_small():
    cases=0
    for length in range(5):
        for values in product([-1,0,1],repeat=length):
            for target in range(-2,3):
                assert brute_count(values,target)==fast_count(values,target)
                cases+=1
    return cases

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert verify_small()==605
assert fast_count([1,-1,1],1)==3
assert brute_count([],0)==0

CHECK YOUR UNDERSTANDING