cswork / libraryOpen practice workspace

Coding questions · Databricks

Find first CIDR block covering IP

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:

  • 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.

Find First CIDR Block Covering an IP

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

Example 1

Input: ("192.168.1.5", ["10.0.0.0/8", "192.168.1.0/24", "192.168.0.0/16"])
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.

Example 2

Input: ("10.1.2.3", ["10.0.0.0/8", "10.1.2.0/24"])
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.

Hints

  1. Convert each IPv4 address into a 32-bit integer so prefix comparisons become simple bit operations.
  2. For a CIDR prefix length x, build a mask with x leading 1 bits. Two addresses are in the same block if their masked values are equal.