Monarchy succession order is also known as The line of succession to the British throne. The succession to the British throne is determined by descent, sex, legitimacy, and religion. Under common law, the Crown is inherited by a sovereign’s children or by a childless sovereign’s nearest collateral line. The basis of the monarchy succession was determined in the seventeenth century. You can get the current British monarchy succession order here.
As programmer, you might be asked to implement the rule using program language. The algorithm is pretty simple – it is pre-order of the hierarchy tree. The first step is to the build the hierarchy tree from the parent children relationships. Please refer to this post to construct the hierarchy tree. remember to make the queen as the root of the tree.
Then we can use recursion or stack to pre-order the tree. In this implementation, we 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 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 |
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)); } } |
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.
Download RoyalSuccessionOrder.java
Java Coding Interview Pocket Book (2nd Edition)
