IP firewall with CIDR rules: A Sample Coding Interview Solution

The coding question

You get a list of firewall rules. Each one is ALLOW or DENY with a CIDR block like 192.168.1.0/24, and the first rule that matches wins. Write a function that says whether an IP is allowed. Then say whether every address in a given CIDR block is allowed.

Ask a few questions first

Ask	What we'll assume
IPv4 only?	Yes, dotted addresses like 10.1.2.3.
What if no rule matches?	Deny. That's the usual default for a firewall.
What does the /24 mean?	The first 24 bits are fixed and the last 8 can be anything, so it covers 256 addresses.
Can a rule's address have host bits set, like 192.168.1.77/24?	Treat it as the block it falls in, so 192.168.1.0/24.
How many rules, and how many lookups?	Up to a few thousand rules. Lots of lookups, so set the rules up once.

A couple of examples

Input	Output
Rules: DENY 192.168.1.128/25, ALLOW 192.168.1.0/24, ALLOW 10.0.0.0/8. is_allowed("192.168.1.10")	True
Same rules. is_allowed("192.168.1.200"), is_allowed("8.8.8.8")	False (the DENY matches first), False (nothing matches)
Same rules. is_block_allowed on 192.168.1.0/25, 192.168.1.0/24, 10.20.0.0/16	True, False, True

Start with brute force

For one IP, walk the rules in order and return the first one that matches. That part is already fine. For a block, check every address in it one at a time.

Cost: A single IP is O(r) for r rules. A block of size m is O(m × r), and a /8 has about 16 million addresses. 0.0.0.0/0 has over 4 billion.

A better way

Turn everything into numbers. An IPv4 address is just a 32-bit integer, 8 bits per part. A CIDR block is a range: clear the last 32 - prefix bits to get the first address, and the block has 2^(32 - prefix) addresses in a row.

Now matching an IP is a range check, lo <= ip <= hi, and the first match wins.

For a whole block, think in ranges too. Keep a list of the parts of the block that no rule has decided yet. Go through the rules in order. If a DENY overlaps any undecided part, some address gets denied, so the answer is no. If an ALLOW overlaps, those addresses are decided as allowed, so cut them out. If you run out of undecided parts, every address was allowed. If rules run out first, the leftovers hit the default deny.

Write ip_to_int: split on dots, check there are four numbers from 0 to 255, and build the integer.
Write cidr_to_range: mask off the host bits to get the first address, and add the block size minus 1 for the last.
Turn every rule into (allow?, first, last) once, up front.
is_allowed walks the rules and returns the action of the first range that holds the IP, or False.
is_block_allowed starts with the block as one undecided range and walks the rules, failing on any DENY overlap and cutting out any ALLOW overlap.

The code

solution.pypython

def ip_to_int(ip):
    parts = ip.split(".")
    if len(parts) != 4:
        raise ValueError("bad IP: " + ip)
    n = 0
    for p in parts:
        if not p.isdigit() or int(p) > 255:
            raise ValueError("bad IP: " + ip)
        n = n * 256 + int(p)
    return n


def cidr_to_range(cidr):
    # "10.0.0.0/8" -> (first, last) address as numbers, both included
    ip, _, bits = cidr.partition("/")
    prefix = int(bits) if bits else 32
    if not 0 <= prefix <= 32:
        raise ValueError("bad prefix: " + cidr)
    size = 1 << (32 - prefix)
    first = ip_to_int(ip) & ~(size - 1)  # clear the host bits
    return first, first + size - 1


class Firewall:
    def __init__(self, rules):
        # rules: list of (action, cidr), checked in order
        self.rules = [(action == "ALLOW", cidr_to_range(cidr)) for action, cidr in rules]

    def is_allowed(self, ip):
        n = ip_to_int(ip)
        for allow, (lo, hi) in self.rules:
            if lo <= n <= hi:
                return allow
        return False  # nothing matched, so deny by default

    def is_block_allowed(self, cidr):
        # Ranges no earlier rule has decided yet. Starts as the whole block.
        open_ranges = [cidr_to_range(cidr)]
        for allow, (lo, hi) in self.rules:
            remaining = []
            for a, b in open_ranges:
                if b < lo or a > hi:
                    remaining.append((a, b))  # this rule doesn't touch it
                    continue
                if not allow:
                    return False  # some undecided address hits a DENY
                # ALLOW decides the overlap. Keep the bits on either side.
                if a < lo:
                    remaining.append((a, lo - 1))
                if b > hi:
                    remaining.append((hi + 1, b))
            open_ranges = remaining
            if not open_ranges:
                return True  # every address was allowed by some rule
        return False  # some addresses matched nothing, so they're denied

	Cost	Why
is_allowed	O(r)	One range check per rule
is_block_allowed	O(r²) worst case	Each ALLOW can split one range into two, so the undecided list grows by at most one per rule. Usually it stays tiny
Memory	O(r)	The parsed rules and the undecided ranges

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

No rules at all, so everything's denied.
A /32, which is a single address, and a /0, which is every address.
A rule written with host bits set, like 192.168.1.77/24.
A block that's only partly covered by ALLOW rules, with the rest matching nothing.
A DENY that comes after an ALLOW for the same addresses, so it never matters.
Bad input like 1.2.3, 1.2.3.256 or /33, which should raise an error.

Common mistakes

Comparing IPs as strings, where "10.0.0.9" sorts after "10.0.0.10".
Forgetting to mask the host bits, so a rule like 192.168.1.77/24 starts in the wrong place.
For blocks, checking only whether the first DENY or ALLOW overlaps, and ignoring that an earlier ALLOW may already have decided those addresses.
Forgetting the default deny for the parts of a block that no rule covers.

Follow-up questions

Lookups are too slow with 100,000 rules. What now?

Build a binary trie on the address bits. Each rule sits at the node for its prefix with its position in the list. Walk the IP's bits down the trie, at most 32 steps, and keep the matching rule with the smallest position.

What about IPv6?

Same idea with 128-bit numbers. Python's integers handle that fine, and the trie just gets deeper.

Can you simplify the rule list?

Drop any rule whose whole range is already decided by earlier rules, using the same undecided-ranges trick. Then merge neighboring blocks with the same action.

How the time adds up

Minutes	What you're doing
0–5	Ask questions and agree on examples
5–10	Talk through the brute force
10–20	Find the better approach
20–35	Write the code
35–40	Test it out loud
40–45	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Databricks.