Monarchy succession order – code

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”

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 :

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.

Java Coding Interview Pocket Book (2nd Edition)

Comments are closed