Implement custom iterator classes

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).

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Solution

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.

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:

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.

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.

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:

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:

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:

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.