Coding - Firewall CIDR Rules

In a Databricks technical interview, the "Firewall CIDR Rules" problem typically asks you to implement a rule-based IPv4 firewall engine. PracHub +1 4 0

Problem Statement

You are given an ordered list of rules, where each rule consists of an action (ALLOW or DENY) and a target (either a specific IPv4 address or a CIDR block). 0 1

Your goal is to implement a function—often called allowAccess(ip)—that determines if a given target IP should be allowed access. The primary constraint is that only the first matching rule applies; if an IP matches multiple rules, the outcome is determined by the one that appears earliest in the list. LeetCode +1 2 0 1

Example Scenario

Input Rules:

1. ["ALLOW", "192.168.1.100"] (Specific IP)
2. ["DENY", "192.168.1.0/24"] (CIDR block)
3. ["ALLOW", "192.168.0.0/16"] (Broader CIDR block)
4. ["DENY", "0.0.0.0/0"] (Catch-all)

Example Queries:

• 192.168.1.100 →right arrow→ true (Matches Rule 1 exactly).
• 192.168.1.50 →right arrow→ false (Fails Rule 1, but matches Rule 2's /24 subnet).
• 192.168.2.10 →right arrow→ true (Fails Rules 1 and 2, but matches Rule 3's /16 subnet).
• 10.0.0.1 →right arrow→ false (Fails first three, matches catch-all Rule 4).

Common Follow-Up Variations

Depending on the role level (e.g., Senior vs. Junior), the interviewer may add these complexities:

• Dynamic Updates: Design data structures to efficiently support addRule(rule) and removeRule(ruleId) while maintaining low-latency queries.
• Matching Semantics: Support different resolution strategies, such as "Most-Specific-Wins" (longest prefix match) instead of "First-Match-By-Priority".
• Range Queries: Determine if an entire CIDR block is fully allowed or denied by the current rule set.
• Scalability: How to handle 10610 to the sixth power106 rules and 10510 to the fifth power105 queries per second using advanced structures like Interval Trees or Radix Tries. PracHub +2

Suggested Technical Approach

1. Integer Conversion: Convert all IPv4 strings into 32-bit integers to allow for constant-time bitwise comparisons.
2. Bitmasking: For CIDR blocks (e.g., /24), precompute a bitmask. A match occurs if (queryIP & mask) == (ruleIP & mask).
3. Linear Scan (Baseline): For a small number of rules, iterating through the list is 𝑂(𝑁) per query.

Would you like to see a Python implementation of this logic or an explanation of how to handle overlapping rules?

[0] - Databricks Screening Interview: IP CIDR Firewall : r/Hack2Hire [1] - Databricks Screening Interview: IP CIDR Firewall : r/Hack2Hire [2] - Databricks L5 (SSE) Technical Phone Screen | Cleared [3] - Design an IP filter using CIDR rules - Databricks Questions [4] - Design IP/CIDR rule matcher | Databricks Interview Question [5] - Check if CIDR is fully canceled by rules | Databricks Interview Question [6] - Databricks Interview Questions & Practice - ShowOffer