Katkat
Back

Convert an IP range to minimal CIDRs

DatabricksSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manipulate IP address representations and implement a greedy strategy to decompose an arbitrary range of IPv4 addresses into the minimum number of CIDR blocks.

Problem Statement

Given two IPv4 addresses as strings, start_ip and end_ip, representing an inclusive range of IP addresses, return the minimal list of CIDR (Classless Inter-Domain Routing) blocks that cover exactly this range. Each CIDR block should be returned as a string in the format ip/prefix.

An IPv4 address is a 32-bit integer. A CIDR block x.x.x.x/n represents a range of 2^(32-n) consecutive IP addresses, where the first n bits are fixed. A valid CIDR block of size 2^k must start at an address where the last k bits are zero.

Function Signature

def get_minimal_cidrs(start_ip: str, end_ip: str) -> List[str]:

Example

Input: start_ip = "192.168.0.0", end_ip = "192.168.0.5"

Output: ["192.168.0.0/30", "192.168.0.4/31"]

Explanation:

  • 192.168.0.0/30 covers 192.168.0.0 to 192.168.0.3 (4 addresses).
  • 192.168.0.4/31 covers 192.168.0.4 to 192.168.0.5 (2 addresses).
  • Total range covered: 192.168.0.0 to 192.168.0.5.

Constraints

  • start_ip and end_ip are valid IPv4 strings.
  • start_ip <= end_ip.

Edge Cases

  • The range consists of a single IP address.
  • The range covers an entire subnet (e.g., 0.0.0.0 to 255.255.255.255).

Hints

Hint 1

Convert the IPv4 strings into 32-bit unsigned integers to simplify numerical comparisons and range calculations.

Hint 2

At each step, find the largest CIDR block that fits within your remaining range, starting at the current address, without exceeding the target end address.

Hint 3

The maximum size of a CIDR block starting at `current_ip` is determined by the number of trailing zeros in its binary representation and the remaining distance to the `end_ip`.

Follow-up questions

  • How would you modify your solution if the input was an IPv6 address range?
  • What is the time complexity of your solution in terms of the number of bits (32)?
  • How would you efficiently validate if an arbitrary input CIDR block is contained within the original requested range?