Massive Algorithms: June 2015

big-o/RotatingIterator.java at master · kowshik/big-o

big-o/RotatingIterator.java at master · kowshik/big-o
* Implement a rotating iterator. The iterator accepts an array list of
* iterators, and iterates over them column-wise.
* * i.e If the following iterators are passed:
* * iterator_1 => [1] iterator_2 => [2, 3] iterator_3 => [4, 5]
* * Then the rotating iterator returns the following elements in sequential * order:
* * 1, 2, 4, 3, 5.
public class RotatingIterator<T> implements Iterator<T> {

private final ArrayList<Iterator<T>> iterators;
private int rotatingIndex;
private T nextItem;

public RotatingIterator(ArrayList<Iterator<T>> iterators) {
this.iterators = iterators;
this.rotatingIndex = 0;
}

@Override
public boolean hasNext() {
if (nextItem != null) {
return true;
}

int count = 0;
boolean itemFound = false;
while (!itemFound && count < iterators.size()) {
Iterator<T> iterator = iterators.get(rotatingIndex);
if (iterator != null && iterator.hasNext()) {
nextItem = iterator.next();
// we need this because nextItem can possibly be null.
itemFound = true;
}

rotatingIndex++;
rotatingIndex %= iterators.size();
count++;
}

return count != iterators.size();
}

@Override
public T next() {
if (!hasNext()) {
throw new NoSuchElementException();
}

T toReturn = nextItem;
nextItem = null;
return toReturn;
}

@Override
public void remove() {
throw new UnsupportedOperationException();
}

}
Read full article from big-o/RotatingIterator.java at master · kowshik/big-o

Merge iterator

Design Pattern 总结

public interface Iterator {
  /**
   * @return True if the there is a next element
   */
  boolean hasNext();
  /**
   * @return next Highest number and removes the items from the stream.
   */
  int getNextHighestNumber();
 }

class MergedIterator {
    List<Iterator> _listIters;
    PriorityQueue<Pair<?,?>> maxHeap;
  /**
   * Construct MergedIterator.
   * @param iterators list of iterator
   */
  MergedIterator(List<Iterator> iterators) {
      if (iterators == null || iterators.size() <= 0) throw new Exception("");
     _listIters = iterators;
     maxHeap = new PriorityQueue<Pair<Int, Iterator>, >(new MyCompartor());
     for (Iterator iter: _listIters) {
          if (iter.hasNext())
              maxHeap.insert(new Pair(iter.getNextHighestNumber(), iter));
      }
  }

  /**
   * @return true if there is a next element.
   */
  boolean hasNext() {
    return maxHeap.size() > 0;
 }

  /**
   * @return next max element across all the iterators.
   */
  int getNextHighestNumber() {
      if (!hasNext()) throw new Exception("Empty");
      Pair pair = maxHeap.pop();
      int num = pair.getFirst();
      Iterator iter = pair.getSecond();
      if (iter.hasNext())
        maxHeap.insert(new Pair(iter.getNextHighestNumber(), iter));
      return num;

  }

}

Read full article from Design Pattern 总结

Design a deep iterator

Related: LeetCode 341 - Flatten Nested List Iterator
Design a deep iterator - 包子IT面试培训
Alis: Nested Iterator
Write a deep iterator to iterate through a list of objects or integer which could be another list or integer. For example, this collection contains Integer or another collection. L means it is a collection that contains either integer or another L.

----> 5

---- 3 -> 4 -> L -> 6

1 -> 2 -> L -> 7-> 8

We would expect an iterator to loop through it will print out 1, 2, 3, 4, 5, 6, 7, 8

Key: stack of iterator.
In java, the idiom of iterator is that u always call hasNext before next.
==>So in next(), there is no need to call hasNext(), which just causes worse performance.
https://github.com/kowshik/big-o/blob/master/java/src/collections/DeepIterator.java
public class DeepIterator<T> implements Iterator<T> {
// A reference to the item which will be returned during
// the next call to next().
private T nextItem;
private final Stack<Iterator<?>> stack = new Stack<Iterator<?>>();

public DeepIterator(Collection<?> collection) {
if (collection == null) {
throw new NullPointerException("Can't iterate over a null collection.");
}
stack.push(collection.iterator());
}

@Override
@SuppressWarnings("unchecked")
public boolean hasNext() {
if (nextItem != null) {
return true;
}

while (!stack.isEmpty()) {
Iterator<?> iter = stack.peek();
if (iter.hasNext()) {
Object item = iter.next();
if (item instanceof Collection<?>) {
stack.push(((Collection<?>) item).iterator());
} else {
nextItem = (T) item;
return true;
}
} else {
stack.pop();
}
}

return false;
}

@Override
public T next() {
if (hasNext()) { // change to if(nextItem!=null)
T toReturn = nextItem;
nextItem = null;
return toReturn;
}

throw new NoSuchElementException();
}

@Override
public void remove() {
throw new UnsupportedOperationException();
}
}

public class DeepIterator implements Iterator {
    private Stack iteratorStack = new Stack();
    private Integer top = null;

    public DeepIterator(Iterable iterable){
        this.iteratorStack.push(iterable.iterator());
    }

    @Override
    public boolean hasNext() {
        if(this.top != null) return true;

        while(!this.iteratorStack.isEmpty()) {
            Iterator tmpIterator = this.iteratorStack.peek();

            if(tmpIterator.hasNext()){
                Object tmp = tmpIterator.next();
                if(tmp instanceof Integer){
                    this.top = (Integer) tmp;
                    return true;
                } else if(tmp instanceof Iterable){
                    this.iteratorStack.push(((Iterable) tmp).iterator());
                } else {
                    throw new RuntimeException("Unsupported data type. ");
                }
            } else {
                this.iteratorStack.pop();
            }
        }
        return false;
    }

    @Override
    public Integer next() throws NoSuchElementException {
        if(hasNext()){
            Integer tmp = this.top;
            this.top = null;
            return tmp;
        }

        throw new NoSuchElementException();
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("This is not supported right now.");
    }
}

http://dongfeiwww.com/design/pattern/2014/07/23/design-pattern/

    public boolean hasNext() {
       if (itrs.isEmpty()) {
           return false;
       }
       Iterator<Object> curIter = itrs.peek();
       while (curIter.hasNext()) {
           Object nextObj = curIter.next();
           if (obj instanceof ArrayList) {
               if ((ArrayList(obj)).size() == 0) { //
                   continue;
               } else {
                   itrs.push((ArrayList(obj)).iterator()); // not needed to use recrusive
                   return hasNext();
               }
           } else {
               curValue = (Object)nextObj;
               return true;
           }
           
       }
       itrs.pop();
       return hasNext();
    }

http://www.mitbbs.com/article_t/JobHunting/32583985.html
http://buttercola.blogspot.com/2015/11/linkedin-deep-iterator.html

eg: {{1,2},3,{4,{5,6}}}
不断调用iterator的next()返回的序列是 1 2 3 4 5 6
这个data structure的interface是这样的

public interface Data<T> {
    // Does this Data hold a collection?
    public boolean isCollection();
    // Returns the collection contained by     // this Data, or null if it is a single element
    public Collection<Data<T>> getCollection();
    // Returns the single element contained     //by this Data, or null if it is  collection
    public T getElement();
}

public class DeepIterator implements Iterator<Data> {

    private Stack<Iterator<Data>> stack = new Stack<>();

    private Data top = null;

    public DeepIterator(List<Data> input) {

        stack.push(input.iterator());

}

    @Override

    public boolean hasNext() {

        if (this.top != null) {

            return true;

}

        while (!stack.isEmpty()) {

            Iterator<Data> it = stack.peek();

            if (it.hasNext()) {

                Data curr = it.next();

                if (!curr.isCollection()) {

                    top = curr.getElement();

                    return true;

                } else {

                    stack.push(curr.getCollection.iterator());

}

            } else {

                stack.pop();

}

}

        return false;

}

    @Override

    public Integer next() {

        if (top != null) {

            Integer result = top;

            top = null;

            return result;

        } else {

            return null;

}

}

}

第1题：level sum，算是deep iterator的变种。一个多重nested array，例如{a,{b,c
},{{d},e}}，返回level sum = a + 2 * (b + c) + 3 * d + 2 * e。
Read full article from Design a deep iterator - 包子IT面试培训

big-o/RotatingIterator.java at master · kowshik/big-o

Merge iterator

Design a deep iterator

Labels

Popular Posts