Implement custom iterator classes
Company: Coinbase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Question
In a blank coding environment (no IDE assistance, no autocomplete), implement an iterator abstraction entirely from scratch. The interviewer typically asks for this in Java, but the same exercise generalizes to any language with an explicit iterator protocol.
1. **Define the iterator interface manually.** Write the `Iterator` interface yourself (do not import the language's built-in one). At minimum it should expose `hasNext()` (is there another element?) and `next()` (return the next element and advance).
2. **Implement two concrete iterator classes** that implement your interface. For example, one that iterates over a simple backing collection (array or list), and a second one with different traversal semantics (such as a range/generator-style iterator, or one composed over another iterator).
3. **Satisfy three follow-up sub-problems.** During the round the interviewer adds three incremental requirements on top of the basic iterators — typically additional traversal features (e.g. `peek()` without advancing, a `remove()` operation, filtering, or flattening/concatenating multiple iterators) or performance/laziness guarantees (e.g. O(1) `next()`, lazy evaluation, no full-collection copy).
4. **Write runnable unit tests from scratch** that validate each iterator and each follow-up requirement, including edge cases (empty collection, single element, exhausting the iterator, calling `next()` past the end).
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Implement custom iterator classes states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Solution
# Solution Alignment
The improved prompt asks for a structured answer that states assumptions, covers edge cases, and explains trade-offs. The answer below preserves the original solution content while making the expected interview coverage explicit.
## Interview Framing
- Start by restating the goal and the assumptions you need.
- Work through the main approach in the same order as the prompt.
- Call out trade-offs, edge cases, and validation steps before finalizing the recommendation.
## Detailed Answer
##### Approach
This is an object-oriented design exercise, not an algorithms puzzle. The interviewer is watching whether you can define a clean interface and back it with correct, well-encapsulated implementations under "blank editor" conditions. Keep state minimal, advance lazily, and make the contract of each method explicit.
##### 1. Define the iterator interface manually
Write your own interface rather than reaching for `java.util.Iterator`:
```java
public interface MyIterator<T> {
boolean hasNext(); // true if next() will return an element
T next(); // return current element and advance; throw if none
}
```
Contract: `next()` must throw `NoSuchElementException` when called after the sequence is exhausted, and `hasNext()` must be safe to call any number of times without side effects.
##### 2. Two concrete iterator classes
**(a) Array/list iterator** — the straightforward case. Hold a reference to the backing data and a cursor index.
```java
public class ListIterator<T> implements MyIterator<T> {
private final List<T> data;
private int idx = 0;
public ListIterator(List<T> data) { this.data = data; }
public boolean hasNext() { return idx < data.size(); }
public T next() {
if (!hasNext()) throw new NoSuchElementException();
return data.get(idx++);
}
}
```
**(b) Range iterator** — a lazy iterator that holds no backing collection, only `[current, end, step)`. This demonstrates that an iterator is a *protocol*, not a wrapper around storage.
```java
public class RangeIterator implements MyIterator<Integer> {
private int cur;
private final int end, step;
public RangeIterator(int start, int end, int step) {
if (step == 0) throw new IllegalArgumentException("step must be non-zero");
this.cur = start; this.end = end; this.step = step;
}
public boolean hasNext() { return step > 0 ? cur < end : cur > end; }
public Integer next() {
if (!hasNext()) throw new NoSuchElementException();
int v = cur; cur += step; return v;
}
}
```
##### 3. Three follow-up sub-problems (typical variants and how to satisfy them)
The exact follow-ups vary by interviewer; the standard ones are all answerable by layering small, single-responsibility classes on top of the base interface:
- **`peek()` without advancing** — wrap an underlying iterator and buffer one element:
```java
public class PeekingIterator<T> implements MyIterator<T> {
private final MyIterator<T> it;
private boolean hasBuf = false; private T buf;
public PeekingIterator(MyIterator<T> it) { this.it = it; }
public T peek() { fill(); return buf; }
public boolean hasNext() { return hasBuf || it.hasNext(); }
public T next() {
fill(); hasBuf = false; T v = buf; buf = null; return v;
}
private void fill() {
if (!hasBuf) {
if (!it.hasNext()) throw new NoSuchElementException();
buf = it.next(); hasBuf = true;
}
}
}
```
- **Filtering iterator** — wrap an iterator + predicate; pre-fetch the next matching element lazily so `hasNext()` stays accurate:
```java
public class FilterIterator<T> implements MyIterator<T> {
private final MyIterator<T> it; private final Predicate<T> pred;
private boolean ready = false; private T nextVal;
public FilterIterator(MyIterator<T> it, Predicate<T> p) { this.it = it; this.pred = p; }
public boolean hasNext() { advance(); return ready; }
public T next() { advance(); if (!ready) throw new NoSuchElementException(); ready = false; return nextVal; }
private void advance() {
while (!ready && it.hasNext()) { T c = it.next(); if (pred.test(c)) { nextVal = c; ready = true; } }
}
}
```
- **Concatenating / flattening iterator** — given an iterator of iterators, expose them as one continuous sequence, advancing to the next inner iterator only when the current one is exhausted (keeps `next()` amortized O(1) and avoids copying everything into one list).
- **`remove()` / O(1) guarantees / lazy evaluation** — if asked for mutation, add `remove()` to the interface and have the list iterator delete the last-returned element; for performance, point out that all the wrappers above are lazy (no full materialization) and that each `next()` does O(1) work amortized.
The key insight the interviewer rewards: each follow-up is a *small composable wrapper* over the same `MyIterator` interface, so you never rewrite traversal logic.
##### 4. Unit tests from scratch
Validate each class and each edge case. Without a test framework, plain assertions work:
```java
void testList() {
MyIterator<Integer> it = new ListIterator<>(List.of(1, 2, 3));
assert it.hasNext() && it.next() == 1;
assert it.next() == 2 && it.next() == 3;
assert !it.hasNext();
try { it.next(); assert false; } catch (NoSuchElementException ok) {}
}
void testEmpty() {
MyIterator<Integer> it = new ListIterator<>(List.of());
assert !it.hasNext();
}
void testPeek() {
PeekingIterator<Integer> p = new PeekingIterator<>(new ListIterator<>(List.of(1, 2)));
assert p.peek() == 1 && p.peek() == 1; // peek is idempotent
assert p.next() == 1 && p.next() == 2 && !p.hasNext();
}
```
Cover: normal traversal, empty input, single element, exhaustion behavior (exception past the end), and idempotent `hasNext()`/`peek()`.
## Checks and Follow-ups
- Verify that the answer addresses every requested part of the prompt.
- Identify the highest-risk assumption and explain how you would validate it.
- Be ready to discuss an alternative approach and why you did not choose it first.
Explanation
The interviewer is grading object-oriented design under no-IDE conditions: a clean hand-written Iterator interface (hasNext/next with a well-defined exhaustion contract), at least one storage-backed and one lazy/computed concrete iterator, and three follow-ups answered by composing small single-responsibility wrappers (peek, filter, concat, remove, or laziness guarantees) rather than rewriting traversal. Tests must cover empty/single/exhausted edge cases and idempotent hasNext.