First-Match CIDR Firewall: Status of an IP Address or a Whole CIDR Block
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A firewall is configured with an ordered list of rules. Each rule pairs an IPv4 pattern with an action, for example:
```python
rules = [("192.168.1.0/24", "ALLOW"), ("8.8.8.8", "DENY")]
```
A pattern is either a CIDR block `a.b.c.d/p`, which covers every address whose first `p` bits equal the first `p` bits of `a.b.c.d`, or a bare address, which is treated as `/32`. The list is ordered, so the status of an address is the action of the first rule that covers it.
Write `get_status(rules, target)`. In the base question the target is a single address: `get_status(rules, "192.168.1.5")` returns `"ALLOW"`, because its first 24 bits (192.168.1) match the first rule. The follow-up asks what happens, once the rules are in place, when the target is itself a CIDR block. A block stands for many addresses, and it counts as allowed only if every address in it is allowed. Your function must handle both kinds of target.
### Function Signature
```python
def get_status(rules: list[tuple[str, str]], target: str) -> str:
```
### Rules
- Read each address as a 32-bit number with the first octet most significant. An address matches the pattern `n/p` when its first `p` bits equal the first `p` bits of `n`. `/0` matches every address. Bits of `n` after the first `p` are ignored.
- The status of a single address is the action of the lowest-index rule it matches.
- Assumption (not stated in the report): an address that matches no rule has status `"DENY"`.
- `target` is either a bare address (a block of exactly one address) or a CIDR block `a.b.c.d/q` covering every address whose first `q` bits equal those of `a.b.c.d`.
- Return `"ALLOW"` if every address in the target block has status `"ALLOW"`; otherwise return `"DENY"`. For a bare address this is simply that address's status.
### Constraints
- `1 <= len(rules) <= 10^5`
- Every prefix length, in a rule or in `target`, is an integer from 0 to 32; a pattern without `/` means `/32`.
- Every address is four decimal octets from 0 to 255, separated by dots, with no leading zeros or whitespace.
- Every action is exactly `"ALLOW"` or `"DENY"`.
- A target block can contain up to `2^32` (4,294,967,296) addresses, which exceeds `2^31 - 1`.
- The output is exactly `"ALLOW"` or `"DENY"`.
### Examples
**Example 1**
```text
rules = [("192.168.1.0/24", "ALLOW"), ("8.8.8.8", "DENY")]
target = "192.168.1.5"
Output: "ALLOW"
```
The first 24 bits of `192.168.1.5` match rule 0. With the same rules, `"8.8.8.8"` would return `"DENY"` (rule 1), and `"10.0.0.1"` would return `"DENY"` because no rule matches it.
**Example 2**
```text
rules = [("10.0.0.7", "DENY"), ("10.0.0.0/24", "ALLOW")]
target = "10.0.0.0/28"
Output: "DENY"
```
The block covers `10.0.0.0` through `10.0.0.15`. Address `10.0.0.7` matches the `DENY` rule first, so the block is not entirely allowed. The target `"10.0.0.16/28"` would return `"ALLOW"`.
**Example 3**
```text
rules = [("10.0.0.0/25", "ALLOW"), ("10.0.0.128/25", "ALLOW")]
target = "10.0.0.0/24"
Output: "ALLOW"
```
No single rule covers the whole block, but each of its halves, `10.0.0.0` through `10.0.0.127` and `10.0.0.128` through `10.0.0.255`, is covered by an `ALLOW` rule.
Overview: Implement an ordered first-match IPv4 firewall that returns ALLOW or DENY for an address, then extend it so the target can be a whole CIDR block that is allowed only if every address inside it is. Tests bit-level prefix matching and reasoning about address ranges at scale.