Daily Archives: December 23, 2015

Deep Iterator

Write an Iterator that takes a nested(deep) list and flattens it out. For e.g. Collection A = {1, 2, {3, 4, 5, {6, 7}, {8,9}}, 10} When you call
DeepIterator it = new DeepIterator(A) ;
while(it.hasNext()){
System.out.println(it.next);
}

The key part of this problem is that the processed data is Collection type, which is the rawest type. It can contain anything.
We can treat it as a tree. The problem will change to traverse the leaf node in tree. So traversal a tree’s leaf node is straight forward. We can use stack to do preorder traversal.

However, we notice that a Collection has Collection.iterator(). This helps a lot. We put Iterator in stack. For each node’s children, we only store an iterator. In this way, space complexity is the deep of the tree.

check my code on github: link

Number of combination of triangle

Given an array with all positive numbers.
Find how many number of group are there which is able to make a triangle.
For example,
Given {3, 4, 5}, return 1
Given {3, 4, 5, 6}, return 4. Possible triangles are: {4, 5, 6}, {3, 5, 6}, {3, 4, 6}, {3, 4, 5}

The solution is that make 3 pointers, i<j<k. For each group of i, j, find the k position, where k is the first position at the right of j,  wherearr[i]+arr[j]<=arr[k]. In this way arr[i], arr[j], arr[[j+1, j+2,…,k-1]] can group a triangle.

Take arr={4, 5, 6, 7, 8, 9, 10} for example, the 3 pointers moving is like below:

The tricky part is that for each round of i, the k keeps moving to right, never moves back to left. We can use this to do k++ in each round of j.

check my code on github: link