IP Prefix - Match Requests Against CIDR Allowlist

Question

## Problem

You are building a firewall rule engine. Given a list of CIDR blocks (e.g., `"192.168.1.0/24"`) and an incoming IP address string, determine whether the IP is covered by any CIDR in the list.

```python
class Firewall:
    def __init__(self, cidrs: list[str]): ...
    def is_allowed(self, ip: str) -> bool:
```

A CIDR `A.B.C.D/N` covers all IPs whose first `N` bits match those of `A.B.C.D`.

## Example

```
fw = Firewall(["10.0.0.0/8", "192.168.1.0/24"])
fw.is_allowed("10.5.3.1")      -> True
fw.is_allowed("192.168.1.200") -> True
fw.is_allowed("192.168.2.1")   -> False
fw.is_allowed("172.16.0.1")    -> False
```

Do not use any networking library -- implement the bit-masking yourself.

## Follow-ups

1. How would you use a trie to make `is_allowed` faster for large allowlists?
2. Add a `add_cidr(cidr)` and `remove_cidr(cidr)` method. How do you handle overlapping ranges?
3. What is the worst-case complexity of the naive approach vs. trie approach?
4. Extend to support both an allowlist and a denylist, where deny takes precedence.

IP Prefix - Match Requests Against CIDR Allowlist

Question Details

Full Details

Topics

More from Google