CIDR IPv4 Firewall Matching

What's being tested

Candidates must demonstrate precise IPv4/CIDR arithmetic and set reasoning: convert between dotted quad and 32-bit integers, compute CIDR start/end, and test containment or overlap. Interviewers also probe algorithmic design for ordered first‑match firewall semantics and scalable lookup/update structures that keep matching low‑latency.

Patterns & templates

• Convert dotted-quad ↔ 32-bit with `ip_to_int` / `int_to_ip` and apply masks via (ip & mask) == (prefix & mask) for prefix containment.

• Represent a CIDR as a closed integer interval [start, end] using start = prefix & mask, end = start | (~mask & 0xFFFFFFFF).

• Prefix containment = single mask equality; overlap = interval intersection check with O(1) bit ops.

• Subtracting one CIDR from another: split into at most two smaller CIDRs using bitwise prefix shrink; repeated subtraction is interval-set difference.

• Ordered first-match firewall: evaluate rules sequentially until a match; for block queries, require full coverage of the block by an allowed rule (or absence of earlier deny).

• Use a prefix trie / binary radix tree for O(W) lookup where W ≤ 32; for N large, compress to a Patricia/radix trie to reduce memory and hops.

Tip: store rules at trie nodes with priority index to resolve first-match without linear scan.

Common pitfalls

Pitfall: confusing network vs broadcast addresses — treat CIDR ranges as inclusive [start, end] using 32-bit arithmetic.

Pitfall: assuming disjoint CIDRs — overlapping rules with ordering change semantics; always respect rule index priority.

Pitfall: using string parsing (regex) in hot path — convert once to ints/masks; runtime must be bitwise, not text-based.

Practice these

the practice cards below cover the canonical variants — solve all of them and time yourself