📘

Detect Overlapping CIDR Blocks

MediumSystems & Infrastructure 📚 ML Systems & Infrastructure 1

Problem Statement

Before peering VPCs, check whether any two CIDR blocks overlap (which would break routing). Return whether the given set of blocks is conflict-free.

Background

Each CIDR maps to an integer address range [network_base, network_base + 2(32-prefix) - 1]** where network_base is the network address with host bits zeroed. Two ranges overlap if start1 <= end2 and start2 <= end1. The set is valid if no pair overlaps.

Your Task

def has_overlap(cidrs):

cidrs: list of "network/prefix" strings.
Return True if any two blocks overlap, else False.

Input Format

cidrs (list of str).

Output Format

A boolean.

Sample

print(has_overlap(["10.0.0.0/16", "10.0.1.0/24"]))

Output:

True

Example:

Input:

print(has_overlap(["10.0.0.0/16", "10.0.1.0/24"]))

Output:

True

Reasoning:

Convert the first CIDR 10.0.0.0/16 to an integer range. The IP 10.0.0.0 converts to the integer $167772160$ . With a prefix of 16, the block size is $2^{32-16} = 65536$ . The network base is $167772160$ (host bits are already zero), so the range is $[167772160, 167837695]$ .
Convert the second CIDR 10.0.1.0/24 to an integer range. The IP 10.0.1.0 converts to the integer $167772416$ . With a prefix of 24, the block size is $2^{32-24} = 256$ . The network base is $167772416$ , so the range is $[167772416, 167772671]$ .
Sort the ranges by their starting addresses to facilitate efficient comparison. The ranges are already in order: $[167772160, 167837695]$ followed by $[167772416, 167772671]$ .
Check for overlap between adjacent ranges. Compare the start of the second range ( $167772416$ ) with the end of the first range ( $167837695$ ). Since $167772416 \le 167837695$ , the condition for overlap is met.
The final output is True

Constraints:

Zero host bits to get the true network base.
Ranges overlap iff start1 <= end2 and start2 <= end1.
Return True if any pair overlaps.

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost DecisionMedium Minimum-Cost Job Scheduling Across Priced WindowsHard Deduplicate Retried Pipeline Runs by Idempotency KeyMedium Retry with Capped Exponential Backoff and Jitter CapMedium Critical Path Length of a Pipeline DAGMedium

1. Background Knowledge

CIDR (Classless Inter-Domain Routing) notation, written as A.B.C.D/P, defines a contiguous block of IPv4 addresses. The prefix length $P$ indicates how many leading bits are fixed for the network portion, while the remaining $32 - P$ bits are free for hosts. The total number of addresses in the block is $2^{32-P}$ . For example, 10.0.0.0/16 covers $2^{16} = 65536$ addresses, starting at the network address where all host bits are zero.

To perform arithmetic on IP addresses, you must convert the dotted-decimal string into a single 32-bit integer. This is done by treating each octet as a byte and shifting: $ip = a \cdot 2^{24} + b \cdot 2^{16} + c \cdot 2^{8} + d$ . Python’s ipaddress module or manual bit-shifting can achieve this. Once you have the integer representation, the network base is obtained by masking out the host bits: base = ip & (~((1 << (32 - prefix)) - 1)). The end address is then base + (1 << (32 - prefix)) - 1.

Two CIDR blocks overlap if and only if their integer intervals intersect. For intervals $[s_1, e_1]$ and $[s_2, e_2]$ , the overlap condition is $s_1 \leq e_2$ and $s_2 \leq e_1$ . If any pair in the set satisfies this, the configuration is invalid. This is a classic interval overlap problem, distinct from interval merging or scheduling.

2. Algorithm Approach

The core pattern is pairwise interval comparison. Since the problem asks whether any two blocks overlap, you can:

Convert each CIDR string to its integer interval $[start, end]$ .
Compare every pair of intervals using the overlap condition.
Return True immediately upon finding the first overlap (early termination).

For small to moderate input sizes, a brute-force $O(n^2)$ pairwise check is sufficient. For very large inputs, you could sort intervals by start address and use a sweep-line approach to detect overlaps in $O(n \log n)$ , but the problem’s context (VPC peering checks) typically involves a manageable number of blocks, making the simpler approach preferable for clarity.

3. Step-by-Step Strategy

👑

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.