##### Question Design and implement a firewall rule matcher that evaluates a single IPv4 address against a list of CIDR rules (each tagged accept/deny). Explain and code the data structures and algorithms you would use. Follow-up: extend the solution to handle matching an incoming CIDR range against the rule set and discuss efficient data structures for range intersection checks.

This question evaluates understanding of IP networking and prefix-based access control, specifically CIDR notation, longest-prefix match semantics, and data-structure skills for efficient prefix and range queries.

How do I approach System Design interview questions?

System Design questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master system design interviews.

What difficulty level is this interview question?

This is a medium difficulty System Design 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.

Implement CIDR firewall matcher | Databricks Interview Question

Firewall Rule Matcher for IPv4 CIDR Rules

Context and Assumptions

You are to design and implement a firewall rule matcher that decides whether to accept or deny traffic for IPv4 addresses based on a list of CIDR-prefix rules. Each rule is tagged accept or deny. Assume:

IPv4 (32-bit addresses).
Precedence: longest-prefix match wins (typical for CIDR-based routing). For ties (same prefix length), earlier rule definition wins. If nothing matches, default is deny.
Rules can overlap (e.g., 10.0.0.0/8 accept and 10.0.0.0/16 deny).

Tasks

Design and implement a matcher that evaluates a single IPv4 address against a list of CIDR rules (accept/deny). Explain the data structures and algorithms used.
Follow-up: extend the solution to handle evaluating an incoming CIDR range against the rule set. Discuss and propose efficient data structures for range intersection checks.

Inputs/Outputs

Input (single-IP case): list of rules like [("10.0.0.0/8", accept), ("10.0.0.0/16", deny), ...] and a query IP (e.g., "10.1.2.3").
Output: accept or deny according to precedence.
Follow-up input: an incoming CIDR (e.g., "10.1.0.0/17").
Follow-up output: either a single decision if uniform over the range, or a decomposition into subranges with decisions; and a discussion of efficient data structures for range intersection.

Context and Assumptions

IPv4 (32-bit addresses).

Precedence: longest-prefix match wins (typical for CIDR-based routing). For ties (same prefix length), earlier rule definition wins. If nothing matches, default is deny.

Rules can overlap (e.g., 10.0.0.0/8 accept and 10.0.0.0/16 deny).

Tasks

Design and implement a matcher that evaluates a single IPv4 address against a list of CIDR rules (accept/deny). Explain the data structures and algorithms used.

Follow-up: extend the solution to handle evaluating an incoming CIDR range against the rule set. Discuss and propose efficient data structures for range intersection checks.

Inputs/Outputs

Input (single-IP case): list of rules like [("10.0.0.0/8", accept), ("10.0.0.0/16", deny), ...] and a query IP (e.g., "10.1.2.3").

Output: accept or deny according to precedence.

Follow-up input: an incoming CIDR (e.g., "10.1.0.0/17").

Follow-up output: either a single decision if uniform over the range, or a decomposition into subranges with decisions; and a discussion of efficient data structures for range intersection.

Implement CIDR firewall matcher

Quick Overview

Firewall Rule Matcher for IPv4 CIDR Rules

Context and Assumptions

Tasks

Inputs/Outputs

Solution

Comments (0)

Implement CIDR firewall matcher

Quick Overview

Firewall Rule Matcher for IPv4 CIDR Rules

Context and Assumptions

Tasks

Inputs/Outputs

Solution

Comments (0)