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.

Design an IP filter using CIDR rules | Databricks Coding Question

Quick Overview

This question evaluates understanding of IP addressing and CIDR notation, bit-level conversion between prefixes and integer ranges, and the design of scalable data structures and algorithms for prefix/range queries, rule priority handling, and rule-set operations (allow/deny semantics).

Design an IP filter using CIDR rules

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Explain CIDR notation with a couple of concrete examples. Show how to convert a prefix like 192.168.0.0/16 into an inclusive 32-bit integer range and a subnet mask. Then, design a data structure for a firewall rule set: each rule is (prefix: CIDR string, action: 'allow' | 'deny', priority: integer). Implement addRule(rule), removeRule(ruleId), and query(ipAddress) -> action. Specify the matching semantics when prefixes overlap (support both first-match-by-priority and longest-prefix-match), target time/space complexity, and how you would handle up to 10^6 rules and 10^5 queries per second. Follow-up: the query is now a CIDR block instead of a single IP. Add operations overlap(queryPrefix) -> boolean, coveredByAllow(queryPrefix) -> boolean, coveredByDeny(queryPrefix) -> boolean, and listConflictingRules(queryPrefix) -> [ruleIds]. Which data structures would you choose to support efficient range and overlap queries, and how would your design extend to IPv6?

Quick Answer: This question evaluates understanding of IP addressing and CIDR notation, bit-level conversion between prefixes and integer ranges, and the design of scalable data structures and algorithms for prefix/range queries, rule priority handling, and rule-set operations (allow/deny semantics).

Part 1: Dynamic IPv4 firewall with CIDR matching

IPv4 CIDR notation a.b.c.d/p means the first p bits are fixed and the remaining 32-p bits may vary. For example, 192.168.0.0/16 has subnet mask 255.255.0.0 and covers every address from 192.168.0.0 to 192.168.255.255. Build a firewall that processes command strings over active rules. Each ADD command creates a rule (prefix, action, priority) and receives the next rule id starting from 1. Commands: - ADD <cidr> <action> <priority> - REMOVE <ruleId> - QUERY <ipAddress> The matching mode is given separately: - priority: among all matching active rules, choose the one with the smallest priority value; ties go to the smaller rule id. - lpm: longest-prefix-match; if several active rules have that same longest prefix length, choose the one with the smallest priority, then smaller rule id. Return the action for each QUERY command in order. If no active rule matches, return "none".

Constraints

1 <= len(commands) <= 200000
0 <= priority <= 10^9
All IP addresses are valid IPv4 addresses and all CIDR prefixes satisfy 0 <= p <= 32
REMOVE on a non-existent or already removed rule does nothing

Examples

Input: ("priority", ["ADD 10.0.0.0/8 allow 5", "ADD 10.1.0.0/16 deny 10", "QUERY 10.1.2.3", "ADD 10.1.2.0/24 deny 1", "QUERY 10.1.2.3", "REMOVE 3", "QUERY 10.1.2.3"])

Expected Output: ["allow", "deny", "allow"]

Explanation: In priority mode, the smallest priority wins among all matching prefixes. After removing rule 3, the /8 allow rule wins again.

Input: ("lpm", ["ADD 0.0.0.0/0 deny 100", "ADD 192.168.1.0/24 allow 50", "ADD 192.168.1.128/25 deny 1", "QUERY 192.168.1.10", "QUERY 192.168.1.200", "QUERY 8.8.8.8"])

Expected Output: ["allow", "deny", "deny"]

Explanation: In longest-prefix-match mode, the deepest matching prefix wins before priority is considered.

Input: ("priority", ["QUERY 1.1.1.1", "REMOVE 1", "ADD 255.255.255.255/32 allow 7", "QUERY 255.255.255.255", "QUERY 255.255.255.254"])

Expected Output: ["none", "allow", "none"]

Explanation: Edge case: querying with no active rules returns none. A /32 rule matches exactly one address.

Input: ("priority", ["ADD 1.1.1.0/24 deny 3", "ADD 1.1.1.0/24 allow 3", "QUERY 1.1.1.4", "REMOVE 1", "QUERY 1.1.1.4"])

Expected Output: ["deny", "allow"]

Explanation: When both priority and prefix length tie, the smaller rule id wins.

Hints

A binary trie over the 32 bits of an IPv4 address lets you inspect every matching prefix on one root-to-leaf path.
For removals, lazy deletion works well: mark a rule inactive, and discard it later when it reaches the top of a heap.

Part 2: CIDR block overlap and coverage queries

Convert each IPv4 CIDR block into an inclusive integer interval [start, end]. For example, 192.168.0.0/16 becomes [3232235520, 3232301055]. Maintain a dynamic set of active firewall rules, where each ADD command creates a new rule id starting from 1 and each rule has only a prefix and an action. Commands: - ADD <cidr> <action> - REMOVE <ruleId> - OVERLAP <cidr> - COVERED_ALLOW <cidr> - COVERED_DENY <cidr> - CONFLICTS <cidr> Definitions: - OVERLAP: does the query block intersect at least one active rule? - COVERED_ALLOW: is every IP in the query block covered by the union of active allow rules? - COVERED_DENY: same for active deny rules. - CONFLICTS: look at active rules whose blocks overlap the query block. If both allow and deny appear among those overlapping rules, return all such overlapping rule ids in increasing order; otherwise return an empty list. These operations ignore priority and matching order; they are purely interval-based. Return one string per query command in order. Use "YES" or "NO" for boolean queries. For CONFLICTS, return the Python-list string form, such as "[]" or "[1, 3]". Implement IPv4 only. The same interval idea extends to IPv6 by replacing 32-bit integers with 128-bit integers.

Constraints

1 <= len(commands) <= 20000
All addresses are valid IPv4 CIDR blocks with 0 <= p <= 32
REMOVE on a non-existent or already removed rule does nothing
The intended solution supports fast overlap and coverage queries; CONFLICTS may spend O(A) time scanning active rules to enumerate matching ids

Examples

Input: ["ADD 10.0.0.0/25 allow", "ADD 10.0.0.128/25 allow", "COVERED_ALLOW 10.0.0.0/24", "OVERLAP 10.0.1.0/24", "ADD 10.0.0.64/26 deny", "CONFLICTS 10.0.0.0/24", "COVERED_DENY 10.0.0.64/26", "REMOVE 3", "CONFLICTS 10.0.0.0/24"]

Expected Output: ["YES", "NO", "[1, 2, 3]", "YES", "[]"]

Explanation: Two adjacent /25 allow rules together cover the full /24. After adding a deny block inside that range, the overlapping rules on the /24 contain both actions, so they conflict.

Input: ["ADD 0.0.0.0/1 deny", "ADD 128.0.0.0/1 deny", "COVERED_DENY 0.0.0.0/0", "OVERLAP 192.168.1.0/24", "CONFLICTS 192.168.1.0/24"]

Expected Output: ["YES", "YES", "[]"]

Explanation: The two /1 deny rules partition the whole IPv4 space, so together they cover /0. There is overlap with the query block, but no allow rule, so no conflict.

Input: ["OVERLAP 1.2.3.0/24", "COVERED_ALLOW 1.2.3.0/24", "CONFLICTS 1.2.3.0/24"]

Expected Output: ["NO", "NO", "[]"]

Explanation: Edge case: with no rules, there is no overlap, no coverage, and no conflict.

Input: ["ADD 255.255.255.255/32 allow", "COVERED_ALLOW 255.255.255.255/32", "OVERLAP 255.255.255.254/31", "REMOVE 1", "OVERLAP 255.255.255.255/32"]

Expected Output: ["YES", "YES", "NO"]

Explanation: A /32 rule covers exactly one address. The /31 query overlaps it before removal and does not overlap after removal.

Input: ["ADD 192.168.1.0/25 allow", "COVERED_ALLOW 192.168.1.0/24"]

Expected Output: ["NO"]

Explanation: A single /25 covers only half of the /24, so full coverage fails.

Hints

Turn each CIDR block into an integer interval [start, end]. Then overlap becomes a range problem.
Because all commands are known before processing starts, coordinate compression plus a range-add segment tree can maintain coverage counts over elementary IP segments.

Quick Overview