How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Databricks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

Check if CIDR is fully canceled by rules | Databricks Coding Question

Quick Overview

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.

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.

Loading coding console...

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.

Input: ("192.168.1.0/24", [("allow", "192.168.1.0/25"), ("deny", "192.168.1.128/26"), ("allow", "192.168.1.128/25")])

Expected Output: False

Explanation: After removing the lower half, the remaining region is `192.168.1.128/25`. The deny rule overlaps part of that remaining region, so the answer is immediately False.

Input: ("10.0.0.0/24", [("allow", "10.0.0.0/25"), ("deny", "10.0.0.0/26"), ("allow", "10.0.0.128/25")])

Expected Output: True

Explanation: The deny rule only touches addresses already removed by the first allow, so it does not overlap the current remaining region. The final allow removes the rest.

Input: ("10.0.0.0/24", [("allow", "10.0.0.64/26"), ("allow", "10.0.0.0/26"), ("allow", "10.0.0.128/25")])

Expected Output: True

Explanation: The first allow removes the middle quarter and splits the remaining region into two pieces. The next two allows remove both pieces completely.

Input: ("0.0.0.0/0", [])

Expected Output: False

Explanation: With no rules, the target is never canceled, so the remaining region is not empty.

Input: ("10.0.1.5/24", [("allow", "10.0.1.200/25"), ("allow", "10.0.1.1/25")])

Expected Output: True

Explanation: Both CIDRs are interpreted by prefix, so they cover the upper and lower halves of `10.0.1.0/24`. Together they remove the whole target.

Solution

def solution(target, rules):
    MAX32 = 0xFFFFFFFF

    def ip_to_int(ip):
        a, b, c, d = map(int, ip.split('.'))
        return (a << 24) | (b << 16) | (c << 8) | d

    def parse_cidr(cidr):
        ip_str, prefix_str = cidr.split('/')
        prefix = int(prefix_str)
        ip = ip_to_int(ip_str)

        if prefix == 0:
            start = 0
            end = MAX32
        else:
            mask = (MAX32 << (32 - prefix)) & MAX32
            start = ip & mask
            end = start | (MAX32 ^ mask)

        return start, end

    t_start, t_end = parse_cidr(target)
    remaining = [(t_start, t_end)]

    for rule_type, cidr in rules:
        r_start, r_end = parse_cidr(cidr)

        if rule_type == 'deny':
            for a, b in remaining:
                if b < r_start:
                    continue
                if a > r_end:
                    break
                return False
        else:
            new_remaining = []
            for a, b in remaining:
                if b < r_start or a > r_end:
                    new_remaining.append((a, b))
                else:
                    if a < r_start:
                        new_remaining.append((a, r_start - 1))
                    if r_end < b:
                        new_remaining.append((r_end + 1, b))
            remaining = new_remaining
            if not remaining:
                return True

    return not remaining

Time complexity: O(r * k) where `r` is the number of rules and `k` is the number of remaining intervals at each step; worst-case O(r^2). Space complexity: O(r) worst-case for storing the disjoint remaining intervals.

Quick Overview

Constraints

Examples

Solution

Hints