Tags » Iterator

341. Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list — whose elements may also be integers or other lists. 265 more words

Leetcode

The Travails of Traversal

The venerated foreach-loop may seem to have formed a part of PHP from the outset, but it actually entered the language starting with PHP 4, apparently appropriated from Perl. 1,708 more words

PHP

Chapt 16. The Standard Template Library

16.1. STL: (Learn C++)

The collection of classes providing templated containers, iterator and algorithms

16.2. STL Containers: (Learn C++) 182 more words

Google - Run Length Encoding Iterator


Run length encoding就是比如aaaabbccc压缩成4a2b3c

题目给一个encoding好的string, 比如4a2b3c,要求写一个iterator来遍历原来的string.


除了iterator一般的edge case以外,这道题还需要注意一些其他的edge case,比如0a2b3c,4a0b3c

Idea就是用一个start pointer指向下一个数字,无论下一个是不是0. 如果当前的cnt用完之后,就从start开始往后找下一个不为0的数字。

class EncodingIterator implements Iterator<Character> {

  String s;
  int cnt;
  Character c;
  int start;

  public EncodingIterator(String s) {
    if (s == null || s.isEmpty()) {
      return;
    }
    this.s = s;
    while (cnt == 0) {
      int i = start;
      for (; i < s.length(); i++) {
        if (!Character.isDigit(s.charAt(i))) {
          break;
        }
      }
      if (i == s.length()) {
        return;
      }
      else {
        this.cnt = Integer.parseInt(s.substring(start, i));
        this.c = s.charAt(i);
        start = i + 1;
      }
    }
  }

  @Override
  public boolean hasNext() {
    return c != null;
  }

  @Override
  public Character next() {
    if (c == null) {
      return null;
    }
    Character result = c;
    this.cnt--;
    while (cnt == 0) {
      c = null;
      int i = start;
      for (; i < s.length(); i++) {
        if (!Character.isDigit(s.charAt(i))) {
          break;
        }
      }
      if (i == s.length()) {
        break;
      }
      else {
        this.cnt = Integer.parseInt(s.substring(start, i));
        this.c = s.charAt(i);
        start = i + 1;
      }
    }
    return result;
  }
}
面经

Google - Moving Window


给一个Iterator和一个window size, 要求Wrap这个iterator来实现一个moving window class,在call next()的时候返回moving average。


Queue

这题就不需要考虑Iterator的那些Edge case。

class MovingWindow implements Iterator<Double> {
  
  Iterator<Double> it;
  int window;
  Queue<Double> queue;
  double sum;
  
  public MovingWindow(Iterator<Double> it, int window) {
    this.it = it;
    this.window = window;
    this.queue = new LinkedList<>();
  }
  
  @Override
  public boolean hasNext() {
    return it.hasNext();
  }
  
  @Override
  public double next() {
    double curr = it.next();
    queue.offer(curr);
    sum += curr;
    if (queue.size() > window) {
      sum -= queue.poll();
    }
    return sum / window;
  }
}
面经

Google - Iterator of Iterator


Input一个list of iterator,设计一个SuperIterator。


Maintain一个current iterator

class SuperIterator<T> implements Iterator<T> {

  List<Iterator<T>> itList;
  Iterator<T> curr;
  int i;

  public SuperIterator(List<Iterator<T>> itList) {
    if (itList == null || itList.isEmpty()) {
      throw new IllegalArgumentException();
    }
    this.itList = itList;
    curr = itList.get(0);
  }

  @Override
  public boolean hasNext() {
    return curr != null && curr.hasNext();
  }

  @Override
  public T next() {
    T result;
    if (curr != null && curr.hasNext()) {
      result = curr.next();
    }
    else {
      while (i < itList.size() && !itList.get(i).hasNext()) {
        i++;
      }

      if (i < itList.size()) {
        curr = itList.get(i);
      }
      else {
        return null;
      }

      result = curr.next();
    }

    // update curr iterator
    while (i < itList.size() && !itList.get(i).hasNext()) {
      i++;
    }
    if (i < itList.size()) {
      curr = itList.get(i);
    }
    else {
      curr = null;
    }

    return result;
  }
}
面经

Google - Jump Iterator


wrap 一个iterator 使得新的iterator的next() 返回旧iterator的next().next()


没有想象中的那么简单,首先考虑一下,只有一个element的情况,hasNext()不能单纯的返回
it.hasNext()。

其次edge case想清楚:
1. 连续的hasNext()
2. 连续的next()
3. 第一次先call next()
4. 连续call next()值得最后一个,然后call hasNext()

当然还有最普通的case,
while (hasNext()) {
System.out.println(next())
} 119 more words

面经