How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Databricks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

Find first CIDR block covering IP | Databricks Coding Question

Q: 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.

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"])

Expected Output: ""

Explanation: The IP does not belong to either block, so the function returns an empty string.

Input: ("203.0.113.9", ["1.2.3.4/32", "0.0.0.0/0"])

Expected Output: "0.0.0.0/0"

Explanation: A /32 block matches only one exact IP, so the first block does not match. A /0 block matches every IPv4 address.

Input: ("1.2.3.4", ["1.2.3.5/32", "1.2.3.4/32"])

Expected Output: "1.2.3.4/32"

Explanation: The first block is an exact match for a different IP, so it fails. The second block exactly matches the input IP.

Input: ("192.168.1.130", ["192.168.1.129/25"])

Expected Output: "192.168.1.129/25"

Explanation: Only the first 25 bits matter. Even though the base address is not network-aligned, both addresses share the same first 25 bits, so it matches.

Input: ("10.0.0.1", [])

Expected Output: ""

Explanation: With no CIDR blocks provided, there is no possible match.

Solution

def solution(ip, cidr_blocks):
    def ip_to_int(addr):
        value = 0
        for part in addr.split('.'):
            value = (value << 8) | int(part)
        return value

    ip_int = ip_to_int(ip)

    for cidr in cidr_blocks:
        base, prefix_str = cidr.split('/')
        prefix = int(prefix_str)
        base_int = ip_to_int(base)

        if prefix == 0:
            mask = 0
        else:
            mask = (0xFFFFFFFF << (32 - prefix)) & 0xFFFFFFFF

        if (ip_int & mask) == (base_int & mask):
            return cidr

    return ""

Time complexity: O(n), where n is the number of CIDR blocks. Space complexity: O(1).

Hints

Convert each IPv4 address into a 32-bit integer so prefix comparisons become simple bit operations.
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.

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.