Katkat
Back

Determine allow/deny for an IP via CIDR rules

DatabricksSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently manage and query hierarchical IP address ranges, requiring knowledge of bitwise operations and data structures for range matching.

Problem Description

Design an IP Access Control List (ACL) system that determines whether a given IPv4 address should be allowed or denied based on a set of CIDR rules. A rule consists of an IP prefix (e.g., 192.168.1.0/24) and an action (ALLOW or DENY).

Rules have precedence: if an IP matches multiple CIDR blocks, the rule with the longest prefix length (the most specific match) takes priority. If two rules have the same prefix length, the first rule added to the system takes precedence.

Requirements

Implement a class IPAccessController with the following methods:

  • add_rule(cidr: str, action: str): Adds a rule to the system. cidr is in standard IP/mask format. action is either 'ALLOW' or 'DENY'.
  • check_ip(ip: str) -> str: Returns 'ALLOW' or 'DENY' based on the rules. If no rule matches, return 'DENY' by default.

Constraints

  • IPv4 addresses consist of 4 octets (0-255).
  • cidr prefix length ranges from 0 to 32.
  • The system should handle up to 100,000 rules.
  • The check_ip method should be optimized for performance, ideally better than O(N) where N is the number of rules.

Example

acl = IPAccessController()
acl.add_rule("10.0.0.0/8", "DENY")
acl.add_rule("10.1.0.0/16", "ALLOW")

# check_ip("10.1.5.5") -> "ALLOW" (more specific match)
# check_ip("10.2.5.5") -> "DENY" (only 10.0.0.0/8 matches)

Edge Cases

  • Overlapping ranges.
  • /0 CIDR blocks (matching everything).
  • Duplicate rules.

Hints

Hint 1

Convert the IPv4 string into a 32-bit integer for efficient bitwise manipulation.

Hint 2

A CIDR range `A.B.C.D/N` can be represented by a base integer and a mask that preserves the first N bits.

Hint 3

Consider using a Trie or a similar prefix-based data structure to store the bits of the IP addresses, where each node stores the rule information.

Follow-up questions

  • How would your system change if you needed to support IPv6 addresses, which are 128 bits long?
  • If the rule list is updated very frequently (high write throughput), how would you maintain the performance of the `check_ip` lookups?
  • How can you detect if a new rule is completely shadowed by an existing, more specific rule?