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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
import java.util.LinkedList; import java.util.Stack; class Task { String name; int level; Task(String n, int l) { name = n; level = l; } } public class ConvertFlatToHierarchy { //O(n) O(n) static void process (String[] lines) { Task task; Stack<Task> stack = new Stack<Task>(); String output; int count = 0; LinkedList<String> res = new LinkedList<String>(); for (int i=0;i<lines.length;i++) { String line = lines[i]; String[] str = line.split(","); String action = str[1].trim(); if (action.equals("start")) { String name = str[0]; task = new Task(name,count); stack.push(task); count ++; } else if (action.equals("end")) { int lastLevel = Integer.MAX_VALUE; task = stack.pop(); count--; StringBuilder sb = new StringBuilder(); for (int j = 0; j < count; j++) sb.append("\t"); output = sb.toString() + task.name; int currLevel = task.level; if (currLevel == 0 ) res.addFirst(output); else { LinkedList<String> list = new LinkedList<String>(); if (currLevel >= lastLevel) list.addLast(output); else list.addFirst(output); if (stack.peek().level == 0) { while (list.size() > 0) { res.addLast(list.getFirst()); list.removeFirst(); } } } lastLevel = currLevel; if (stack.size()==0) { for(String s : res) System.out.println(s); res.clear(); } } } } public static void main(String[] args) { String[] s={ "main, start", "foo, start", "foo, end", "bar, start", "bar, end", "main, end", "main2, start", "main2, end"}; process(s); } } |
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
