Katkat
Back

Implement an IPv4 Iterator

OpenAISoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to handle IPv4 address arithmetic, bitwise operations, and the implementation of a stateful iterator that supports bidirectional traversal and range generation from CIDR notation.

Problem: IPv4 Iterator

Implement an IPv4RangeIterator class that generates all IP addresses within a given CIDR block (e.g., "192.168.1.0/24"). The iterator should support forward and backward traversal.

Requirements

  1. __init__(self, cidr): Parses the CIDR string and prepares the range. If the input is invalid, raise a ValueError.
  2. next(self): Returns the next IPv4 string in the sequence. Raises StopIteration if at the end.
  3. prev(self): Returns the previous IPv4 string in the sequence. Raises StopIteration if at the beginning.

Constraints

  • Use efficient memory storage (do not store all IPs in a list).
  • Represent IP addresses as 32-bit unsigned integers internally.
  • Assume input format is valid CIDR notation.

Examples

# Input: "192.168.1.254/30"
# Range: 192.168.1.252, 192.168.1.253, 192.168.1.254, 192.168.1.255

it = IPv4RangeIterator("192.168.1.254/30")
print(it.next()) # "192.168.1.252"
print(it.next()) # "192.168.1.253"
print(it.prev()) # "192.168.1.252"

Edge Cases

  • Single IP ranges (e.g., /32).
  • Full subnet ranges (e.g., /0 or /8).
  • Boundary conditions at the start and end of the calculated range.

Hints

Hint 1

Convert the IPv4 string to a 32-bit integer by splitting the octets and using bit shifts: `(o1 << 24) | (o2 << 16) | (o3 << 8) | o4`.

Hint 2

For a CIDR `x.x.x.x/n`, the number of bits to mask is `32 - n`, and the network address is determined by zeroing out the last `32 - n` bits of the integer.

Hint 3

Keep track of a `current_index` integer that increments or decrements, and convert it back to a dotted-decimal string only when returning the value.

Follow-up questions

  • How would you modify this iterator to support a list of non-contiguous CIDR blocks?
  • What changes are required to support IPv6 addresses, given they are 128-bit integers?
  • If the iterator needs to support jumping to a specific position in the range, what is the time complexity of a 'seek' operation?