Similar to convert JSON file to objects, we can covert hierarchical list to a nested object. The input is like a table of content with multiple levels, the output is a nested object obj.children[1].children[2]. “obj” is the top level object. Each nested object’s level maps with the level in the hierarchy list. You can access any object from top object “obj”.
Tree data structure is a hierarchy data structure. From root, you can access any node in the tree. Using the same concept, we define a “Node”. It is like a TreeNode, in which there are links to its children”. The top object “obj” can be regarded as the root of the tree. When reading each item in the hierarchy list, it is like adding a node in a tree. To keep track the position where to add, we define two variables “prev” and “parent”. “pre” keeps track the previous added node’s level. “parent” keeps track the upper level node. It starts from root. By comparing the level of the new item with “prev”, we can decide where to add new object.
Microsoft Interview Question:
Design a data structure which reads below block of text
*Status update1
**Joe is working on a bug
**Alice is on vacation
*StatusUpdate2
**Alex finished task1
and returns me an Object such that I can navigate this nested text easily like this:
obj.children[0] – > returns “StatusUpdate”
obj.children[0].children[1] -> “Alice is on vacation”
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 68 69 70 71 72 73 74 75 76 77 78 | import java.io.IOException; import java.util.List; import java.util.ArrayList; class StatusNode { String status; List<StatusNode> children=new ArrayList<>(); StatusNode(){}; StatusNode(String s) { status=s; } void addChild(StatusNode st) { children.add(st); } public String toString() { return status; } } public class ConvertHierarchyToNestedObject { static int pre; static StatusNode parent; //Build object, Time O(n), Space O(1) static StatusNode readDataAndCreateObj(String[] input) { StatusNode root = new StatusNode(); StatusNode curr = root; parent = root; pre = 0; for (String strLine: input) { int level = strLine.lastIndexOf("*"); String st = strLine.substring(level + 1); StatusNode node = new StatusNode(st); curr = addNode(curr, node, level); } return root; } //Utility function to add child, Time O(1) Space O(1) static StatusNode addNode(StatusNode curr, StatusNode node, int level) { if (level == pre) { curr.addChild(node); } else if (level > pre) { parent = curr; int last = curr.children.size() - 1; curr = curr.children.get(last); curr.addChild(node); } else if (pre > level) { curr = parent; curr.addChild(node); } pre = level; return curr; } public static void main(String[] args) throws IOException { String[] input = { "*Status update1", "**Joe is working on a bug", "**Alice is on vacation", "*Status Update2", "**Alex finished task1"}; StatusNode obj = readDataAndCreateObj(input); //print all status in object for (int i = 0;i < obj.children.size(); i++) { System.out.println(obj.children.get(i).status); for (int j = 0; j < obj.children.get(i).children.size(); j++) { System.out.println(" " + obj.children.get(i).children.get(j).status); } } //print first two System.out.println("\nobj.children[0] – > "+obj.children.get(0)); System.out.println("obj.children[0].children[1] -> "+obj.children.get(0).children.get(1)); System.out.println(); } } |
Output:
Status update1
Joe is working on a bug
Alice is on vacation
Status Update2
Alex finished task1
obj.children[0] – > Status update1
obj.children[0].children[1] -> Alice is on vacation
O Notation:
Time complexity: O(n)
Space complexity: O(1)
Download ConvertHierarchyToNestedObject.java
Build hierarchy tree
