algoadvance

Given an Iterator class interface with methods: next() and hasNext():

• next() returns the next element in the iteration.
• hasNext() returns true if there are more elements in the iteration.

Design a PeekingIterator that supports the peek() operation, which essentially returns the next element in the iteration without advancing the iterator. Implement the PeekingIterator class:

• PeekingIterator(Iterator iterator) Initializes the object with the given iterator iterator.
• next() should return the next element in the sequence.
• peek() should return the next element in the sequence without advancing the iterator.
• hasNext() should return true if there are more elements in the sequence.

Example:

iter = PeekingIterator(Iterator([1, 2, 3]))
iter.next()    # returns 1
iter.peek()    # returns 2
iter.next()    # returns 2
iter.next()    # returns 3
iter.hasNext() # returns False

Clarifying Questions

1. What should happen if peek() or next() is called when there are no more elements?
   • Assume that calling next() when there are no more elements will result in an error, as per the typical behavior of iterators.
   • Similarly, peek() should also result in an error if there are no more elements.
2. Will the input iterator always contain elements of a specific type?
   • Assume that the elements are all integers.

Strategy

1. Initialization:
   • Store the given iterator.
   • Utilize a variable (_next_element) to keep track of the next element and a boolean (_has_next) that indicates if the next element has been loaded.
2. peek():
   • Return _next_element if _has_next is True.
3. next():
   • Return _next_element.
   • Update _next_element with the next element from the iterator if it exists.
4. hasNext():
   • Return _has_next.

Code

Here’s the implementation of the PeekingIterator class:

class PeekingIterator:
    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        self.iterator = iterator
        self._next_element = None
        self._has_next = False

        if self.iterator.hasNext():
            self._next_element = self.iterator.next()
            self._has_next = True

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        return self._next_element

    def next(self):
        """
        :rtype: int
        """
        if not self._has_next:
            raise StopIteration("No more elements in the iterator")

        current_element = self._next_element
        if self.iterator.hasNext():
            self._next_element = self.iterator.next()
        else:
            self._has_next = False
            self._next_element = None

        return current_element

    def hasNext(self):
        """
        :rtype: bool
        """
        return self._has_next

Time Complexity

• __init__(): O(1)
• peek(): O(1)
• next(): O(1)
• hasNext(): O(1)

This ensures that all operations are efficient and run in constant time.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?