Implement CIDR firewall matcher
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.
Constraints & Assumptions
-
Preserve the scope, facts, inputs, and requested outputs from the prompt above.
-
If the prompt leaves a detail unspecified, state a reasonable assumption before relying on it.
-
Keep the answer interview-ready: concise enough to present, but concrete enough to implement or evaluate.
Clarifying Questions to Ask
-
Clarify users, core use cases, read/write patterns, scale, latency, availability, and data retention.
-
State explicit assumptions before making sizing or architecture decisions.
-
Prioritize the functional path first, then address reliability, security, observability, and rollout.
What a Strong Answer Covers
-
A scoped requirements summary with concrete non-goals and success metrics.
-
API, data model, architecture, consistency, capacity, and operations.
-
Reasoned trade-offs among simple and scalable designs, including bottlenecks and failure modes.
-
A validation, monitoring, migration, and launch plan appropriate for the risk level.
Follow-up Questions
-
What breaks first at 10x traffic or data volume?
-
How would you degrade gracefully during dependency failures?
-
What metrics and alerts would prove the design is healthy after launch?