IP to CIDR
Asked at Databricks, OpenAI
Problem
Given a start IP address and a number of IPs to cover, return the minimum list of CIDR blocks that exactly covers the range. This tests your understanding of IP addresses, subnet masks, and binary representation.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | Medium | View all Databricks questions → |
| OpenAI | Medium | View all OpenAI questions → |
How to Think About It
Key insight: convert the IP to a 32-bit integer. The CIDR block size is determined by the trailing zeros in the binary representation. A block of size 2^k covers IPs from (ip & ~(2^k-1)) to (ip & ~(2^k-1)) + 2^k - 1.
Visual walkthrough: IP "255.0.0.7" = 11111111.00000000.00000000.00000111 in binary. Trailing zeros = 0. So the smallest block is /32 (size 1). For "255.0.0.8" = ...00001000, trailing zeros = 3, so block size is 2^3 = 8 (/29 block).
Algorithm: while numIps > 0:
- Convert start IP to integer.
- Find the number of trailing zeros in start (call it tz).
- The maximum block size is 2^tz, but also limited by numIps.
- Find the largest power of 2 <= min(2^tz, numIps). Call it blockSize.
- The CIDR prefix length = 32 - log2(blockSize).
- Add the CIDR block to result.
`- Advance start by blockSize. Decrement numIps by blockSize.
Converting IP to integer: "a.b.c.d" = a2^24 + b2^16 + c*2^8 + d. Use int.from_bytes or manual bit shifting.
Converting integer to IP: shift and mask. (ip >> 24) & 0xFF, (ip >> 16) & 0xFF, etc.
The trailing zeros trick: use ip & (-ip) to isolate the lowest set bit. The block size is the minimum of this value and the remaining IPs. This avoids computing log2 manually.
Edge cases: start IP at the boundary of a block (e.g., 0.0.0.0 with trailing zeros = 32), numIps = 0 (return empty list), numIps larger than remaining block (split into multiple blocks).
Optimal Approach
Convert start IP to a 32-bit integer. While numIps > 0:
- Find the number of trailing zeros in start:
tz = trailingZeros(start). If start is 0, tz = 32. - The maximum block size from trailing zeros is
1 << tz. - The actual block size is the largest power of 2 that fits:
blockSize = min(1 << tz, largestPowerOf2 <= numIps). - Calculate prefix length:
32 - log2(blockSize). - Add
integerToIP(start)/prefixLengthto result. start += blockSize.numIps -= blockSize.
To find the largest power of 2 <= n: use n & (-n) to get the lowest set bit, or use bit_length.
Time: O(numIps) in the worst case (many /32 blocks). Space: O(1) for output.
What Trips People Up in Real Interviews
Forgetting that the block size must be a power of 2. You cannot use arbitrary sizes. The CIDR notation inherently means the block size is 2^(32-prefix). Always round down to the nearest power of 2.
Off-by-one in the prefix calculation. A block of size 2^k has prefix 32-k. So size 1 = /32, size 2 = /31, size 4 = /30, etc. Don't confuse the number of addresses with the prefix length.
Not handling the case where numIps exceeds the remaining block. If the start IP is at the boundary of a /29 block (size 8) but you only need 3 more IPs, use a smaller block that covers exactly 3 IPs (round down to power of 2).
Using floating point for log2 and getting precision errors. Use integer bit operations instead. block.bit_length() - 1 gives log2 for powers of 2. Avoid math.log2 for IP calculations.
Converting IP to integer incorrectly. The formula is a*2^24 + b*2^16 + c*2^8 + d. Don't concatenate the octets as a string and parse as integer.
Solution Code
def ipToCIDR(ip, n):
def ip_to_int(ip):
parts = list(map(int, ip.split('.')))
return (parts[0] << 24) | (parts[1] << 16) | (parts[2] << 8) | parts[3]
def int_to_ip(num):
return '.'.join(str((num >> (24 - 8 * i)) & 0xFF) for i in range(4))
def trailing_zeros(x):
if x == 0:
return 32
count = 0
while x & 1 == 0:
x >>= 1
count += 1
return count
start = ip_to_int(ip)
result = []
while n > 0:
tz = trailing_zeros(start)
max_block = 1 << tz
block = max_block
while block > n:
block >>= 1
prefix = 32 - (block.bit_length() - 1)
result.append(f"{int_to_ip(start)}/{prefix}")
start += block
n -= block
return resultFrequently Asked Questions
What is the IP to CIDR problem?
Given a start IP address and a number of IPs to cover, return the minimum list of CIDR blocks that exactly covers the range. This tests your understanding of IP addresses, subnet masks, and binary representation.
How do you solve IP to CIDR?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask IP to CIDR?
IP to CIDR is asked at Databricks, OpenAI. It is a medium difficulty problem.
What are common mistakes on IP to CIDR?
- Forgetting that the block size must be a power of 2. You cannot use arbitrary sizes. The CIDR notation inherently means the block size is 2^(32-prefix). Always round down to the nearest power of 2.
- Off-by-one in the prefix calculation. A block of size 2^k has prefix 32-k. So size 1 = /32, size 2 = /31, size 4 = /30, etc. Don't confuse the number of addresses with the prefix length.
- Not handling the case where numIps exceeds the remaining block. If the start IP is at the boundary of a /29 block (size 8) but you only need 3 more IPs, use a smaller block that covers exactly 3 IPs (round down to power of 2).
- Using floating point for log2 and getting precision errors. Use integer bit operations instead. `block.bit_length() - 1` gives log2 for powers of 2. Avoid `math.log2` for IP calculations.
- Converting IP to integer incorrectly. The formula is `a*2^24 + b*2^16 + c*2^8 + d`. Don't concatenate the octets as a string and parse as integer.