British royal succession order is also known as the line of succession to the British throne. Under common law, the crown is inherited by a sovereign’s children or by a childless sovereign’s nearest collateral line. You can get the current British monarchy succession order here. When you are asked to implement the rule, the algorithm is pretty simple. It is preorder of the hierarchy tree. The first step is to the build the royal succession tree from the parent children relationships. Remember to make the queen as the root of the tree.
Then you can use recursion or stack to preorder the tree. In this implementation, you use stack to hold royal members. Staring from the root, push the member in the stack. In a while loop, pop the member in the stack and add him/her to the order list. Meanwhile, push this member’s successors (from the last to the first) to the stack. Finally return the order list.
Google Interview Question:
Given the monarchy relatiohship, as list of “parent child1, child2”
1 2 3 4 5 6 7 | king / \ a1 a2 / \ / \ b1 b2 c1 c2 / \ \ d1 d2 d3 |
implement its method to get the list of successors in order.
Order of Succession: king -> a1 -> b1 -> d1 -> d2 -> b2 -> d3 -> a2 -> c1 -> c2
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 | import java.util.*; class Member { protected String name; protected List<Member> successors = new ArrayList<>(); //Constructor, Time O(1), Space O(1) public Member (String name) { this.name = name; } //Add child to member, Time O(1), Space O(1) public void addChild(Member child) { successors.add(child); } } public class RoyalSuccessionOrder { private Map<String, Member> monarchy = new HashMap<>(); //stores (name, member) pair private Member king; //Build map from the input list, Iteration, Time O(n), Space O(n), //n is total number of members in family public void buildMonarchyMap(String[] nameList) { for (String line : nameList) { String[] strs = line.split(" "); for (int i = 0; i < strs.length; i++) { if (!monarchy.containsKey(strs[i])) monarchy.put(strs[i], new Member(strs[i])); } if (strs.length > 1) { for(int i = 1; i < strs.length; i++) monarchy.get(strs[0]).addChild(monarchy.get(strs[i])); } if (strs[0].equals("Queen")) king = monarchy.get("Queen"); } } //Build tree, Recursion, Time O(n), Space O(h), h is level of successors public void buildMonarchyTree(Member root) { if (root.successors.size() == 0) return; for (Member succ : root.successors) buildMonarchyTree(succ); } //Pre-order the succession order, Iteration, Time O(n), Space O(n) public List<String> preOrderSuccessors(Member root) { if (root == null) return Collections.emptyList(); Stack<Member> stack = new Stack<>(); List<String> res = new LinkedList<>(); stack.add(root); while (!stack.isEmpty()) { Member curr = stack.pop(); res.add(curr.name); for (int i = curr.successors.size()-1; i >= 0; i--) stack.add(curr.successors.get(i)); } return res; } public static void main(String[] args) { RoyalSuccessionOrder tree = new RoyalSuccessionOrder(); String[] list = {"Queen Charles Andrew Edward Anne", "Charles William Harry", "Andrew Beatric Eugenie", "Edward James Louise","Anne Peter Zara", "William George Charlotte Louis", "Harry Archie", "Peter Savannah Isla", "Zara Mia Lena"}; tree.buildMonarchyMap(list); tree.buildMonarchyTree(tree.king); System.out.println("The royal succession sequence: " ); System.out.println(tree.preOrderSuccessors(tree.king)); } } |
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 70 71 72 73 74 75 76 | class Member { //Constructor, Time O(1), Space O(1) constructor (name) { this.name = name; this.successors = []; } //Add child to member, Time O(1), Space O(1) addChild(child) { this.successors.push(child); } } class RoyalSuccessionOrder { constructor () { this.monarchy = new Map(); //stores (name, member) pair this.king = null; } //Build map from the input list, Iteration, Time O(n), Space O(n), //n is total number of members in family buildMonarchyMap(nameList) { for (let line of nameList) { var strs = line.split(" "); for (let i = 0; i < strs.length; i++) { if (!this.monarchy.has(strs[i])) this.monarchy.set(strs[i], new Member(strs[i])); } if (strs.length > 1) { for(let i = 1; i < strs.length; i++) this.monarchy.get(strs[0]).addChild(this.monarchy.get(strs[i])); } if (strs[0]==="Queen") this.king = this.monarchy.get("Queen"); } return this.king; } //Build tree, Recursion, Time O(n), Space O(h), h is level of successors buildMonarchyTree(root) { if (root.successors.length == 0) return; for (let succ of root.successors) { this.buildMonarchyTree(succ); } } //Pre-order the succession order, Iteration, Time O(n), Space O(n) preOrderSuccessors(root) { if (root == null) return []; var stack = []; var res = []; stack.push(root); while (!stack.length == 0) { var curr = stack.pop(); res.push(curr.name); for (let i = curr.successors.length-1; i >= 0; i--) stack.push(curr.successors[i]); } return res; } } var tree = new RoyalSuccessionOrder(); const list = ["Queen Charles Andrew Edward Anne", "Charles William Harry", "Andrew Beatric Eugenie", "Edward James Louise", "Anne Peter Zara", "William George Charlotte Louis", "Harry Archie", "Peter Savannah Isla", "Zara Mia Lena"]; var king = tree.buildMonarchyMap(list); tree.buildMonarchyTree(king); console.log("The royal succession sequence: " ); console.log(tree.preOrderSuccessors(king)); |
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 | class Member : #Constructor, Time O(1), Space O(1) def __init__(self, name) : self.name = name self.successors = [] #Add child to member, Time O(1), Space O(1) def addChild(self, child) : self.successors.append(child) class RoyalSuccessionOrder: def __init__(self) : self.monarchy = {} #stores (name, member) pair self.king = None #Build map from the input list, Iteration, Time O(n), Space O(n), #n is total number of members in family def buildMonarchyMap(self, nameList) : for line in nameList : strs = line.split(" ") for i in range(0, len(strs)): if strs[i] not in self.monarchy: self.monarchy[strs[i]] = Member(strs[i]) if len(strs) > 1: for i in range(1, len(strs)) : self.monarchy.get(strs[0]).addChild(self.monarchy.get(strs[i])) if strs[0]=="Queen": self.king = self.monarchy.get("Queen") return self.king; #Build tree, Recursion, Time O(n), Space O(h), h is level of successors def buildMonarchyTree(self, root) : if len(root.successors) == 0 : return for succ in root.successors: self.buildMonarchyTree(succ) #Pre-order the succession order, Iteration, Time O(n), Space O(n) def preOrderSuccessors(self, root) : if root == None: return [] stack = [] res = [] stack.append(root) while len(stack) != 0: curr = stack.pop() res.append(curr.name) for i in range (len(curr.successors)-1,-1,-1): stack.append(curr.successors[i]) return res tree = RoyalSuccessionOrder() list = ["Queen Charles Andrew Edward Anne", "Charles William Harry", "Andrew Beatric Eugenie", "Edward James Louise", "Anne Peter Zara", "William George Charlotte Louis", "Harry Archie", "Peter Savannah Isla", "Zara Mia Lena"] king = tree.buildMonarchyMap(list) tree.buildMonarchyTree(king) print("The royal succession sequence: " ) print(tree.preOrderSuccessors(king)) |
Output:
The royal succession sequence:
[Queen, Charles, William, George, Charlotte, Louis, Harry, Archie, Andrew, Beatric, Eugenie, Edward, James, Louise, Anne, Peter, Savannah, Isla, Zara, Mia, Lena]
O Notation:
Time complexity: O(n)
Space complexity: O(n)
n is number of monarchy members.
Use Depth first search. Preorder to be precise.
Download RoyalSuccessionOrder.java
Download RoyalSuccessionOrder.js
Download RoyalSuccessionOrder.py
Build hierarchy tree – code
