Determine allow/deny for an IP via CIDR rules
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
### Problem
You are implementing a simple IPv4 firewall.
You are given an **ordered** list of rules. Each rule has:
- an `action`: either `ALLOW` or `DENY`
- a CIDR block in the form `a.b.c.d/p` (e.g., `192.168.0.0/16`)
You are also given a query IPv4 address `ip` (e.g., `192.168.1.10`).
A rule **matches** the IP if the IP is within the rule’s CIDR range.
### Task
Return the action for the **first** rule in the list that matches `ip`. If no rule matches, return a configurable default action (assume `ALLOW` unless stated otherwise).
### Input / Output
- Input: `rules` (list of `(action, cidr)`), and `ip`
- Output: `"ALLOW"` or `"DENY"`
### Notes / Constraints
- IPv4 only.
- Rules may overlap.
- CIDR prefix length `p` is in `[0, 32]`.
- You may assume all inputs are well-formed strings.
Quick Answer: This question evaluates understanding of IPv4 addressing, CIDR range matching, rule ordering and precedence, and algorithmic correctness in determining allow/deny outcomes.
You are implementing a simple IPv4 firewall. You are given an ordered list of rules, where each rule is a pair (action, cidr). The action is either "ALLOW" or "DENY", and the CIDR is an IPv4 block like "192.168.0.0/16". You are also given a query IPv4 address ip. A rule matches if the IP falls within that CIDR range. Return the action of the first rule that matches the IP. If no rule matches, return the default action, which is "ALLOW" unless a different default is provided.
Constraints
- 0 <= len(rules) <= 10^5
- Each rule is of the form (action, cidr), where action is "ALLOW" or "DENY"
- CIDR prefix length p is in the range [0, 32]
- IPv4 only; all input strings are well-formed
- Rules are evaluated in order, and the first matching rule decides the result
Examples
Input: ([('DENY', '10.0.0.0/8'), ('ALLOW', '10.1.0.0/16')], '10.1.2.3')
Expected Output: 'DENY'
Explanation: 10.1.2.3 matches both CIDR blocks, but the first matching rule is DENY.
Input: ([('ALLOW', '192.168.1.10/32'), ('DENY', '192.168.1.0/24')], '192.168.1.10')
Expected Output: 'ALLOW'
Explanation: The exact /32 rule matches first, so it takes priority over the broader /24 deny rule.
Input: ([('DENY', '0.0.0.0/0')], '8.8.8.8')
Expected Output: 'DENY'
Explanation: A /0 CIDR matches every IPv4 address.