Bird
Raised Fist0

Iterator Pattern - Traversal Without Exposing Internal Structure

LLDeasyInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Iterator Pattern - Traversal Without Exposing Internal Structure
40 min · medium
medium

Design a collection traversal system using the Iterator pattern to allow clients to traverse elements without exposing the internal data structure. The system must support multiple collection types (e.g., List, Set), allow concurrent safe iteration, and enable extensibility for new collection types without modifying existing code.

Given Info
  • Collections can be heterogeneous (e.g., List, Set) with different internal structures.
  • Iterator must provide a uniform interface to traverse elements sequentially.
  • Internal structure of collections must remain encapsulated; no direct access.
  • Support concurrent iteration with fail-fast behavior on structural modification.
  • Extensibility: new collection types can be added without changing existing iterators.
📋
Guided Steps
1/5
Step 1
Define the Iterator Interface
Design the Iterator interface that declares traversal methods. Consider Java interface constraints and method signatures.
💡 Hint
Use interface because Iterator defines behavior without state; Java interfaces cannot hold instance fields.
Key Decision
Use Java interface Iterator<E> with methods boolean hasNext() and E next() - interface chosen because it cannot hold state but defines traversal behavior.
Interviewer Expectation
Mid: Names Iterator pattern and interface usage. Senior: Explains interface cannot hold instance fields in Java, so state is maintained in concrete iterator classes.
⚠️Common Wrong Answer
Using abstract class for Iterator interface leads to unnecessary inheritance and inability to implement multiple interfaces, reducing flexibility.
Step 2
Implement Concrete Iterator Classes
Implement concrete iterator classes for different collection types that maintain iteration state internally.
💡 Hint
Use abstract class or concrete class to hold iteration state like current index or cursor; interface cannot hold state in Java.
Key Decision
Concrete iterator classes hold private iteration state fields (e.g., int cursor) and implement Iterator interface; state must be instance variables, not static or interface fields.
Interviewer Expectation
Mid: Implements Iterator interface with stateful classes. Senior: Explains why state must be instance fields and how concurrency affects iteration state visibility.
⚠️Common Wrong Answer
Storing iteration state in static fields causes shared state across threads, leading to incorrect iteration results and race conditions.
Step 3
Encapsulate Collection Internal Structure
Design collection classes to provide Iterator instances without exposing internal data structures.
💡 Hint
Use method public Iterator<E> iterator() returning concrete iterator; collection internal fields remain private.
Key Decision
Collections expose public Iterator<E> iterator() method returning new concrete iterator instance; internal data structures are private fields (composition) inaccessible externally.
Interviewer Expectation
Mid: Uses Iterator pattern to hide internal structure. Senior: Explains composition relationship and lifecycle ownership - iterator depends on collection but collection encapsulates data.
⚠️Common Wrong Answer
Returning internal data structure directly (e.g., exposing internal array) breaks encapsulation and allows clients to modify collection state unsafely.
Step 4
Implement Fail-Fast Behavior for Concurrent Modification
Ensure iterators detect concurrent modifications and throw ConcurrentModificationException.
💡 Hint
Use a volatile modCount field in collection and check it in iterator methods to detect structural changes.
Key Decision
Collection maintains volatile int modCount incremented on structural changes; iterator captures expectedModCount at creation and compares before each next()/hasNext(), throwing ConcurrentModificationException if mismatch.
Interviewer Expectation
Mid: Describes fail-fast behavior concept. Senior: Explains volatile ensures visibility of modCount changes across threads and how iterator detects concurrent modification precisely.
⚠️Common Wrong Answer
Not using volatile modCount leads to visibility issues where iterator misses concurrent modifications, causing inconsistent iteration without exceptions.
Step 5
Support Extensibility for New Collection Types
Design the system so new collection types can be added without modifying existing iterator or collection code.
💡 Hint
Use interface segregation and programming to interface; new collections implement Iterable<E> and provide their own iterator implementations.
Key Decision
Collections implement Iterable<E> interface; clients use Iterable interface to obtain Iterator, enabling Open/Closed Principle - new collections added without modifying existing code.
Interviewer Expectation
Mid: Names Open/Closed Principle and interface segregation. Senior: Explains how Java Iterable interface enables extensibility and decouples client code from concrete collection implementations.
⚠️Common Wrong Answer
Hardcoding collection types in client code violates Open/Closed Principle and requires modifying existing code to add new collections.
🔌
API Design Challenge
Design an API that allows clients to traverse different collection types uniformly without exposing internal data structures, supports fail-fast concurrent iteration, and enables adding new collection types without modifying existing code.
Hints
  • Use Java's Iterable<E> interface to provide a standard iterator() method.
  • Implement fail-fast behavior using a volatile modCount field and expectedModCount in iterators.
  • Design iterator interfaces and concrete classes to encapsulate iteration state and support multiple concurrent iterators.
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Iterator interface with hasNext() and next() methods
  • Concrete iterator classes holding iteration state as instance fields
  • Collections encapsulating internal data structures with private fields
  • Fail-fast mechanism using volatile modCount and expectedModCount
  • Collections implementing Iterable<E> for extensibility
Good to Have - 30%
  • Use of ConcurrentModificationException for fail-fast behavior
  • Explanation of composition relationship and lifecycle ownership
  • Discussion of thread visibility guarantees provided by volatile
  • Separation of traversal logic from collection storage (Single Responsibility Principle)
Bonus - 10%
  • Support for multiple concurrent iterators on same collection
  • Use of final keyword for immutable iterator fields
Anti-patterns to Avoid
Using abstract class for Iterator interface reduces flexibility and violates Java multiple inheritance constraints, limiting ability to implement multiple interfaces and increasing coupling.
Storing iteration state in static fields causes race conditions and incorrect iteration results because state is shared across all iterator instances and threads.
Exposing internal data structures breaks encapsulation and allows unsafe modifications, leading to unpredictable collection state and bugs.
Not using volatile for modCount leads to visibility issues where iterator misses concurrent modifications, causing inconsistent iteration without exceptions.
✅
Model Answer
▼ Reveal

This design uses the Iterator pattern to provide a uniform way to traverse heterogeneous collections without exposing their internal structures. Java interfaces define traversal behavior without state, while concrete iterator classes maintain iteration state as private instance fields. Collections encapsulate their data and expose iterators via the Iterable interface. Fail-fast behavior is implemented using a volatile modCount field in collections and expectedModCount in iterators to detect concurrent modifications. The design supports extensibility by allowing new collection types to implement Iterable and provide their own iterators without modifying existing code.

Key Decisions
  • Use Java interface Iterator<E> to define traversal methods without holding state, as interfaces cannot have instance fields.
  • Implement concrete iterator classes with private instance fields (e.g., cursor) to maintain iteration state safely per iterator instance.
  • Encapsulate collection internal data structures as private fields and expose only iterator() method returning new iterator instances.
  • Maintain a volatile int modCount in collections incremented on structural changes; iterators capture expectedModCount at creation and compare before each operation to detect concurrent modifications.
  • Collections implement Iterable<E> interface to allow clients to use polymorphic iteration and enable adding new collection types without modifying existing code.
  • Iterator<E> interface defines traversal methods without holding state, leveraging Java interface constraints.
  • Concrete iterator classes hold iteration state as private instance fields, enabling multiple concurrent iterators.
  • Collections encapsulate internal data structures as private fields (composition), exposing only iterator() method.
  • Fail-fast behavior implemented using volatile modCount field in collections and expectedModCount in iterators to detect concurrent modifications.
  • Collections implement Iterable<E> interface to support extensibility and polymorphic iteration.
  • Use of ConcurrentModificationException to signal unsafe concurrent structural changes during iteration.
  • Iterator implementations are not thread-safe by default; clients must synchronize externally if needed.
  • Avoid static fields in iterators to prevent shared mutable state and race conditions.
  • Use of final keyword for iterator fields where possible to ensure immutability of references.
  • Iterator pattern enforces Single Responsibility Principle by separating traversal logic from collection storage.

Practice

(1/5)
1. A class diagram shows a class with a private constructor and a static synchronized getInstance() method returning the single instance. Which design pattern is this, and why is it the correct choice here?
easy
A. Factory Method pattern, because it controls object creation through a static method.
B. Prototype pattern, because it clones existing instances to avoid new construction.
C. Singleton pattern, because it ensures only one instance with thread-safe lazy initialization.
D. Builder pattern, because it constructs complex objects step-by-step.

Solution

  1. Step 1: Identify the pattern from constructor and method

    The private constructor prevents external instantiation, and the static synchronized getInstance() method ensures a single instance with thread safety, matching Singleton pattern characteristics.

  2. Step 2: Eliminate other patterns

    Factory Method controls subclass instantiation, Builder separates construction from representation, Prototype clones objects; none enforce single instance with thread safety.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Private constructor + synchronized static getInstance() -> Singleton pattern [check]
Hint: Private constructor + static synchronized method -> Singleton [check]
Common Mistakes:
2. You want to add a new WeekendFeeStrategy to the existing chain of responsibility-based parking fee system. Which change respects the Open-Closed Principle (OCP) and Dependency Inversion Principle (DIP)?
medium
A. Modify the existing FeeHandler class to add weekend fee logic inside its handleRequest() method.
B. Create a subclass WeekendFeeHandler extending FeeHandler and override handleRequest() with weekend logic.
C. Create a new WeekendFeeHandler implementing the FeeStrategy interface and add it to the chain without changing existing handlers.
D. Add a boolean flag isWeekend to FeeHandler and branch logic based on it.

Solution

  1. Step 1: Understand OCP and DIP

    OCP requires extending behavior without modifying existing code; DIP requires depending on abstractions, not concretions.

  2. Step 2: Evaluate options

    Modify the existing FeeHandler class to add weekend fee logic inside its handleRequest() method. modifies existing class, violating OCP; Create a new WeekendFeeHandler implementing the FeeStrategy interface and add it to the chain without changing existing handlers. adds new handler, respecting OCP and DIP; Add a boolean flag isWeekend to FeeHandler and branch logic based on it. adds flag inside existing handler, violating OCP; Create a subclass WeekendFeeHandler extending FeeHandler and override handleRequest() with weekend logic. subclasses but may cause tight coupling and violates DIP if chain depends on concrete classes.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    New handler class added without modifying existing code [check]
Hint: Add new handler class, don't modify existing ones [check]
Common Mistakes:
3. You want to add a WeekendPermissionStrategy that changes file access permissions on weekends without modifying existing classes. Which SOLID principle guides the minimum change, and what is the correct approach?
medium
A. Single Responsibility Principle: modify the Directory class to handle weekend logic directly.
B. Liskov Substitution Principle: subclass File to override permission checks for weekends.
C. Open/Closed Principle: create a new WeekendPermissionStrategy implementing PermissionStrategy, inject it where needed.
D. Dependency Inversion Principle: invert dependencies by making Directory depend on concrete WeekendPermissionStrategy.

Solution

  1. Step 1: Identify the SOLID principle for extensibility without modification

    The Open/Closed Principle (OCP) states software entities should be open for extension but closed for modification.

  2. Step 2: Apply OCP by adding a new WeekendPermissionStrategy implementing existing PermissionStrategy interface

    This allows adding weekend-specific logic without changing existing Directory or File classes.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    New strategy class + interface -> OCP compliance [check]
Hint: Add new strategy class, don't modify existing code [check]
Common Mistakes:
4. Given a design where pricing strategies are implemented via a FeeStrategy interface, adding a WeekendFeeStrategy requires which minimal change to comply with SOLID principles?
medium
A. Modify the existing FeeStrategy implementations to include weekend logic.
B. Create a new WeekendFeeCalculator class that extends all existing fee classes.
C. Add a new WeekendFeeStrategy class implementing FeeStrategy without changing existing classes.
D. Add a boolean isWeekend flag to FeeStrategy interface and implement conditionals in all classes.

Solution

  1. Step 1: Identify applicable SOLID principle

    The Open-Closed Principle (OCP) requires classes to be open for extension but closed for modification.

  2. Step 2: Evaluate options for minimal change and OCP compliance

    Adding a new class implementing FeeStrategy (Add a new WeekendFeeStrategy class implementing FeeStrategy without changing existing classes.) is ideal, but if the design requires weekend logic in all strategies, adding a flag and conditionals violates OCP by modifying all classes.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Adding flag and conditionals modifies existing classes -> violates OCP ✗
Hint: OCP: extend via new class, avoid modifying existing ones [check]
Common Mistakes:
5. ElectricCar needs to use ChargingSpots in the parking lot system. What is the minimum change to the current design to support this without modifying existing classes?
hard
A. Add a flag in ParkingLot to treat ElectricCars differently and hardcode charging spot logic.
B. Modify Vehicle class to add a boolean isElectric field and add logic in ParkingSpot to check it.
C. Create a new ElectricCar class and a new ChargingSpot class, then modify ParkingLot to handle both explicitly.
D. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility map externally.

Solution

  1. Step 1: Identify extensibility without modifying existing classes

    Adding new enum values and subclasses allows extension without changing existing class code, preserving OCP.

  2. Step 2: Update compatibility externally

    Updating SpotCompatibility map outside existing classes avoids modifying their code and prevents class explosion or god-class logic.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Extend enums + subclass + external compatibility update -> minimal change [check]
Hint: Extend enums and subclasses, update compatibility externally [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard