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 an IPv4 Range Iterator | OpenAI Coding Question

Implement an IPv4 Range Iterator

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a class that iterates through IPv4 addresses across multiple inclusive ranges. Each range is given as a pair of IPv4 addresses in dotted-decimal format, such as `(10.0.0.1, 10.0.0.3)`. The input may contain multiple ranges. Build an iterator that returns every individual IP address in ascending order. Requirements: - `constructor(ranges)`: initialize the iterator from a list of ranges. - `has_next() -> bool`: return whether another IP address is available. - `next() -> string`: return the next IP address in ascending order. You may assume each range is valid and inclusive. If helpful, you may first normalize the input by sorting ranges and merging any overlapping or adjacent intervals. Follow-up: - Represent IPv4 addresses internally as unsigned 32-bit integers. - Explain how to convert between dotted-decimal strings and integers using bit operations. - Discuss the time and space complexity of your design.

Quick Answer: This question evaluates implementing iterative data structures and range-handling algorithms alongside numeric representation of IPv4 addresses and bit-level conversions between dotted-decimal strings and 32-bit integers.

Implement the core logic of an IPv4 range iterator. Since this platform evaluates a function rather than a class, write `solution(ranges, operations)` that simulates the iterator. Each range is given as a pair `(start_ip, end_ip)` of IPv4 addresses in dotted-decimal format, and each range is inclusive. The input may contain multiple ranges in any order. The iterator must return every individual IP address covered by the ranges in ascending numeric order. Overlapping or adjacent ranges should behave like one continuous range after normalization. Your function should process the operations in order: - `"has_next"` -> append `True` or `False` to the result - `"next"` -> append the next IPv4 address string to the result Assume all ranges are valid, and `"next"` is never called when no IP address remains. Follow-up expectations: - Represent IPv4 addresses internally as unsigned 32-bit integers. - Convert `a.b.c.d` to an integer with bit operations: `(a << 24) | (b << 16) | (c << 8) | d`. - Convert back by using right shifts and masking with `255`.

Constraints

1 <= len(operations) <= 200000
0 <= len(ranges) <= 200000
Each IPv4 address is valid and in the range 0.0.0.0 to 255.255.255.255
Each range is inclusive and satisfies start_ip <= end_ip numerically
The total number of IPs represented by the ranges may be much larger than len(operations), so do not expand all addresses eagerly

Examples

Input: ([('10.0.0.3', '10.0.0.5'), ('10.0.0.1', '10.0.0.2')], ['has_next', 'next', 'next', 'next', 'next', 'next', 'has_next'])

Expected Output: [True, '10.0.0.1', '10.0.0.2', '10.0.0.3', '10.0.0.4', '10.0.0.5', False]

Explanation: The two ranges are adjacent after sorting, so they merge into one continuous range from 10.0.0.1 to 10.0.0.5.

Input: ([('192.168.1.12', '192.168.1.13'), ('192.168.1.10', '192.168.1.11')], ['next', 'next', 'has_next', 'next', 'next'])

Expected Output: ['192.168.1.10', '192.168.1.11', True, '192.168.1.12', '192.168.1.13']

Explanation: The ranges are adjacent and normalize into 192.168.1.10 through 192.168.1.13.

Input: ([], ['has_next', 'has_next'])

Expected Output: [False, False]

Explanation: With no ranges, the iterator is empty from the beginning.

Input: ([('0.0.0.0', '0.0.0.0'), ('0.0.0.0', '0.0.0.1')], ['has_next', 'next', 'next', 'has_next'])

Expected Output: [True, '0.0.0.0', '0.0.0.1', False]

Explanation: The ranges overlap and merge into 0.0.0.0 through 0.0.0.1.

Input: ([('255.255.255.254', '255.255.255.255'), ('255.255.255.255', '255.255.255.255')], ['next', 'has_next', 'next', 'has_next'])

Expected Output: ['255.255.255.254', True, '255.255.255.255', False]

Explanation: This checks correct handling of the highest IPv4 values and overlapping ranges.

Input: ([('1.1.1.1', '1.1.1.2'), ('1.1.1.4', '1.1.1.4')], ['next', 'next', 'has_next', 'next', 'has_next'])

Expected Output: ['1.1.1.1', '1.1.1.2', True, '1.1.1.4', False]

Explanation: The ranges are separate, so the iterator must skip the gap and continue with the next merged interval.

Hints

Comparing IPv4 strings lexicographically is not enough. Convert each address to a 32-bit integer first.
Sort the intervals, merge overlaps or adjacent ranges, then keep a pointer to the current interval and current IP so each operation is O(1) after preprocessing.

Quick Overview

This question evaluates implementing iterative data structures and range-handling algorithms alongside numeric representation of IPv4 addresses and bit-level conversions between dotted-decimal strings and 32-bit integers.