How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at OpenAI during technical interviews.

Implement IPv4 and CIDR iterators | OpenAI Coding Question

Implement IPv4 and CIDR iterators

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem: IPv4 / CIDR Iterator You are building utilities to iterate through IPv4 addresses. ### Definitions - An IPv4 address is in dotted decimal form: `a.b.c.d`, where each octet is `0..255`. - A CIDR block is `ip/prefixLen`, e.g. `192.168.1.0/24`, where `prefixLen` is `0..32`. ### Tasks Implement functions/classes to support: 1. **Ascending iteration of a single IPv4 address** - Given an IPv4 address string, return the **next** IPv4 address (i.e., add 1 to the 32-bit value with carry across octets). - Define behavior when the input is `255.255.255.255` (e.g., error, wrap, or return null) and be consistent. 2. **Descending iteration of a single IPv4 address** - Given an IPv4 address string, return the **previous** IPv4 address (subtract 1 from the 32-bit value with borrow across octets). - Define behavior when the input is `0.0.0.0`. 3. **Iteration over a CIDR block** - Given a CIDR string like `10.0.0.0/30`, produce an iterator (or list/stream) of all IPv4 addresses in that block. - Specify ordering (ascending is typical). - Clarify whether you include the network and broadcast addresses; implement accordingly. ### Examples - `next("1.2.3.4") -> "1.2.3.5"` - `next("1.2.3.255") -> "1.2.4.0"` - `prev("1.0.0.0") -> "0.255.255.255"` - For `"192.168.1.0/30"`, the block size is 4 addresses; iterate all addresses in that range. ### Constraints / Notes - Assume valid input formatting unless you choose to add validation. - Aim for O(1) work per `next()`/`prev()` step and O(1) extra space (besides the output).

Quick Answer: This question evaluates understanding of IPv4 addressing and CIDR notation, along with competency in binary/bitwise arithmetic, iterator construction, and edge-case handling for address boundaries.

Part 1: Next IPv4 Address

Given a valid IPv4 address in dotted decimal form, return the next IPv4 address in ascending order. Adding 1 should carry across octets when needed. For example, incrementing the last octet of `1.2.3.255` should produce `1.2.4.0`. If the input is the maximum possible IPv4 address, `255.255.255.255`, return `None`.

Constraints

The input is guaranteed to be a valid IPv4 address.
Each octet is an integer in the range 0 to 255.
Your algorithm should use O(1) extra space.

Examples

Input: "1.2.3.4"

Expected Output: "1.2.3.5"

Explanation: Simple increment without carry.

Input: "1.2.3.255"

Expected Output: "1.2.4.0"

Explanation: The last octet overflows and carries into the third octet.

Input: "10.0.255.255"

Expected Output: "10.1.0.0"

Explanation: Carry may ripple across multiple octets.

Input: "0.0.0.0"

Expected Output: "0.0.0.1"

Explanation: Lowest normal case.

Input: "255.255.255.255"

Expected Output: None

Explanation: There is no next IPv4 address after the maximum value.

Hints

Treat the address like a 4-digit number in base 256.
Work from right to left and stop once you increment an octet that is not 255.

Part 2: Previous IPv4 Address

Given a valid IPv4 address in dotted decimal form, return the previous IPv4 address in descending order. Subtracting 1 should borrow across octets when needed. For example, decrementing `1.0.0.0` should produce `0.255.255.255`. If the input is the minimum possible IPv4 address, `0.0.0.0`, return `None`.

Constraints

The input is guaranteed to be a valid IPv4 address.
Each octet is an integer in the range 0 to 255.
Your algorithm should use O(1) extra space.

Examples

Input: "1.2.3.5"

Expected Output: "1.2.3.4"

Explanation: Simple decrement without borrow.

Input: "1.0.0.0"

Expected Output: "0.255.255.255"

Explanation: Borrow ripples across three octets.

Input: "0.0.1.0"

Expected Output: "0.0.0.255"

Explanation: Borrow from the third octet into the last octet.

Input: "10.0.0.0"

Expected Output: "9.255.255.255"

Explanation: Borrow can affect multiple octets and reduce a higher octet.

Input: "0.0.0.0"

Expected Output: None

Explanation: There is no previous IPv4 address before the minimum value.

Hints

This is the reverse of addition with carry: think in terms of borrow in base 256.
Process octets from right to left until you find one that is greater than 0.

Part 3: Iterate All IPv4 Addresses in a CIDR Block

Given a CIDR block string such as `"192.168.1.0/30"`, return a list of every IPv4 address in that block in ascending order. Include both the network address and the broadcast address. If the IP portion is not already the network address, first normalize it by applying the CIDR mask. For example, `"10.0.0.5/30"` belongs to the block starting at `10.0.0.4`, so the returned list should begin there.

Constraints

The input is guaranteed to be a valid CIDR string.
The block size will not exceed 65536 addresses.
Include both network and broadcast addresses in the output.
You may assume the result fits in memory.

Examples

Input: "192.168.1.0/30"

Expected Output: ["192.168.1.0", "192.168.1.1", "192.168.1.2", "192.168.1.3"]

Explanation: A /30 block contains 4 total addresses.

Input: "10.0.0.5/30"

Expected Output: ["10.0.0.4", "10.0.0.5", "10.0.0.6", "10.0.0.7"]

Explanation: The IP is normalized to the network address 10.0.0.4 before iteration.

Input: "0.0.0.0/32"

Expected Output: ["0.0.0.0"]

Explanation: A /32 block contains exactly one address.

Input: "255.255.255.254/31"

Expected Output: ["255.255.255.254", "255.255.255.255"]

Explanation: A /31 block contains exactly two addresses.

Hints

Convert the IPv4 address to a 32-bit integer so masking and iteration are easier.
The block size of a `/p` network is `2^(32-p)`.

Quick Overview

This question evaluates understanding of IPv4 addressing and CIDR notation, along with competency in binary/bitwise arithmetic, iterator construction, and edge-case handling for address boundaries.