Print stack trace as hierarchy – code

In an input string, there are “start” and “end” pairs. Every “start” has a corresponding “stop” message, in a stack-like fashion. We are going to parse it and print a hierarchy view of the stack trace. So that we can visualize the hierarchy structures of the data.

To build hierarchy of stack trace, we need two data structures – Stack and LinkedList. We read the line 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. Now save the string to a LinkedList. This LinkedList will be the output as hierarchy view of original input data.

However the order will be in backwards. To maintain the items in insert order, we need another LinkedList to temporary hold the items. We insert data either at the front or at the end of the list based on its hierarchy level.

Amazon Interview Question:
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)
n is number of lines in the log


Download PrintHierarchyOfNestedText.java

Comments are closed