Quick Overview

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.

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.

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.

Loading coding console...