Katkat
Back

Evaluate ACL rules for IP and CIDR

DatabricksSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate binary representations of IP addresses and perform efficient prefix matching using CIDR notation, requiring careful bitwise arithmetic and efficient lookup structures.

Problem Statement

You are building a firewall engine that evaluates incoming IP addresses against a set of Access Control List (ACL) rules. An ACL rule is defined as either a specific IP address (e.g., 192.168.1.1) or a CIDR block (e.g., 192.168.1.0/24).

Your task is to implement an ACLMatcher class that supports:

  1. add_rule(rule: str): Adds an IP or CIDR rule to the system.
  2. is_allowed(ip: str) -> bool: Returns True if the provided IP matches any of the stored rules, and False otherwise.

Constraints

  • Assume IPv4 addresses only (represented as four octets 0-255).
  • The add_rule function may be called up to 10^5 times.
  • The is_allowed function must be highly efficient, ideally better than O(N) where N is the number of rules.

Examples

# Example 1
matcher = ACLMatcher()
matcher.add_rule("10.0.0.0/8")
matcher.is_allowed("10.5.5.5") # Returns True
matcher.is_allowed("192.168.1.1") # Returns False

# Example 2
matcher.add_rule("192.168.1.5")
matcher.is_allowed("192.168.1.5") # Returns True

Edge Cases

  • A CIDR prefix of /0 (matches everything).
  • Overlapping rules (e.g., adding 10.0.0.0/8 then 10.1.0.0/16).
  • Converting string IP octets to 32-bit integers correctly.

Hints

Hint 1

Convert every IPv4 address into a 32-bit integer by treating the four octets as components of a base-256 number.

Hint 2

A CIDR block `IP/mask` defines a range; represent this as a prefix of length `mask` bits and check if the candidate IP's leading bits match that prefix.

Hint 3

Consider using a Trie (prefix tree) where each node represents a bit (0 or 1) to store the rules, allowing O(1) matching time relative to the 32 bits of an IPv4 address.

Follow-up questions

  • How would you modify your implementation to support rule removal (`remove_rule`)?
  • What changes would be necessary to support IPv6 addresses, which are 128 bits long?
  • If the number of rules is small but the number of `is_allowed` calls is massive, how would you optimize the memory footprint of your Trie?