Quick Overview

This question evaluates understanding of IPv4 addressing, CIDR and numeric range representations, plus competency in designing efficient data structures and algorithms for low-latency rule matching with dynamic updates.

Design IP/CIDR rule matcher

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement a rule matcher that returns 'accept' or 'deny' for a given IPv4 address based on a set of rules. Each rule can be either an inclusive numeric IP range [start, end] or a CIDR block. Define the data structures to support addRule(rule), removeRule(rule), and query(ip), and explain how you resolve overlapping or conflicting rules (e.g., most-specific-wins, then newest-wins). Target up to 1e5 rules with low-latency queries. Analyze time and space complexity and outline tests to avoid bitwise operator-precedence bugs when parsing and comparing IP addresses. Follow-up: propose and compare data structures for efficient range and prefix checks (e.g., interval tree, segment tree, sorted disjoint intervals with binary search, ordered map, and binary/radix trie), and explain trade-offs for static vs dynamic updates.

Overview: This question evaluates understanding of IPv4 addressing, CIDR and numeric range representations, plus competency in designing efficient data structures and algorithms for low-latency rule matching with dynamic updates.

Part 1: IPv4 Rule Matcher with Add, Remove, and Query

You are given a sequence of firewall operations over IPv4 rules. A rule is either a closed numeric range or a CIDR block, and each rule has an action: 'accept' or 'deny'. Process the operations in order and return the result of every query. Conflict resolution is deterministic: among all active rules that match the queried IP, the most specific rule wins, where specificity means the smaller covered interval length. If two matching rules have the same interval length, the newer active rule wins. If no rule matches, return 'none'. If the same rule is added multiple times, each add creates a separate active instance, and a remove deletes only the most recently added still-active identical instance. Removing a rule that is not active does nothing.

Constraints

  • 0 <= len(operations) <= 100000
  • All IPv4 addresses are valid dotted-decimal IPv4 strings
  • CIDR prefix lengths are between 0 and 32 inclusive
  • Actions are either 'accept' or 'deny'
  • For range rules, start and end fit in the IPv4 space; treat the rule as inclusive

Examples

Input: [('add_cidr', '10.0.0.0/8', 'accept'), ('add_cidr', '10.1.0.0/16', 'deny'), ('query', '10.1.2.3'), ('query', '10.2.3.4'), ('query', '11.0.0.1')]

Expected Output: ['deny', 'accept', 'none']

Explanation: The /16 rule is more specific than the /8 rule for 10.1.2.3. The address 10.2.3.4 matches only the /8. The address 11.0.0.1 matches nothing.

Input: [('add_cidr', '192.168.1.1/32', 'deny'), ('add_range', '192.168.1.1', '192.168.1.1', 'accept'), ('query', '192.168.1.1')]

Expected Output: ['accept']

Explanation: Both rules cover exactly one IP, so they have equal specificity. The newer rule wins.

Hints

  1. Convert every IPv4 address to a 32-bit integer before comparing ranges. Use explicit parentheses when shifting and masking.
  2. Because the full operation list is known in advance, compress only the IPs that are actually queried, then support range updates and point queries on those coordinates.

Part 2: Choose the Best Rule-Index Data Structure for Firewall Workloads

You are given several workload scenarios for a firewall rule engine that must support numeric IP ranges and CIDR prefixes. For each scenario, choose the cheapest indexing strategy under the exact cost model below. This problem turns the follow-up design discussion into a deterministic optimization task. A scenario may be pure-range, pure-prefix, mixed, or even empty. For mixed workloads, you may also choose a hybrid strategy that uses a radix trie for prefixes and the cheapest valid range structure for numeric ranges.

Constraints

  • 1 <= len(scenarios) <= 100000
  • All count fields are integers between 0 and 10^9
  • coordinate_count is an integer between 0 and 10^9
  • Use L(x) = 0 if x <= 1, otherwise ceil(log2(x))
  • If multiple strategies have the same cost, use priority: sorted_disjoint_intervals < ordered_map < interval_tree < segment_tree < radix_trie < hybrid(...)

Examples

Input: [{'prefix_rules': 0, 'range_rules': 8, 'prefix_updates': 0, 'range_updates': 0, 'queries': 100, 'disjoint_ranges': True, 'coordinate_count': 0}]

Expected Output: ['sorted_disjoint_intervals']

Explanation: This is a pure static disjoint-range workload, which is exactly what sorted disjoint intervals are best at under the given model.

Input: [{'prefix_rules': 10, 'range_rules': 0, 'prefix_updates': 5, 'range_updates': 0, 'queries': 20, 'disjoint_ranges': False, 'coordinate_count': 0}]

Expected Output: ['radix_trie']

Explanation: This is a pure prefix workload, and only the radix trie directly targets prefixes without converting them to ranges.

Approach

This is a simulation / cost-comparison problem, not a classic algorithm: for each scenario we enumerate every legal indexing strategy, price it under the given cost model, and return the cheapest (breaking ties by a fixed priority order). Cost helper. clog2(x) implements L(x) = ceil(log2(x)) via (x-1).bit_length(), returning 0 when x <= 1. Range structures. best_range_strategy builds candidate (name, cost) pairs for the four range structures, each behind a guard: - sorted_disjoint_intervals only when ranges are disjoint and there are no range updates (static). - ordered_map only when ranges are disjoint. - interval_tree is always valid for range work. - segment_tree only when 0 < coordinate_count <= 200000 (coordinate compression must be feasible). lr = L(rules+updates), l0 = L(rules), and lc = L(coordinate_count) plug into the per-operation formulas in the cost model. Per-scenario dispatch. Based on whether prefix work and/or range work exist, one of four branches runs: - Empty: all range structures (size 0) plus a radix_trie priced at 32*queries. - Range-only: the range candidates. - Prefix-only: radix_trie (32*(rules+updates+queries)) and optionally segment_tree. - Mixed: an optional unified segment_tree, plus a hybrid combining the best range structure with a radix trie, named hybrid(<range>+radix_trie). Selection. The winner is min(candidates, key=(cost, overall_priority, name)), so equal costs resolve via the required ordering (sorted_disjoint_intervals < ordered_map < interval_tree < segment_tree < radix_trie < hybrid). overall_key maps any hybrid(...) string to the hybrid rank. This is correct because each branch enumerates exactly the strategies valid for that workload shape.

Time complexity: O(S), where S = len(scenarios). Each scenario evaluates a constant number of candidate strategies, and each cost is an O(1) arithmetic expression (bit_length is constant-time on the bounded integers here).

Space complexity: O(1) auxiliary per scenario (the candidates list / all_range dict hold a constant number of entries), excluding the O(S) output list.

Hints

  1. First classify each scenario as pure range, pure prefix, mixed, or empty. Different strategy sets are valid in different categories.
  2. Avoid floating-point logs. In Python, ceil(log2(x)) for x > 1 can be computed as (x - 1).bit_length().

Loading coding console...

Show the approach

Approach

Idea. Only the queried IPs can ever be answered, so the solution first collects every query IP, sorts the distinct values into coords, and builds a segment tree over these compressed coordinates (size m). Every rule — whether a range or a CIDR block — is converted to an inclusive integer interval [start, end] via ip_to_int/parse_cidr, then mapped to the compressed index window [l, r] with bisect. The rule is inserted into the canonical O(log m) tree nodes whose union covers [l, r] (the update recursion).

Conflict resolution. Each node holds a min-heap of tuples (length, -timestamp, rid, action). Because it's a min-heap, the smallest length (most specific = smallest interval) wins, and ties break on -timestamp, i.e. the newer rule. A query walks the root→leaf path to the IP's index and takes the best tuple across all nodes on that path — exactly the set of rules covering that IP — returning its action, or 'none'.

Add / remove semantics. Adds get a fresh rid and timestamp; identical rules are pushed onto a per-key rule_stacks LIFO so a remove deactivates the most-recently-added still-active instance (active[rid]=False). Deletion is lazy: heaps aren't edited on removal. Instead clean(node) pops heap tops whose rid is no longer active before reading the min, and remove pops dead entries off the stack top first. Querying a value never inserted means m=0 or the path's heaps are empty, yielding 'none'. This correctly handles duplicate adds, mismatched removes (no-ops), and the most-specific-then-newest tie-break shown in the tests.

Time complexity:
O((N + Q) log Q)
Space complexity:
O(Q + N log Q)