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面试培训

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts