IP Address / CIDR Iterator (5-part)

Given IPv4 / CIDR notation, implement parsing, range iteration, containment checks, etc. 5 parts revealed one at a time; the next part unlocks only when the previous one passes its tests. Requirements One-part-at-a-time reveal; candidates have surfaced ~5 parts. Part 4 and Part 5 are likely two branches of the same problem. Parts 1–3 ladder up on the same iterator surface: class IPV4Iterator: def __init__(self, ip_or_cidr: str, reverse: bool = False) -> None: ... # Part 1: bare IPv4 string ("a.b.c.d"); forward iterate to 255.255.255.255 then StopIteration. # Part 2: same, with reverse=True; backward iterate down to 0.0.0.0 then StopIteration. # Part 3: CIDR form ("a.b.c.d/prefix"); restrict the walk to the block # [network_address, network_address + 2**(32 - prefix) - 1], honoring `reverse`. # Forward stops at broadcast address (all host bits 1); reverse stops at network address (all host bits 0). def __iter__(self) -> 'IPV4Iterator': ... def __next__(self) -> str: ... # Raise StopIteration past the relevant boundary # (max_ip in forward, min_ip in reverse, or the CIDR-block edge). Required corner cases per part: forward: start at 0.0.0.0; start at 255.255.255.255 (stops immediately); rollover 192.168.0.255 → 192.168.1.0. reverse: start at 0.0.0.0 (stops immediately); start at 255.255.255.255; underflow 192.168.1.0 → 192.168.0.255. CIDR: respect [network, network + 2**(32-prefix) - 1]; iteration begins from the supplied seed IP (which need not be the network address) and walks inside the block only. CIDR special prefixes: /32 yields exactly one IP (the supplied address); /31 yields exactly two IPs. Examples # Part 1 forward, near the top of the space: list(IPV4Iterator("255.255.255.250")) # ["255.255.255.250", "255.255.255.251", ..., "255.255.255.255"] # Part 2 reverse, walks down to and includes 0.0.0.0: list(IPV4Iterator("0.0.0.5", reverse=True)) # ["0.0.0.5", "0.0.0.4", "0.0.0.3", "0.0.0.2", "0.0.0.1", "0.0.0.0"] # Part 3 CIDR, seed in the middle of the block — forward stops at broadcast: list(IPV4Iterator("192.168.1.5/29")) # block 192.168.1.0–.7 # ["192.168.1.5", "192.168.1.6", "192.168.1.7"] list(IPV4Iterator("192.168.1.5/29", reverse=True)) # reverse stops at network address # ["192.168.1.5", "192.168.1.4", ..., "192.168.1.0"] # Special prefixes: list(IPV4Iterator("192.168.1.100/32")) # ["192.168.1.100"] list(IPV4Iterator("10.0.0.0/31")) # ["10.0.0.0", "10.0.0.1"] Notes Extreme time pressure: hard stop enforced; only after the previous part fully passes does the next reveal. The bar emphasizes raw throughput: "engineering excellence doesn't matter — comments, edge case planning, all of it is wasted time. Make the code work + debug fast." Different question from the 'encode/decode strings' listed. The canonical IP↔CIDR decomposition is a two-line bit trick: convert each dotted-quad to a 32-bit integer; at each step pick the largest aligned block that fits, i.e. block = min(lowbit(start), largest_pow2 ≤ remaining) where lowbit(x) = x & -x. Containment and range overlap collapse to integer interval arithmetic once this conversion is in hand — most of the remaining sub-parts are wrappers around that core. Practical helpers: ip_to_int = lambda s: int.from_bytes(bytes(int(o) for o in s.split('.')), 'big') and the inverse; for CIDR, network = start_int & (~((1 << (32 - prefix)) - 1) & 0xFFFFFFFF). CIDR mask math (the exact lines) Given start_int = ip_to_int(ip) and prefix: host_bits = 32 - prefix block_size = 2 ** host_bits # /32→1, /31→2, /29→8, /24→256 network_mask = (0xFFFFFFFF << host_bits) & 0xFFFFFFFF # keep the & 0xFFFFFFFF — Python ints are unbounded network_address = start_int & network_mask # first IP, all host bits 0 broadcast_address = network_address + block_size - 1 # last IP, all host bits 1, INCLUSIVE both ends # forward: cursor = start_int, stop once cursor > broadcast_address # reverse: cursor = start_int, stop once cursor < network_address A bare (non-CIDR) string just sets the limit to the full-space edge instead: forward limit = (256 ** 4) - 1 (i.e. 255.255.255.255), reverse limit = 0. So Parts 1–3 collapse into one __next__ that compares the cursor against a single direction-dependent limit. Part 4 follow-up — step and batch surface Once Parts 1–3 are green, the most common Part 4 reveal extends the same iterator with two throughput knobs (signatures used to stay backwards-compatible with the earlier parts): class IPV4Iterator: def __init__(self, ip_or_cidr: str, reverse: bool = False, step: int = 1) -> None: ... # `step` is the integer advance per __next__ call; default 1 reproduces parts 1-3. # Raise ValueError on step <= 0; honor reverse by walking `-step` per call. def next_batch(self, size: int) -> list[str]: ... # Return up to `size` IPs from the current cursor, stopping early at the same # StopIteration boundary used by __next__. Empty list means the iterator is exhausted. next_batch is just a bounded drain of __next__: append next(self) up to size times, breaking on StopIteration — so it inherits the boundary logic for free rather than re-deriving it. Performance and the "make it faster" prompt Part 4 is often phrased as the interviewer asking "how can we make this faster / use less memory?" The baseline is already tight, so the expected answer is to name it precisely, then offer the knobs: __next__ is O(1) per call; iterating N addresses is O(N); state is O(1) (only the cursor + a couple of bounds are stored). step lets you skip (every k-th IP) without materializing the skipped ones. next_batch amortizes per-call overhead when a consumer wants chunks. Storing the cursor as a 32-bit int, not a string, is the core efficiency point — string parse/format every step is the slow path; raise it explicitly. If many iterators share a network, cache the per-CIDR derivation (network_address / broadcast_address) instead of recomputing the mask each time. For millions of addresses, a vectorized range (e.g. NumPy arange over the integer interval) beats a Python-level loop; mention it as the scaling answer. Common bugs candidates report Carry/rollover errors: forgetting that adding 1 to an octet may carry — working in 32-bit integers avoids this entirely; string-manipulation approaches often get it wrong. Off-by-one on CIDR boundary: including one too many or one too few IPs; the broadcast address is network + 2^(32-prefix) - 1, inclusive on both ends. Reverse underflow crash: not guarding current < min_ip (or < network_address) before decrementing — yields negative integers or wraps. Seed-IP assumption: assuming the input IP in CIDR form is always the network address; it need not be. The iterator starts from the supplied seed and walks to the block boundary. (If the spec instead wants the seed validated as inside the block, that's a separate guard — clarify which is intended.) Preparation Know the semantics of the ipaddress stdlib but don't lean on it (some interviewers may forbid it) Practice IPv4 ↔ int conversion, CIDR mask computation, range overlap Drill lowbit / trailing-zero-count idioms in pure Python without int.bit_length shortcuts — a recurring stuck point is choosing the wrong aligned block size when start has more trailing zeros than remaining can absorb Up front, ask two clarifying questions that change the spec: (1) do input strings need validation, and (2) must a CIDR seed IP be confirmed inside its block — both are cheap to ask and expensive to assume wrong.