Build hierarchy from Stack-like log

When the input data is a flat list, you may notice sometimes they contains the data consists of “start” and “end” pairs. Every “start” has a corresponding “stop” message, which is in a stack-like fashion. When analyzing this kind of data, it will be helpful to build hierarchy from stack-like list. So that you can visualize the hierarchy structures of the data.

To build hierarchy from stack-like list, we need two data structures – Stack and LinkedList. We read the item one by one. When reading the item with “start”, we push the item in the stack, and keep track its level. When reading the item with “stop”, we pop the item from Stack. Meanwhile, we put number of spaces before the string. This number for the spaces specifies its hierarchy level. Then save the string to a LinkedList. This LinkedList will be the output as hierarchy view of original input data. To keep the data in insert order, we use another LinkedList to temporary hold the items. we can insert data either at the front or at the end of the list based on its hierarchy level.

Amazon Interview Question(CareerCup):
Input like method stack trace: “main, start”, “foo, start”, foo, end”, “bar, start”, “bar end”, “main, end”, “main2, start”, “main2, end”. Output String, such as the following format, to indicate the order in which the method was called and the hierarchy.
main
   Foo
   Bar
main2

Java Code:

Output:
main
  foo
  bar
main2

O Notation:
Time complexity is O(n)
Space complexity is O(n)

Note:
If you have any questions or want to put comments, please post at youtube. I will answer you!
The code displayed here is the simplified version after the enhancement in the 2nd edition of Java coding interview pocket book. Please click the top download button to download the original version.

Actionable:
Download ProcessLogWithStack.zip
Watch process log with stack tutorial
Build hierarchy tree

Comments are closed