IPv4 CIDR Rule Matching

What's being tested

IPv4 CIDR rule matching tests bit-level reasoning, parsing, and choosing the right lookup structure for prefix/range containment. Interviewers probe whether you can implement correctness first, then scale from linear scans to prefix tries, sorted ranges, or bucketed lookups with clear rule-priority semantics.

Patterns & templates

• IPv4 parsing via `ip_to_int(s)` — split four octets, validate 0..255, compute (a<<24)|(b<<16)|(c<<8)|d; use unsigned 32-bit logic.

• CIDR containment with masks — for a.b.c.d/p, mask = (0xffffffff << (32-p)) & 0xffffffff; match when (ip & mask) == (base & mask).

• Range conversion — CIDR block maps to [start, end], where start = base & mask, end = start | (~mask & 0xffffffff); useful for interval search.

• Linear scan baseline — O(R) per query, O(R) space; acceptable if rule count is small or “first matching rule wins” dominates.

• Binary trie for longest-prefix match — insert 32 bits, store rule/action at nodes; query in O(32) time, space O(total prefix bits).

• Priority handling — distinguish first rule wins, last rule wins, and longest prefix wins; store insertion index or best-so-far metadata explicitly.

• Dynamic updates — trie insert/delete is O(32); sorted interval structures need rebalancing and careful overlap handling.

Common pitfalls

Pitfall: Treating IPs as strings causes wrong ordering and containment; always normalize to a 32-bit integer before comparison.

Pitfall: Mishandling /0 and /32; /0 matches everything, while /32 matches exactly one address.

Pitfall: Optimizing before clarifying semantics; “first CIDR block covering IP” and “longest-prefix firewall rule” require different lookup behavior.

Practice these

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