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.
A firewall is configured with an ordered list of rules. Each rule is a pair `(pattern, action)` that 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.
Implement `get_status(rules, target)`. The target is either a single address or 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.
### Rules
- Read each address as a 32-bit unsigned 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.
- 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` (so bits of the target after the first `q` are ignored too).
- 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. A block does not need one rule that covers all of it: it is allowed whenever each of its addresses individually has status `"ALLOW"`.
`rules` is passed as a single argument: a list of two-element `(pattern, action)` pairs (arrays in JavaScript, `java.util.List<java.util.List<String>>` in Java, `std::vector<std::vector<std::string>>` in C++).
### 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"`.
An address read as a 32-bit number can be as large as `2^32 - 1` (4,294,967,295), and a block can hold `2^32` addresses; both exceed `2^31 - 1`, so address arithmetic needs 64-bit integers (`long` in Java, `long long` in C++).
### 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` (192.168.1) 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"`.
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
Input: ([('192.168.1.0/24', 'ALLOW'), ('8.8.8.8', 'DENY')], '192.168.1.5')
Expected Output: 'ALLOW'
Explanation: Source example 1: 192.168.1.5 lies in 192.168.1.0/24, the first rule, which allows it.
Input: ([('192.168.1.0/24', 'ALLOW'), ('8.8.8.8', 'DENY')], '8.8.8.8')
Expected Output: 'DENY'
Explanation: Source example 1 variant: 8.8.8.8 only matches the bare /32 DENY rule.
Hints
- Turn each dotted address into one 32-bit number; a prefix of length p then describes one contiguous, aligned range of 2^(32-p) addresses.
- Two CIDR ranges are always either disjoint or nested, so a rule either contains the whole target block, lies entirely inside it, or cannot affect it.
- A later rule only decides the status of addresses that no earlier rule matched, and a block can be fully allowed even when no single rule covers it.