Find first CIDR block covering IP
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given:
- A single IPv4 address as a string, e.g. `"192.168.1.5"`.
- A list of CIDR blocks (IPv4), each as a string in the form `"a.b.c.d/x"`, where `0 <= a,b,c,d <= 255` and `0 <= x <= 32`.
Each CIDR block `a.b.c.d/x` represents all IP addresses whose first `x` bits are identical to the first `x` bits of the base address `a.b.c.d`.
Task:
Return the **first** CIDR block in the given list that covers (contains) the given IP address. If none of the CIDR blocks contains the IP, return some designated value such as `null` or an empty string.
Clarifications:
- "First" means the first element in the input list order that matches.
- Assume IPv4 only.
- You may assume the input strings are syntactically valid.
- Aim for an efficient solution that can handle up to, for example, 10^5 CIDR blocks.
Define clearly what you return when there is no matching CIDR.
Quick Answer: This question evaluates a candidate's understanding of IPv4 and CIDR notation, ability to perform prefix-based address containment checks using bitwise reasoning, and competence in parsing and efficient lookup across many ranges.
You are given an IPv4 address as a string and a list of IPv4 CIDR blocks. Return the first CIDR block in the given list that contains the IP address. If no block matches, return an empty string "".
A CIDR block has the form "a.b.c.d/x", where x is the prefix length. It covers all IPv4 addresses whose first x bits match the first x bits of the base address a.b.c.d.
Important: return the first matching block in the original input order, not the most specific one.
Constraints
- 0 <= len(cidr_blocks) <= 10^5
- Each IPv4 address has exactly 4 octets, and each octet is between 0 and 255
- Each prefix length x satisfies 0 <= x <= 32
- All input strings are syntactically valid IPv4 and CIDR strings
Examples
Input: ("192.168.1.5", ["10.0.0.0/8", "192.168.1.0/24", "192.168.0.0/16"])
Expected Output: "192.168.1.0/24"
Explanation: The IP does not match 10.0.0.0/8, but it does match 192.168.1.0/24. Even though it also matches 192.168.0.0/16, the first match must be returned.
Input: ("10.1.2.3", ["10.0.0.0/8", "10.1.2.0/24"])
Expected Output: "10.0.0.0/8"
Explanation: Both CIDR blocks contain the IP, but the first matching block in list order is 10.0.0.0/8.
Input: ("8.8.8.8", ["192.168.0.0/16", "10.0.0.0/8"])