Databricks CIDR Firewall：首条规则与整段地址全覆盖

题目重点：从 IPv4 mask 匹配单 IP，扩展到整个 CIDR block 的 first-match 全覆盖判断，并区分其他规则语义。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

IPv4 地址合法；规则列表有序，每条是 CIDR 与 ALLOW/DENY；单 IP 无匹配时 DENY。CIDR host bits 可被规范化到网络地址。
块查询的训练口径：查询块内所有 IP 各自按同一个首条匹配规则执行，全部 ALLOW 才 true。部分题目写成 allow 消去/deny veto，若真实题定义为全局 deny 优先，结果会不同，必须当轮确认。

解题路线

解析 IPv4 为 32 位整数，CIDR /p 的网络区间由 mask 得到；IP 命中规则可用位掩码比较，也可用可靠库解析。单 IP 顺序扫描，第一条命中立即返回动作，O(R)。
不能枚举一个 /0 的 2³² 个地址。块查询先取查询区间 [lo,hi]，把每条规则与其相交区间的起点及终点后一位作为边界；在相邻边界段内，所有规则的命中真假不变，因此只查一段的代表 IP。
如果所有非空段都首条 ALLOW，整块 ALLOW；任何段 DENY 或无匹配则 false。/0、/32、无规则、完全覆盖、允许与拒绝交错及规则顺序反转都要测。
大量重复查询可把 ordered rules 编译成不相交 IPv4 决策区间后做二分；编译更新需要版本与原子替换。前缀 trie 可以加速点查询，但整块覆盖仍要证明所有子区间状态。

手动走一遍

规则 `10.0.0.0/31 ALLOW` 后接 `10.0.0.0/30 DENY`：查询 `10.0.0.0/31` 两个地址都首条允许，true；查询 `/30` 的后两个地址落第二条拒绝，false。若调换两规则顺序，原先允许的前两个也会变成拒绝。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Training contract for ordered IPv4 ALLOW/DENY firewall rules.
An address uses the first matching rule. Unmatched addresses are denied.
A queried CIDR block is allowed iff every address in it is allowed under
those same ordered rules. This is one explicit interpretation of the visible
follow-ups; the posts do not agree on a universal block-query contract.
"""
from ipaddress import IPv4Address, IPv4Network, ip_network

Rule = tuple[IPv4Network, str]


def parse_rules(raw: list[tuple[str, str]]) -> list[Rule]:
    rules = []
    for cidr, action in raw:
        if action not in {"ALLOW", "DENY"}:
            raise ValueError(f"unknown action: {action}")
        rules.append((ip_network(cidr, strict=False), action))
    return rules


def get_status(rules: list[Rule], ip: str) -> str:
    address = IPv4Address(ip)
    for network, action in rules:
        if address in network:
            return action
    return "DENY"


def block_fully_allowed(rules: list[Rule], block: str) -> bool:
    query = ip_network(block, strict=False)
    lo, hi = int(query.network_address), int(query.broadcast_address)
    boundaries = {lo, hi + 1}
    for network, _ in rules:
        first = max(lo, int(network.network_address))
        last = min(hi, int(network.broadcast_address))
        if first <= last:
            boundaries.add(first)
            boundaries.add(last + 1)
    ordered = sorted(boundaries)
    # Within each segment every rule's match status is constant, so one
    # representative point suffices. We do not enumerate large CIDR blocks.
    for start, end in zip(ordered, ordered[1:]):
        if start < end and get_status(rules, str(IPv4Address(start))) != "ALLOW":
            return False
    return True

复杂度

R 条规则：单 IP O(R) 时间/O(1) 查询空间；块查询收集至多 2R+2 个边界，排序 O(R log R)，至多 O(R) 个区间各扫 R 条规则，最坏 O(R²) 时间、O(R) 空间。预编译决策区间可换取多次查询性能。

易错点与追问

容易失分的边界

把字符串前缀比较当 CIDR 匹配，忽略 octet/bit 边界。
把规则当无序集合，丢掉首条优先级。
整块只查网络地址或仅查起止端点，漏中间 deny。
用枚举 IP 处理大块。
把 deny-veto 与 first-match 口径混在一个函数里。

继续深挖

CIDR block 全部允许与只要存在允许 IP 有何区别？
如果 deny 无条件优先，算法怎么变？
热规则频繁更新时如何编译并无锁切换？
IPv6 的 128 位地址有什么不同？