PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates understanding of IPv4 addressing and CIDR prefix matching, including bitwise reasoning, robust parsing, handling of edge cases, and algorithmic efficiency for large rule sets.

  • hard
  • Databricks
  • Coding & Algorithms
  • Software Engineer

Implement firewall matching with CIDR rules

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Implement a simple IPv4 firewall rule matcher. ### Problem You are given an ordered list of firewall rules. Each rule has: - an **action**: `ALLOW` or `DENY` - a **CIDR prefix** in IPv4 notation: `A.B.C.D/L`, where: - `A, B, C, D` are integers in `[0, 255]` - `L` (the prefix length) is an integer in `[0, 32]` The firewall processes incoming IPv4 addresses in order of the rules: - Convert each IPv4 address and each rule's network address to a 32‑bit integer. - An IP address **matches** a CIDR rule if the first `L` bits of the IP are equal to the first `L` bits of the rule's network address. - Rules are evaluated in the given order. The **first** matching rule determines the result. - If **no** rule matches, the default is `DENY`. ### Task Design and implement a function: ```text bool isAllowed(List<Rule> rules, string ipAddress) ``` where: - `rules` is the ordered list of rules, each with `action` ∈ {`"ALLOW"`, `"DENY"`} and `cidr` ∈ IPv4 CIDR format `"A.B.C.D/L"`. - `ipAddress` is a string in IPv4 dotted format `"A.B.C.D"`. The function should return `true` if the IP is allowed by the rule set, and `false` otherwise. You should: - Parse and validate IPv4 addresses and CIDR strings. - Implement correct CIDR matching semantics for all prefix lengths, including edge cases like `/0` (matches all IPs) and `/32` (matches exactly one IP). - Assume there can be up to, for example, `10^5` rules and `10^5` queries, and aim for an efficient solution. ### Follow‑up 1 — Test cases List and explain a set of important test cases you would use to validate your implementation, including: - Simple matches and non‑matches. - Multiple matching rules where the **first** should win. - Boundary addresses of CIDR ranges (first and last IP in the block). - Edge prefix lengths (0 and 32). - Invalid inputs (malformed IPs or CIDRs) and how your function should behave in that case (you may define reasonable behavior and be consistent). ### Follow‑up 2 — CIDR as query input Extend the API so that the input to check is itself a CIDR block, e.g. `"10.0.1.0/24"`, instead of a single IP. Define and implement a function with a suitable signature, for example: ```text Result checkRange(List<Rule> rules, string cidrRange) ``` Decide and justify the semantics of `Result`, for example: - Does it indicate whether the **entire** range is allowed/denied by the same action? - Does it distinguish between fully allowed, fully denied, and **mixed** (partially allowed, partially denied) ranges? Clearly specify the matching and precedence rules when a CIDR range query overlaps multiple firewall rules. ### Follow‑up 3 — Matching condition Formally specify, in terms of 32‑bit integers and bit operations, the exact condition under which an IPv4 address matches a CIDR `network/prefixLength` pair.

Quick Answer: This question evaluates understanding of IPv4 addressing and CIDR prefix matching, including bitwise reasoning, robust parsing, handling of edge cases, and algorithmic efficiency for large rule sets.

Part 1: Implement isAllowed for IPv4 firewall matching with CIDR rules

You are given an ordered list of firewall rules. Each rule is a pair (action, cidr), where action is 'ALLOW' or 'DENY' and cidr is an IPv4 CIDR such as '192.168.1.0/24'. Given one IPv4 address, return whether it is allowed. A rule matches when the first L bits of the IP equal the first L bits of the CIDR's address. Rules are checked in order, the first matching rule wins, and if no rule matches the result is deny. For this problem, treat any malformed IP, malformed CIDR, malformed rule shape, or invalid action as invalid input and return False.

Constraints

  • 0 <= len(rules) <= 10^5
  • Each IPv4 octet must be an integer in [0, 255]
  • Each prefix length must be an integer in [0, 32]
  • Rule order matters: the first matching rule decides the result
  • If any rule or the queried IP is malformed, return False

Examples

Input: ([('ALLOW', '192.168.1.0/24'), ('DENY', '0.0.0.0/0')], '192.168.1.99')

Expected Output: True

Explanation: Both rules match, but the first match is ALLOW, so the IP is allowed.

Input: ([('DENY', '10.0.0.0/8'), ('ALLOW', '10.0.0.0/16')], '10.0.5.6')

Expected Output: False

Explanation: The IP matches both CIDRs, but the earlier DENY rule wins.

Input: ([('ALLOW', '10.0.0.0/24')], '10.0.1.1')

Expected Output: False

Explanation: No rule matches, so the default result is DENY.

Input: ([('ALLOW', '1.2.3.4/32'), ('DENY', '0.0.0.0/0')], '1.2.3.4')

Expected Output: True

Explanation: A /32 rule matches exactly one IP address.

Input: ([('ALLOW', '10.0.0.0/8'), ('DENY', '300.0.0.0/8')], '10.1.2.3')

Expected Output: False

Explanation: Any malformed rule makes the whole input invalid for this problem, so return False.

Hints

  1. Convert dotted IPv4 strings into a single 32-bit integer so comparisons become bit operations.
  2. For a prefix length L, build a mask with the top L bits set and compare masked values.

Part 2: Validate coverage of a firewall matcher test suite

A good firewall matcher test suite should cover several important categories. You are given a list of proposed single-IP test cases. Each test case is (rules, ip_address), where rules is a list of (action, cidr) pairs. Return which coverage categories are still missing from the suite. Use these exact categories and this exact output order: ['SIMPLE_MATCH', 'SIMPLE_NON_MATCH', 'FIRST_RULE_WINS', 'BOUNDARY', 'EDGE_PREFIX_0', 'EDGE_PREFIX_32', 'INVALID_INPUT']. A case covers SIMPLE_MATCH if exactly one valid rule matches the IP. It covers SIMPLE_NON_MATCH if no valid rule matches and the result would be default deny. It covers FIRST_RULE_WINS if at least two valid rules match the same IP and at least two of those matching rules have different actions. It covers BOUNDARY if the IP equals the first or last IP of any valid CIDR block in that case. It covers EDGE_PREFIX_0 or EDGE_PREFIX_32 if that case contains a valid /0 or /32 rule. It covers INVALID_INPUT if the IP or any rule in that case is malformed. Return the missing categories.

Constraints

  • 0 <= len(test_suite) <= 10^4
  • The total number of rules across all cases is at most 2 * 10^5
  • Only valid cases may cover categories other than INVALID_INPUT
  • IPv4 and CIDR validation rules are the same as in the firewall problem

Examples

Input: ([([('ALLOW', '10.0.0.0/24')], '10.0.0.5'), ([('ALLOW', '10.0.0.0/24')], '11.0.0.1'), ([('DENY', '10.0.0.0/8'), ('ALLOW', '10.0.0.0/16')], '10.0.1.1'), ([('ALLOW', '192.168.1.0/24')], '192.168.1.255'), ([('ALLOW', '0.0.0.0/0')], '8.8.8.8'), ([('DENY', '1.2.3.4/32')], '1.2.3.4'), ([('ALLOW', '300.1.1.0/24')], '1.1.1.1')],)

Expected Output: []

Explanation: This suite covers every required category, including invalid input.

Input: ([([('ALLOW', '10.0.0.0/24')], '10.0.0.5'), ([('ALLOW', '10.0.0.0/24')], '11.0.0.1'), ([('DENY', '10.0.0.0/8'), ('ALLOW', '10.0.0.0/16')], '10.0.1.1'), ([('ALLOW', '0.0.0.0/0')], '8.8.8.8')],)

Expected Output: ['BOUNDARY', 'EDGE_PREFIX_32', 'INVALID_INPUT']

Explanation: The suite has a simple match, a non-match, precedence, and /0, but no boundary case, no /32 case, and no invalid input case.

Input: ([],)

Expected Output: ['SIMPLE_MATCH', 'SIMPLE_NON_MATCH', 'FIRST_RULE_WINS', 'BOUNDARY', 'EDGE_PREFIX_0', 'EDGE_PREFIX_32', 'INVALID_INPUT']

Explanation: An empty proposed suite covers nothing.

Input: ([([('ALLOW', '10.0.0.0/24')], '999.1.1.1')],)

Expected Output: ['SIMPLE_MATCH', 'SIMPLE_NON_MATCH', 'FIRST_RULE_WINS', 'BOUNDARY', 'EDGE_PREFIX_0', 'EDGE_PREFIX_32']

Explanation: This suite covers only INVALID_INPUT because the queried IP is malformed.

Hints

  1. Reuse the same IP-to-integer and CIDR parsing logic you would use in the firewall matcher itself.
  2. Track each category with a boolean flag; one valid case can cover several categories at once.

Part 3: Extend firewall matching to CIDR range queries

Instead of checking one IP address, you must check an entire queried CIDR block such as '10.0.1.0/24'. Each IP inside that block is evaluated by the same ordered firewall rules, using first-match-wins and default deny. Return 'ALLOW' if every IP in the queried block ends with ALLOW, 'DENY' if every IP ends with DENY, and 'MIXED' if some IPs are allowed while others are denied. If the query CIDR or any rule is malformed, return 'INVALID'. A CIDR like '10.0.1.7/24' represents the whole /24 block after masking.

Constraints

  • 0 <= len(rules) <= 5000
  • Each action must be 'ALLOW' or 'DENY'
  • Each IPv4 octet must be in [0, 255] and each prefix length in [0, 32]
  • Rules are evaluated in the given order
  • Malformed input should return 'INVALID'

Examples

Input: ([('ALLOW', '10.0.0.0/24')], '10.0.0.0/24')

Expected Output: 'ALLOW'

Explanation: The single rule covers the whole queried block, so every IP is allowed.

Input: ([('ALLOW', '10.0.0.0/25')], '10.0.0.0/24')

Expected Output: 'MIXED'

Explanation: The first half of the /24 is allowed, while the second half is denied by default.

Input: ([('DENY', '10.0.0.0/24'), ('ALLOW', '10.0.0.0/25')], '10.0.0.0/25')

Expected Output: 'DENY'

Explanation: Even though the later ALLOW overlaps, the earlier DENY already matches the whole query block.

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

Expected Output: 'DENY'

Explanation: With no rules at all, every IP is denied by default.

Input: ([('ALLOW', '10.0.0.0/24')], '10.0.0.0/33')

Expected Output: 'INVALID'

Explanation: A prefix length of 33 is invalid.

Hints

  1. Convert each CIDR to an integer interval [start, end].
  2. Process rules in order while keeping track of only the still-unresolved parts of the query range.

Part 4: Implement the exact IPv4-to-CIDR matching condition

Given one IPv4 address and one CIDR string, return whether the IP matches the CIDR. Matching means that if the CIDR is network/prefixLength, then the first prefixLength bits of the IP and the CIDR address are equal. For this problem, return False for malformed IPs or malformed CIDRs.

Constraints

  • Each IPv4 octet must be an integer in [0, 255]
  • The prefix length must be an integer in [0, 32]
  • Return False on malformed input
  • You should use bit operations rather than string-by-string binary comparison

Examples

Input: ('192.168.1.10', '192.168.1.0/24')

Expected Output: True

Explanation: The first 24 bits match.

Input: ('192.168.2.10', '192.168.1.0/24')

Expected Output: False

Explanation: The third octet differs, so the first 24 bits do not match.

Input: ('8.8.8.8', '0.0.0.0/0')

Expected Output: True

Explanation: A /0 CIDR matches every IPv4 address.

Input: ('1.2.3.4', '1.2.3.4/32')

Expected Output: True

Explanation: A /32 CIDR matches exactly one IP.

Input: ('256.1.1.1', '1.2.3.0/24')

Expected Output: False

Explanation: The IP is malformed because 256 is outside the valid IPv4 octet range.

Hints

  1. A prefix length of 0 means every IP matches.
  2. Use a 32-bit mask with the top L bits set, then compare masked values.
Last updated: Apr 19, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Choose the Best Travel Mode - Databricks (medium)
  • Implement an Alternating Tic-Tac-Toe Game - Databricks (hard)
  • Implement a Snapshot Set Iterator - Databricks (medium)
  • Find the Best Commute Mode - Databricks (medium)
  • Partition a Target String by Source Substrings - Databricks (medium)