IP to CIDR

IP to CIDR

1. What is this problem about?

The IP to CIDR interview question is a networking and bit manipulation challenge. You are given a starting IPv4 address and a number of required IPs n. Your goal is to represent this range of n addresses using the minimum possible number of CIDR (Classless Inter-Domain Routing) blocks. For example, a range of 4 IPs might be represented by one /30 block.

2. Why is this asked in interviews?

Companies like Airbnb and Databricks ask the IP to CIDR coding problem to test a candidate's mastery of Bit Manipulation and numeric bases. It evaluations your understanding of binary masks and the ability to work with large integers ($2^{32}$). It’s a test of how you convert a domain-specific problem (networking) into a generic algorithmic optimization task.

3. Algorithmic pattern used

This problem follows the Greedy Bitmasking pattern.

1. Conversion: Convert the string IP address to a 32-bit long integer.
2. Greedy Steps: While $n > 0$:
   • Find the largest power of 2 that divides the current IP address. This is the "trailing zeros" in binary (e.g., if the last 3 bits are 0, you can use a block of size $2^3 = 8$).
   • The block size must also be $\leq n$.
   • Calculate the CIDR prefix: 32 - log2(blockSize).
   • Update $n$: n -= blockSize.
   • Update IP: currentIP += blockSize.

4. Example explanation

IP: 255.0.0.7, $n = 10$.

1. ...00111. Largest power of 2 that divides it is $2^0=1$.
   • Block: 255.0.0.7/32. $n = 9$, IP = .8.
2. ...01000. Largest power of 2 is $2^3=8$.
   • Block size 8 is $\leq n(9)$.
   • Block: 255.0.0.8/29. $n = 1$, IP = .16.
3. ...10000. Largest power 2 is 16, but $n=1$.
   • Use block size 1.
   • Block: 255.0.0.16/32. $n=0$. Result: three CIDR blocks.

5. Common mistakes candidates make

• String Manipulation: Trying to solve it by parsing string dots, which is much harder than using a 32-bit integer.
• Over-allocating: Using a block size larger than $n$, which covers more IPs than requested.
• Logarithm logic: Errors in converting block size to the CIDR prefix number (e.g., size 4 is /30, not /2).

6. Interview preparation tip

Practice finding the "Lowest Set Bit" using the x & -x trick. In this problem, lowbit = currentIP & -currentIP tells you the maximum possible block size for the current address. This is a vital Bit Manipulation interview pattern.