Design IP/CIDR rule matcher

Q: Design IP/CIDR rule matcher

This is a Coding & Algorithms interview question from Databricks for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Design and implement a rule matcher that returns 'accept' or 'deny' for a given IPv4 address based on a set of rules. Each rule can be either an inclusive numeric IP range [start, end] or a CIDR block. Define the data structures to support addRule(rule), removeRule(rule), and query(ip), and explain how you resolve overlapping or conflicting rules (e.g., most-specific-wins, then newest-wins). Target up to 1e5 rules with low-latency queries. Analyze time and space complexity and outline tests to avoid bitwise operator-precedence bugs when parsing and comparing IP addresses. Follow-up: propose and compare data structures for efficient range and prefix checks (e.g., interval tree, segment tree, sorted disjoint intervals with binary search, ordered map, and binary/radix trie), and explain trade-offs for static vs dynamic updates.

Design IP/CIDR rule matcher

Comments (0)