Tag Archives: stack

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. Example 1: Given the list [[1,1],2,[1,1]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].… Read More »

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… Read More »

Get max histogram rectangle

I solved this problem one year ago. This time I solved it again and wrote some analysis for it. Problem definition: Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the… Read More »

The Maximum Volume of Trapped Rain Water

Problem description: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given the input [0,1,0,2,1,0,1,3,2,1,2,1] the return value would be 6 This problem can be solved in O(n) time, by going through from left to… Read More »

Find min sublist

This problem is given by Junmin Liu. I dicussed with him, and thought about this for 2 days, and finally came up with this the O(n) time, O(1) soluiton. Problem: Give a list of unsorted number, find the min window or min sublist of the list, such as if sublist is sorted, the whole list… Read More »