Check if CIDR is fully canceled by rules
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given:
- A target CIDR block `T` as a string, e.g. `"10.0.0.0/16"`.
- A list of rule CIDR blocks. Each rule has:
- A type: either `"allow"` or `"deny"`.
- A CIDR block (IPv4) as a string `"a.b.c.d/x"`.
Interpretation of rules when applied **in order** to the target CIDR `T`:
1. We start with the set of IPs covered by `T` as the "remaining" region.
2. For each rule in the list, from first to last:
- If the rule type is `"allow"` and its CIDR overlaps with the current remaining region of `T`, we **remove** ("cancel") the overlapping subset from the remaining region. (Think of this as: the allowed portion is handled elsewhere and is thus removed from what remains to be canceled.)
- If the rule type is `"deny"` and its CIDR has **any** overlap with the current remaining region of `T`, we immediately return `false` (because a deny rule applies somewhere inside `T`).
3. After processing all rules, if the remaining region of `T` is completely empty (i.e., all IPs in `T` have been canceled out by `allow` rules without any deny overlap), then return `true`. Otherwise, return `false`.
Task:
Implement a function that, given `T` and the list of `(type, CIDR)` rules, returns a boolean indicating whether `T` can be **fully canceled** by the rules under the above semantics.
Clarifications and requirements:
- Use standard IPv4 and CIDR semantics; `a.b.c.d/x` describes all addresses sharing the first `x` bits with `a.b.c.d`.
- Rules must be processed **sequentially** in the given order.
- Overlap is defined as having at least one common IP address.
- The remaining region of `T` may split into multiple disjoint CIDR ranges after applying some allow rules; you must handle such splitting correctly.
- Target and rules are all IPv4 CIDRs; strings are syntactically valid.
- Aim for a solution that is correct and reasonably efficient; discuss your complexity and any data structures used for representing and subtracting CIDR ranges.
Quick Answer: This question evaluates understanding of IPv4 CIDR arithmetic, set operations on IP ranges (overlap detection and subtraction), and ordered rule semantics for allow/deny processing.
You are given a target IPv4 CIDR block `target` and a list of rules. Each rule is a pair `(rule_type, cidr)` where `rule_type` is either `"allow"` or `"deny"`.
Interpret the rules in order over only the IP addresses inside `target`:
1. Start with the entire `target` as the remaining region.
2. For an `allow` rule, remove the overlapping part of that CIDR from the current remaining region.
3. For a `deny` rule, if it overlaps any part of the current remaining region, return `False` immediately.
4. After all rules, return `True` only if the remaining region is empty; otherwise return `False`.
Important details:
- Rules are processed strictly from first to last.
- Removing an allowed subrange may split the remaining region into multiple disjoint pieces.
- Later rules must be checked against all remaining pieces.
- CIDRs use normal IPv4 semantics even if the given address is not the canonical network address. For example, `10.0.1.5/24` represents the same block as `10.0.1.0/24`.
Implement a function that returns whether the target CIDR is fully canceled under these semantics.
Constraints
- 0 <= len(rules) <= 2000
- All CIDR strings are valid IPv4 CIDRs of the form `a.b.c.d/x` with `0 <= x <= 32`
- Rules must be processed sequentially in the given order
- Your solution must correctly handle splitting the remaining region into multiple disjoint intervals after an `allow` rule
Examples
Input: ("10.0.0.0/24", [("allow", "10.0.0.0/25"), ("allow", "10.0.0.128/25")])
Expected Output: True
Explanation: The first allow removes the lower half of the /24, and the second removes the upper half, so nothing remains.
Input: ("10.0.0.0/24", [("allow", "10.0.0.0/25")])
Expected Output: False
Explanation: Only the first 128 IPs are removed. The upper half of the target still remains.
Hints
- Convert each CIDR into an inclusive integer interval `[start, end]` using 32-bit IPv4 arithmetic.
- Maintain the uncanceled part of the target as a sorted list of disjoint intervals. An `allow` subtracts from these intervals, while a `deny` only needs to detect whether any interval overlaps.