0

IPv4 range iterator with reverse and CIDR support

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: IPv4 range iterator with reverse and CIDR support

Companies: OpenAI

Difficulty: Medium

Problem statement

An IPv4 address such as "172.16.4.9" is four octets, each 0 to 255. Taken together, the octets form one unsigned 32-bit number.

Build iterators that walk IPv4 addresses lazily, one at a time. The full address space has more than 4 billion entries, so you must not build a list of them.

Part 1: forward iterator

Implement an iterator built from a starting address. It returns that address, then each next address in order, and ends after 255.255.255.255.

  • Support has_next() -> bool and next() -> str. In Python, __iter__/__next__ are fine too.
  • Raise ValueError for a malformed address. A valid address has exactly four parts, and each part is a decimal number from 0 to 255.

Example: starting at "172.16.4.254", the first three calls to next() return "172.16.4.254", "172.16.4.255", "172.16.5.0". Starting at "255.255.255.254", the iterator returns two addresses and then has_next() is False.

Part 2: reverse iterator

Add an iterator that walks downward from a starting address and ends after 0.0.0.0.

Example: starting at "172.16.5.1", it returns "172.16.5.1", "172.16.5.0", "172.16.4.255", and so on.

Part 3: CIDR blocks

A CIDR block "base/p" (with 0 <= p <= 32) contains every address whose first p bits match the first p bits of base. Iterate over all addresses in a block in either direction. You may also be given a start address inside the block.

Example: "172.16.4.0/30" contains 172.16.4.0 through 172.16.4.3. Forward from "172.16.4.2" it returns "172.16.4.2", "172.16.4.3". In reverse with no start address, it returns .3, .2, .1, .0.

Part 4: discussion

Give the time and space cost of each operation. Explain how your design behaves on very large blocks, such as /8 or /0.

Approach

Key idea: an IPv4 address is a 32-bit unsigned integer. A.B.C.D is A·2^24 + B·2^16 + C·2^8 + D. Once you convert to an integer, "the next address" is +1, and carries between octets (10.0.0.255 to 10.0.1.0) happen on their own. You convert back to dotted form only when you return a value.

Naive version (mention it, then move on). Keep four octets and increment the last one, carrying into the octet to its left when one passes 255. This works, but the carry logic is easy to get wrong, and it gets worse for the reverse direction and for CIDR blocks. The integer version removes all of it.

Do not build a list. From 0.0.0.0 the range has 2^32 (about 4.3 billion) addresses. The iterator must be lazy: it stores one cursor and computes each address when asked. That gives O(1) memory whatever the range size.

One iterator class for every part. The iterator holds three values: next (the value to return next), stop (the last value to return, inclusive), and step (+1 or -1).

  • Part 1 (forward): start up to 255.255.255.255 with step +1.
  • Part 2 (reverse): start down to 0.0.0.0 with step -1.
  • Part 3 (CIDR): a block base/p covers the addresses whose top p bits equal the top p bits of base. The mask is 0xFFFFFFFF << (32 - p), cut to 32 bits. The first address is base & mask, and the last is first | ~mask. Then reuse the same iterator over [first, last], in either direction, starting anywhere inside the block.

Invariant. has_next() is true exactly when next has not passed stop in the walking direction. The last address is the edge case. After returning 255.255.255.255, next becomes 2^32. After returning 0.0.0.0, it becomes -1. Python integers do not overflow, so these values simply mean "done". In a language with fixed-width integers, you would need a separate done flag or a 64-bit cursor. A 32-bit unsigned counter would wrap to 0 and loop forever.

Parsing. Reject anything that is not four ASCII decimal octets in 0..255. That includes empty parts, signs, spaces, and more than three digits. For CIDR, the prefix length must be 0..32. A host bit set in the base (10.0.0.7/30) is normalized away by the mask. Say this choice out loud: some interviewers want it rejected instead.

Code

from __future__ import annotations

from typing import Iterator

MAX_IP = (1 << 32) - 1


def ip_to_int(ip: str) -> int:
    parts = ip.split(".")
    if len(parts) != 4:
        raise ValueError(f"bad IPv4 address: {ip!r}")
    value = 0
    for part in parts:
        # Rejects "", "-1", "+1", " 1", non-ASCII digits, and "0001".
        if not (part.isascii() and part.isdigit()) or len(part) > 3 or int(part) > 255:
            raise ValueError(f"bad IPv4 address: {ip!r}")
        value = (value << 8) | int(part)
    return value


def int_to_ip(value: int) -> str:
    return ".".join(str((value >> shift) & 0xFF) for shift in (24, 16, 8, 0))


class IPRangeIterator:
    """Lazily yields addresses from start to stop (inclusive), stepping +1 or -1."""

    def __init__(self, start: int, stop: int, step: int = 1) -> None:
        if step not in (1, -1):
            raise ValueError("step must be 1 or -1")
        self._next = start   # the next value to return
        self._stop = stop    # last value to return (inclusive)
        self._step = step

    def __iter__(self) -> IPRangeIterator:
        return self

    def has_next(self) -> bool:
        if self._step == 1:
            return self._next <= self._stop
        return self._next >= self._stop

    def __next__(self) -> str:
        if not self.has_next():
            raise StopIteration
        value = self._next
        self._next += self._step   # may step to 2**32 or -1: that just means "done"
        return int_to_ip(value)


def forward(start_ip: str) -> IPRangeIterator:
    """Part 1: start_ip, start_ip + 1, ..., 255.255.255.255."""
    return IPRangeIterator(ip_to_int(start_ip), MAX_IP, 1)


def reverse(start_ip: str) -> IPRangeIterator:
    """Part 2: start_ip, start_ip - 1, ..., 0.0.0.0."""
    return IPRangeIterator(ip_to_int(start_ip), 0, -1)


def parse_cidr(cidr: str) -> tuple[int, int]:
    """Return (first, last) address of a block like '10.0.0.0/30'."""
    ip, sep, length = cidr.partition("/")
    if not sep or not length.isdigit() or int(length) > 32:
        raise ValueError(f"bad CIDR: {cidr!r}")
    prefix = int(length)
    mask = (MAX_IP << (32 - prefix)) & MAX_IP   # prefix=0 gives mask 0
    first = ip_to_int(ip) & mask                # clear host bits: '10.0.0.7/30' -> 10.0.0.4
    last = first | (~mask & MAX_IP)
    return first, last


def cidr_iter(cidr: str, start_ip: str | None = None, reverse_order: bool = False) -> IPRangeIterator:
    """Part 3: every address in the block, optionally starting at start_ip inside it."""
    first, last = parse_cidr(cidr)
    if start_ip is None:
        begin = last if reverse_order else first
    else:
        begin = ip_to_int(start_ip)
        if not first <= begin <= last:
            # Outside the block: the range is empty in the direction we walk.
            return IPRangeIterator(1, 0, 1)
    if reverse_order:
        return IPRangeIterator(begin, first, -1)
    return IPRangeIterator(begin, last, 1)


def cidr_size(cidr: str) -> int:
    first, last = parse_cidr(cidr)
    return last - first + 1

Complexity

  • ip_to_int / int_to_ip: O(1). The input is a fixed 4 octets.
  • Creating any iterator (forward, reverse, cidr_iter): O(1) time and O(1) space. Nothing is precomputed.
  • has_next() / __next__(): O(1) each. Walking k addresses costs O(k) time and O(1) extra space, apart from the strings you return.
  • cidr_size: O(1). It is 2^(32 - p), so you never count by iterating.

Test cases

  • forward("255.255.255.253") yields 255.255.255.253, 255.255.255.254, 255.255.255.255, and then stops.
  • forward("10.0.0.254"), first three values: 10.0.0.254, 10.0.0.255, 10.0.1.0 (the carry into the third octet).
  • forward("255.255.255.255") yields exactly one value. After it, has_next() is False (no wraparound to 0.0.0.0).
  • reverse("0.0.0.1") yields 0.0.0.1, 0.0.0.0, and then stops (no wraparound to 255.255.255.255).
  • reverse("10.0.1.0"), first two values: 10.0.1.0, 10.0.0.255 (a borrow across octets).
  • cidr_iter("192.168.1.7/30") yields 192.168.1.4 to 192.168.1.7. The host bits in the base are masked off.
  • cidr_iter("192.168.1.0/30", "192.168.1.2") yields 192.168.1.2, 192.168.1.3.
  • cidr_iter("192.168.1.0/30", reverse_order=True) yields .3, .2, .1, .0.
  • cidr_iter("192.168.1.0/30", "192.168.1.9") is empty, because the start is outside the block.
  • cidr_iter("8.8.8.8/32") yields only 8.8.8.8. cidr_size("0.0.0.0/0") is 4294967296, and its iterator starts at 0.0.0.0 without allocating anything.
  • Invalid input raises ValueError: "1.2.3", "256.0.0.1", "1.2.3.-1", "1..2.3", "a.b.c.d", "1.2.3.4.5", "1.2.3.4/33", "1.2.3.4" passed as a CIDR.

Follow-ups

  • Arbitrary end address or step size. Pass stop and any nonzero step. has_next already compares by direction. With |step| > 1, check next <= stop before you add the step, not after.
  • Range to minimal CIDR list (LeetCode 751 style). Given start and a count n, cover exactly those addresses with the fewest blocks. At each point, the largest block that can start at x has size x & -x, the lowest set bit (for x = 0 it is 2^32). Halve it until it is <= remaining, emit the block, then advance. This is O(32) blocks and O(32) work per block.
  • Iterate over many CIDR blocks or a list of ranges, merged and without duplicates. Convert each block to [first, last], sort, merge overlapping or adjacent intervals, then chain one IPRangeIterator per merged interval. Memory is O(number of blocks), not O(number of addresses). For a lazy stream of sorted blocks, a heap merge gives the same result.
  • Exclusions or "is this IP allowed?" queries. Store merged intervals in a sorted array and binary-search them, which is O(log m) per query. For longest-prefix match, use a binary trie on the 32 bits. Mention that ipaddress.ip_network exists in the standard library, but interviewers usually want the bit math.
  • IPv6. The same design works with 128-bit integers. Python handles them natively, but in other languages you need two 64-bit words. Output formatting (:: compression) becomes the hard part. Laziness matters even more, because one /64 is 2^64 addresses.

Interviewer expectations

Mid-level (L4)

  • Converts between dotted and integer forms correctly with shifts and masks, and keeps the iterator lazy.
  • Handles the 255.255.255.255 end (and 0.0.0.0 in reverse) without wrapping around or raising too early.
  • Writes has_next/next (or the Python iterator protocol) and tests a carry across an octet.

Senior (L5)

  • Uses one parameterized iterator for forward, reverse, and CIDR instead of three copies.
  • Gets the CIDR mask right for /0 and /32, and states how host bits in the base are handled.
  • Validates input strictly and explains why a 2^32-element list is not an option.

Staff (L6+)

  • Raises fixed-width overflow (uint32 wraparound) for other languages and designs the stop condition to avoid it.
  • Extends the design cleanly to range-to-CIDR, merged multi-range iteration, and IPv6, with bounds on memory per block.
  • Discusses API choices: inclusive vs. exclusive bounds, empty vs. error for an out-of-block start, and thread safety if one iterator is shared.

Sign in to comment, vote or remix.