Evaluate ACL rules for IP and CIDR
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
## Problem
You are implementing an IPv4 access-control list (ACL). The ACL contains ordered rules; each rule has:
- `action`: either `ALLOW` or `DENY`
- `cidr`: an IPv4 CIDR block like `192.168.1.0/24`
A request is **allowed** if the **first** rule (in order) whose CIDR contains the request matches and has `ALLOW`. If the first matching rule has `DENY`, the request is denied. If **no** rule matches, the request is denied.
### Task A (base)
Given an ACL and a single IPv4 address `ip` (e.g., `10.1.2.3`), determine whether the request is allowed.
### Task B (follow-up)
Now the input is a CIDR block `query_cidr` instead of a single IP. Determine whether **every IP address** inside `query_cidr` would be allowed by the ACL under the same “first match wins” semantics.
Return `true` if all addresses in `query_cidr` are allowed; otherwise return `false`.
## Notes / Constraints
- IPv4 addresses are 32-bit.
- CIDR masks are between `/0` and `/32`.
- Aim for an approach that is more efficient than enumerating every IP in the queried CIDR range.
Quick Answer: This question evaluates a candidate's competency in IP address and CIDR arithmetic, bitwise reasoning, and algorithm design within the Coding & Algorithms category, focusing on IP networking and access-control logic.