PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCoaches

Quick Overview

This question evaluates proficiency in IPv4 address representation and arithmetic, CIDR parsing, iterator API design for forward and backward traversal, and performance-aware algorithms and data structures for range enumeration.

  • medium
  • OpenAI
  • Coding & Algorithms
  • Software Engineer

Implement an IPv4 Iterator

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement an iterator over IPv4 addresses. Start with a basic version: 1. Given a start IPv4 address and an end IPv4 address, support forward iteration over every address in the inclusive range. 2. Extend the iterator to support backward iteration as well. 3. Extend the input format so the iterator can be created from a CIDR block such as `192.168.1.0/24`, and still support both forward and backward traversal. 4. Discuss or implement optimizations to improve time and space complexity, especially avoiding materializing all IP addresses in memory. You may assume valid IPv4 strings in dotted-decimal notation. Be prepared to explain the core data representation, iterator APIs such as `hasNext`, `next`, `hasPrev`, and `prev`, and edge cases around boundaries.

Quick Answer: This question evaluates proficiency in IPv4 address representation and arithmetic, CIDR parsing, iterator API design for forward and backward traversal, and performance-aware algorithms and data structures for range enumeration.

Part 1: Implement forward iteration over an inclusive IPv4 address range

Given two IPv4 addresses `start_ip` and `end_ip` in dotted-decimal notation, return every IPv4 address in the inclusive range from `start_ip` to `end_ip` in forward order. Treat IPv4 addresses as 32-bit unsigned integers under the hood. If `start_ip` is numerically greater than `end_ip`, return an empty list.

Constraints

  • Each IPv4 string is valid dotted-decimal notation with 4 octets in `[0, 255]`.
  • If `start_ip > end_ip`, treat the range as empty and return `[]`.
  • For this problem, the number of addresses in the returned list will not exceed `10^4`.

Examples

Input: ("192.168.1.1", "192.168.1.3")

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

Explanation: Basic inclusive forward iteration.

Input: ("192.168.0.254", "192.168.1.1")

Expected Output: ["192.168.0.254", "192.168.0.255", "192.168.1.0", "192.168.1.1"]

Explanation: The range crosses an octet boundary.

Input: ("10.0.0.5", "10.0.0.5")

Expected Output: ["10.0.0.5"]

Explanation: Single-address range edge case.

Input: ("10.0.0.2", "10.0.0.1")

Expected Output: []

Explanation: If the start is greater than the end, treat it as an empty range.

Hints

  1. Convert each IPv4 address into a single 32-bit integer so that incrementing to the next IP becomes simple arithmetic.
  2. To rebuild the dotted string, extract the 4 octets using bit shifts and masks.

Part 2: Extend the iterator to support backward iteration

Implement a bidirectional IPv4 iterator over the inclusive range `[start_ip, end_ip]`. Instead of returning the full list immediately, simulate iterator API calls. The iterator uses standard cursor-between-elements semantics: the cursor starts before the first address. `hasNext()` is true if a call to `next()` would succeed. `hasPrev()` is true if a call to `prev()` would succeed. `next()` returns the address at the cursor and moves the cursor forward by 1. `prev()` moves the cursor backward by 1 and returns that address. If `next()` or `prev()` cannot move, return `None` for that operation.

Constraints

  • Each IPv4 string is valid dotted-decimal notation.
  • If `start_ip > end_ip`, treat the iterator as empty.
  • `1 <= len(operations) <= 10^5`.
  • Each operation is one of `hasNext`, `next`, `hasPrev`, or `prev`.

Examples

Input: ("192.168.1.1", "192.168.1.3", ["hasPrev", "hasNext", "next", "next", "hasPrev", "prev", "next", "next", "hasNext"])

Expected Output: [False, True, "192.168.1.1", "192.168.1.2", True, "192.168.1.2", "192.168.1.2", "192.168.1.3", False]

Explanation: After two `next` calls, `prev` returns the second element again because the cursor moves backward first, then returns that element.

Input: ("10.0.0.5", "10.0.0.5", ["hasNext", "next", "hasNext", "hasPrev", "prev", "prev"])

Expected Output: [True, "10.0.0.5", False, True, "10.0.0.5", None]

Explanation: Single-element iterator edge case.

Input: ("255.255.255.254", "255.255.255.255", ["next", "next", "next", "hasPrev", "prev"])

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

Explanation: Trying to move past the end returns `None`, but moving backward still works.

Input: ("10.0.0.2", "10.0.0.1", ["hasNext", "next", "hasPrev", "prev"])

Expected Output: [False, None, False, None]

Explanation: Reversed bounds create an empty iterator.

Hints

  1. You do not need to build the entire address list. A start integer, a size, and a cursor index are enough.
  2. Think of the cursor as sitting between elements, like a list iterator.

Part 3: Create the iterator from a CIDR block and support forward/backward traversal

Implement a bidirectional IPv4 iterator built from a CIDR block such as `192.168.1.0/24`. The iterator should include every address in the block and support the same cursor semantics as Part 2. Important: do not exclude network or broadcast addresses. If the CIDR base address is not already aligned to the prefix, first normalize it by applying the subnet mask.

Constraints

  • The CIDR prefix length is an integer in `[0, 32]`.
  • The input IPv4 string is valid dotted-decimal notation.
  • Do not exclude any addresses from the block; include all `2^(32 - prefix)` addresses.
  • `1 <= len(operations) <= 10^5`.

Examples

Input: ("192.168.1.0/30", ["hasNext", "next", "next", "next", "next", "hasNext"])

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

Explanation: A `/30` block contains exactly 4 addresses.

Input: ("10.0.0.0/31", ["next", "next", "hasNext", "hasPrev", "prev", "prev", "hasPrev"])

Expected Output: ["10.0.0.0", "10.0.0.1", False, True, "10.0.0.1", "10.0.0.0", False]

Explanation: A `/31` block contains 2 addresses, and backward traversal works with the same cursor semantics.

Input: ("8.8.8.8/32", ["hasPrev", "hasNext", "next", "next", "prev"])

Expected Output: [False, True, "8.8.8.8", None, "8.8.8.8"]

Explanation: A `/32` block contains exactly one address.

Input: ("192.168.1.5/30", ["next", "next", "next", "next"])

Expected Output: ["192.168.1.4", "192.168.1.5", "192.168.1.6", "192.168.1.7"]

Explanation: The input base is normalized to the true network start `192.168.1.4` for a `/30`.

Hints

  1. A CIDR block is just an inclusive integer interval: compute the masked network start, then derive the block size from the prefix length.
  2. Once you know the start integer and block size, the iterator logic is almost identical to Part 2.

Part 4: Optimize time and space complexity without materializing all IP addresses

You are given an IPv4 source that may represent a huge address space. The source is either an inclusive range or a CIDR block. Implement a memory-efficient query engine that answers questions about the source without building a list of all IP addresses. This is the same core representation an optimized iterator would use internally. Support these query types: - `("count",)` -> total number of addresses - `("get", index)` -> the address at 0-based position `index`, or `None` if out of bounds - `("contains", ip)` -> whether the given IP belongs to the source - `("index", ip)` -> the 0-based index of `ip` within the source, or `-1` if it is absent

Constraints

  • All IPv4 strings are valid dotted-decimal notation.
  • For `("range", start_ip, end_ip)`, if `start_ip > end_ip`, treat the source as empty.
  • For `("cidr", cidr_block)`, normalize the base address by applying the subnet mask.
  • The source may be as large as the entire IPv4 space (`/0`), so materializing all addresses is not allowed.
  • `1 <= len(queries) <= 2 * 10^5`.

Examples

Input: (("range", "192.168.1.10", "192.168.1.12"), [("count",), ("get", 0), ("get", 2), ("get", 3), ("contains", "192.168.1.11"), ("index", "192.168.1.12"), ("index", "192.168.1.9")])

Expected Output: [3, "192.168.1.10", "192.168.1.12", None, True, 2, -1]

Explanation: Basic range queries over a small interval.

Input: (("cidr", "10.0.0.0/30"), [("count",), ("get", 1), ("contains", "10.0.0.4"), ("index", "10.0.0.3")])

Expected Output: [4, "10.0.0.1", False, 3]

Explanation: A `/30` CIDR block contains 4 addresses.

Input: (("cidr", "0.0.0.0/0"), [("count",), ("get", 0), ("get", 4294967295), ("contains", "255.255.255.255"), ("index", "255.255.255.255")])

Expected Output: [4294967296, "0.0.0.0", "255.255.255.255", True, 4294967295]

Explanation: This demonstrates why you must not build the entire address list in memory.

Input: (("range", "10.0.0.5", "10.0.0.4"), [("count",), ("get", 0), ("contains", "10.0.0.5"), ("index", "10.0.0.5")])

Expected Output: [0, None, False, -1]

Explanation: Reversed bounds create an empty source.

Input: (("cidr", "192.168.1.5/30"), [("get", 0), ("get", 3), ("contains", "192.168.1.4"), ("index", "192.168.1.7")])

Expected Output: ["192.168.1.4", "192.168.1.7", True, 3]

Explanation: The CIDR base is normalized to the actual network start before answering queries.

Hints

  1. Reduce any source to an inclusive integer interval `[lo, hi]` and answer every query with arithmetic on that interval.
  2. `get(index)` and `index(ip)` are inverse operations when the address lies inside the interval.
Last updated: May 4, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Simulate Infection Spread on a Grid - OpenAI (hard)
  • Implement Social Follow Recommendations - OpenAI (medium)
  • Build a Compose Rating Card - OpenAI (medium)
  • Generate Data Labeling Schedules - OpenAI (medium)
  • Convert IPv4 Ranges to CIDR Blocks - OpenAI (medium)