Build hierarchy tree is to build a corporation hierarchy tree from an employ list. HashMap plays important role to store the data when reading the input. You can get the root by finding the employee without the manager. Starting from the root, get subordinates for each employee. Then you build tree recursively.
Here are the steps:
1. Define employee Class that has id, name and subordinates.
2.read the data line by line, store the data in the HashMap. If the employee doesn’t have managerId, he is at the top of hierarchy (root).
3. Use recursion to find subordinates and build nary tree.
4. Use recursion to print the hierarchy. The data structure tree and HashMap are used.
Amazon Interview Question:
Scan the file, it has empId, first names, last name, and reportToId.
Output a file to show the hierarchy, nobody to report to is at the top.
Input Sample:
1 2 3 4 5 6 7 8 9 10 | 1 Rob Choi 6 2 Paul Marmolejo 5 3 Lois Lemer 6 4 Christie Jacobs 5 5 Moises Medina 6 6 Joseph Grant 7 Andy Zuckeman 1 8 Melaney Partner 3 9 Cliff Gannett 5 10 Mark O'Donnell 1 |
Output Sample:
1 2 3 4 5 6 7 8 9 10 | Joseph Grant Rob Choi Andy Zuckeman Mark O'Donnell Lois Lemer Melaney Partner Moises Medina Paul Marmolejo Christie Jacobs Cliff Gannett |
Java
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 79 80 81 82 83 84 85 86 | import java.util.*; class Employee { protected int id, managerId; protected String name; protected List<Employee> subordinates; //Constructor, Time O(1), Space O(1) public Employee(String id, String name, String managerId) { this.id = Integer.parseInt(id); this.name = name; this.managerId = Integer.parseInt(managerId); } } public class BuildHierarchyTree { private Map<Integer, Employee> employees = new HashMap<>(); //stores (id, employee) pair private Employee root; //Read data and build map, Iteration, Time O(n), Space O(n), n is number of employees public void readDataAndCreateMap(String[] lines) { Employee employee = null; for (String strLine : lines) { String[] values = strLine.split(" "); if (values.length >= 4) employee = new Employee(values[0], values[1] + " " + values[2], values[3]); else employee = new Employee(values[0], values[1] + " " + values[2], "0"); employees.put(employee.id, employee); if (employee.managerId == 0) root = employee; } } //Build tree, Recursion, Time O(n), Space O(h), n is number of employees, h is levels of hierarchy tree public void buildHierarchyTree(Employee root) { Employee employee = root; List<Employee> subs = getSubsById(employee.id); employee.subordinates = subs; if (subs.size() == 0) return; for (Employee em : subs) buildHierarchyTree(em); } //Get subordinates list by given id, Time O(n), Space O(k) ~ O(n), k is number of subordinates private List<Employee> getSubsById(int managerId) { List<Employee> subs = new ArrayList<Employee>(); for (Employee em : employees.values()) { if (em.managerId == managerId) subs.add(em); } return subs; } //Print tree, Recursion, Time O(n), Space O(h) public void printHierarchyTree(Employee root, int level) { for (int i = 0; i < level; i++) System.out.print("\t"); System.out.println(root.name); List<Employee> subs = root.subordinates; for (Employee em : subs) printHierarchyTree(em, level+1); } public static void main(String[] args) { String[] lines = { "1 Rob Choi 6", "2 Paul Marmolejo 5", "3 Lois Lemer 6", "4 Christie Jacobs 5", "5 Moises Medina 6", "6 Joseph Grant", "7 Andy Zuckeman 1", "8 Melaney Partner 3", "9 Cliff Gannett 5", "10 Mark O'Donnell 1" }; BuildHierarchyTree tree = new BuildHierarchyTree(); tree.readDataAndCreateMap(lines); tree.buildHierarchyTree(tree.root); tree.printHierarchyTree(tree.root, 0); } } |
JavaScript
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 | class Employee { constructor(id, name, managerId) { this.id = id; this.name = name; this.managerId = managerId; this.subordinates = {}; } } class BuildHierarchyTree { employees = new Map(); root = null; readDataAndCreateMap(lines) { for (const strLine of lines) { var values = strLine.split(" "); var employee; if (values.length >= 4) employee = new Employee(values[0], values[1] + " " + values[2], values[3]); else employee = new Employee(values[0], values[1] + " " + values[2], "0"); this.employees.set(employee.id, employee); if (employee.managerId == 0) this.root = employee; } console.log(this.employees.size); } getSubsById(managerId) { var subs = new Array(); for (const em of this.employees.values()) { if (em.managerId == managerId) subs.push(em); } return subs; } buildHierarchyTree(root) { var employee = root; var subs = this.getSubsById(employee.id); employee.subordinates = subs; if (subs.length == 0) return; for (const em of subs) this.buildHierarchyTree(em); } printHierarchyTree(root, level) { var str = ""; for (let i = 0; i < level; i++) str += "\t"; str += root.name console.log(str); var subs = root.subordinates; for (const em of subs) this.printHierarchyTree(em, level+1); } } const lines = [ "1 Rob Choi 6", "2 Paul Marmolejo 5", "3 Lois Lemer 6", "4 Christie Jacobs 5", "5 Moises Medina 6", "6 Joseph Grant", "7 Andy Zuckeman 1", "8 Melaney Partner 3", "9 Cliff Gannett 5", "10 Mark O'Donnell 1" ]; const tree = new BuildHierarchyTree(); tree.readDataAndCreateMap(lines); tree.buildHierarchyTree(tree.root); tree.printHierarchyTree(tree.root, 0); |
Python
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 | class Employee: subordinates = [] #Constructor, Time O(1), Space O(1) def __init__(self, id, name, managerId): # constructor method self.id = id self.name = name self.managerId = managerId class BuildHierarchyTree: employees = {} root = None #Read data and build map, Iteration, Time O(n), Space O(n), n is number of employees def readDataAndCreateMap(self, lines): employee = None for strLine in lines: values = strLine.split(" ") if len(values) >=4: employee = Employee (values[0], values[1] + " " + values[2], values[3] ) else: employee = Employee (values[0], values[1] + " " + values[2], 0) self.employees[employee.id] = employee if employee.managerId == 0 : self.root = employee #Build tree, Recursion, Time O(n), Space O(h), n is number of employees, h is levels of hierarchy tree def buildHierarchyTree(self, root) : employee = root subs = self.getSubsById(employee.id) employee.subordinates = subs if len(subs) == 0: return for em in subs: self.buildHierarchyTree(em) #Get subordinates list by given id, Time O(n), Space O(k) ~ O(n), k is number of subordinates def getSubsById(self, managerId) : subs = [] for em in self.employees.values(): if em.managerId == managerId: subs.append(em) return subs #Print tree, Recursion, Time O(n), Space O(h) def printHierarchyTree(self, root, level) : for i in range(0, level, 1): print("\t", end='') print(root.name); subs = root.subordinates for em in subs: self.printHierarchyTree(em, level+1) lines = { "1 Rob Choi 6", "2 Paul Marmolejo 5", "3 Lois Lemer 6", "4 Christie Jacobs 5", "5 Moises Medina 6", "6 Joseph Grant", "7 Andy Zuckeman 1", "8 Melaney Partner 3", "9 Cliff Gannett 5", "10 Mark O'Donnell 1" } tree = BuildHierarchyTree() tree.readDataAndCreateMap(lines) tree.buildHierarchyTree(tree.root) tree.printHierarchyTree(tree.root, 0) |
Doodle
Output:
Joseph Grant
Rob Choi
Andy Zuckeman
Mark O’Donnell
Lois Lemer
Melaney Partner
Moises Medina
Paul Marmolejo
Christie Jacobs
Cliff Gannett
O Notation:
Time complexity: O(n)
Space complexity: O(n)
Download BuildHierarchyTree.java
Download BuildHierarchyTree.js
Download BuildHierarchyTree.py
Build hierarchy tree (YouTube)
Java Coding Interview Pocket Book
