Katkat
Back

Implement an IPv4 Range Iterator

OpenAISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate 32-bit integers, understand bitwise operations, and implement a custom iterator for a contiguous range of IP addresses.

Problem Statement

An IPv4 address is represented as a string in the format "A.B.C.D", where each letter is an integer between 0 and 255. Internally, these can be represented as a single 32-bit unsigned integer by treating the address as base-256 (e.g., "192.168.0.1" = 192 * 256^3 + 168 * 256^2 + 0 * 256^1 + 1 * 256^0).

Implement an IPv4RangeIterator class that generates all IP addresses within a given CIDR range (e.g., "192.168.0.0/24").

Class Interface

class IPv4RangeIterator:
    def __init__(self, cidr: str):
        # cidr: e.g., "192.168.0.0/24"
        pass

    def has_next(self) -> bool:
        # Returns True if there are more IPs in the range
        pass

    def next(self) -> str:
        # Returns the next IP in the range as a string
        pass

Constraints

  • The subnet mask (the number after /) will be between 0 and 32.
  • You should handle the conversion efficiently without storing all addresses in memory at once.

Example

Input: IPv4RangeIterator("192.168.0.0/30")

  • next() -> "192.168.0.0"
  • next() -> "192.168.0.1"
  • next() -> "192.168.0.2"
  • next() -> "192.168.0.3"
  • has_next() -> False

Edge Cases

  • Range covering the entire IPv4 space ("0.0.0.0/0").
  • A single IP address range ("10.0.0.0/32").

Hints

Hint 1

Convert the IPv4 string to a 32-bit integer by splitting the string by '.' and shifting each octet into its respective position.

Hint 2

A CIDR mask /n means the first n bits of the IP are fixed, and the remaining (32-n) bits can vary from 0 to 2^(32-n) - 1.

Hint 3

Use a bitwise AND with a mask to determine the starting integer, and use an instance variable to track the current offset within the range.

Follow-up questions

  • How would you modify this class to support an IPv6 range iterator?
  • How would you check if an arbitrary IP address exists within this specific CIDR range in O(1) time?
  • If you needed to return the range as a list of smaller CIDR blocks (e.g., splitting a /24 into two /25s), how would you approach that?