How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms 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.

Evaluate ACL rules for IP and CIDR | Databricks Coding Question

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.

Part 1: Determine Whether a Single IPv4 Address Is Allowed by an ACL

You are given an ordered IPv4 access-control list (ACL). Each rule is a pair (action, cidr), where action is either ALLOW or DENY, and cidr is an IPv4 CIDR block such as 192.168.1.0/24. A request for a single IPv4 address is handled by the first rule whose CIDR contains that address. - If that first matching rule is ALLOW, return True. - If that first matching rule is DENY, return False. - If no rule matches, return False. Write a function that determines whether a given IPv4 address is allowed.

Constraints

0 <= len(rules) <= 200000
Each action is either ALLOW or DENY
Each IP address is a valid IPv4 address
Each CIDR has a mask length from /0 to /32
Default behavior is deny if no rule matches

Examples

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

Expected Output: True

Explanation: The first rule already matches 10.1.2.3 and allows it. The later DENY rule is ignored.

Input: ([('DENY', '192.168.1.0/24'), ('ALLOW', '192.168.1.42/32')], '192.168.1.42')

Expected Output: False

Explanation: The IP matches the first rule, which is DENY, so the request is denied.

Input: ([('ALLOW', '10.0.0.0/8')], '11.0.0.1')

Expected Output: False

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

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

Expected Output: True

Explanation: The /0 CIDR contains every IPv4 address.

Input: ([], '1.2.3.4')

Expected Output: False

Explanation: An empty ACL means no rule matches, so the IP is denied.

Hints

Convert an IPv4 address into a 32-bit integer so containment checks become numeric range checks.
Because the ACL uses first-match-wins semantics, you should stop scanning as soon as you find the first matching rule.

Part 2: Determine Whether Every IP in a Query CIDR Is Allowed

You are given the same ordered IPv4 ACL as in Part 1. Each rule is a pair (action, cidr), where action is ALLOW or DENY. Now the query is not a single IP address, but a CIDR block query_cidr. Return True only if every IPv4 address inside query_cidr would be allowed by the ACL under the same first-match-wins semantics. Important rules: - For each individual IP, only the first matching ACL rule matters. - If the first matching rule is ALLOW, that IP is allowed. - If the first matching rule is DENY, that IP is denied. - If no rule matches an IP, that IP is denied. You should use an approach that is more efficient than checking every IP address in the query block one by one.

Constraints

0 <= len(rules) <= 2000
Each action is either ALLOW or DENY
All IPv4 addresses and CIDR strings are valid
CIDR mask lengths are from /0 to /32
Your solution should avoid enumerating every IP in the queried CIDR range

Examples

Input: ([('ALLOW', '10.0.0.0/9'), ('ALLOW', '10.128.0.0/9')], '10.0.0.0/8')

Expected Output: True

Explanation: The two ALLOW rules together cover the entire queried /8, and no earlier DENY blocks any part of it.

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

Expected Output: False

Explanation: Addresses in 10.0.0.0/16 are denied by the first matching rule, so not every IP in the /8 is allowed.

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

Expected Output: True

Explanation: Every IP in the query matches the earlier ALLOW rule first, so the later DENY rule never applies.

Input: ([('ALLOW', '192.168.0.0/17')], '192.168.0.0/16')

Expected Output: False

Explanation: Only half of the queried /16 is allowed. The other half matches no rule and is denied by default.

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

Expected Output: True

Explanation: A single ALLOW /0 rule permits every IPv4 address, so the whole query is allowed.

Hints

Think about which parts of the query CIDR have not been matched by any earlier rule yet.
A CIDR block can be represented as one numeric interval [start, end]. Allow rules subtract coverage from the remaining interval set; deny rules fail if they touch any still-unmatched part.

Quick Overview

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.