Katkat
Back

Implement IPv4 and CIDR iterators

OpenAISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate IP address bit-representations and implement a custom iterator to traverse all addresses within a given CIDR block.

Problem Statement

Implement an IPv4Iterator class that takes a CIDR string (e.g., "192.168.1.0/24") and generates all IPv4 addresses within that range in ascending order.

An IPv4 address consists of four 8-bit octets (totaling 32 bits). A CIDR block consists of an IP address and a prefix length n, representing the range of addresses where the first n bits are fixed.

Requirements

Implement the following methods:

  • __init__(self, cidr_string): Parses the CIDR block and initializes the iterator state.
  • __next__(self): Returns the next IPv4 address in the range as a string (e.g., "192.168.1.1"), or raises StopIteration when no more addresses remain.

Examples

# Input: "192.168.1.0/30"
# Output: "192.168.1.0", "192.168.1.1", "192.168.1.2", "192.168.1.3"

# Input: "10.0.0.0/32"
# Output: "10.0.0.0"

Constraints

  • n (prefix length) will be between 0 and 32.
  • You must handle the full range of IPv4 addresses.
  • Efficiency: The iterator should use constant extra space O(1) (excluding the string representation of the IP).

Edge Cases

  • Prefix length 0 (covers all possible IPv4 addresses).
  • Prefix length 32 (contains only one address).
  • Invalid input strings.

Hints

Hint 1

Convert the IP address into a 32-bit unsigned integer to simplify range arithmetic.

Hint 2

Use bitwise shifting and masking to calculate the network base (start) and the broadcast address (end) based on the prefix length.

Hint 3

Maintain a cursor that increments from the start address until it exceeds the calculated broadcast address.

Follow-up questions

  • How would you modify your implementation to check if a specific IP address exists within a provided CIDR block in O(1) time?
  • How would you handle IPv6 addresses, which require 128-bit representations?
  • If the iterator was used in a distributed system, how would you partition the CIDR block to allow multiple workers to process segments of the range in parallel?