Problem: A kingdom consists of a king, his children, his grandchildren, and so on. Every once in a while, someone in the family dies or a child is born.
The kingdom has a well-defined order of inheritance that consists of the king as the first member. Let's define the recursive function Successor(x, curOrder), which given a person x and the inheritance order so far, returns who should be the next person after x in the order of inheritance.
Successor(x, curOrder):
if x has no children or all of x's children are in curOrder:
if x is the king return null
else return Successor(x's parent, curOrder)
else return x's oldest child who's not in curOrderFor example, assume we have a kingdom that consists of the king, his children Alice and Bob (Alice is older than Bob), and finally Alice's son Jack.
In the beginning, curOrder will be ["king"].
Calling Successor(king, curOrder) will return Alice, so we append to curOrder to get ["king", "Alice"].
Calling Successor(Alice, curOrder) will return Jack, so we append to curOrder to get ["king", "Alice", "Jack"].
Calling Successor(Jack, curOrder) will return Bob, so we append to curOrder to get ["king", "Alice", "Jack", "Bob"].
Calling Successor(Bob, curOrder) will return null. Thus the order of inheritance will be ["king", "Alice", "Jack", "Bob"].
Using the above function, we can always obtain a unique order of inheritance.
Implement the ThroneInheritance class:
- ThroneInheritance(string kingName) Initializes an object of the ThroneInheritance class. The name of the king is given as part of the constructor.
- void birth(string parentName, string childName) Indicates that parentName gave birth to childName.
- void death(string name) Indicates the death of name. The death of the person doesn't affect the Successor function nor the current inheritance order. You can treat it as just marking the person as dead.
- string[] getInheritanceOrder() Returns a list representing the current order of inheritance excluding dead people.
Example:
Input
["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"]
[["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]]
Output
[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]
Explanation
ThroneInheritance t= new ThroneInheritance("king"); // order: king
t.birth("king", "andy"); // order: king > andy
t.birth("king", "bob"); // order: king > andy > bob
t.birth("king", "catherine"); // order: king > andy > bob > catherine
t.birth("andy", "matthew"); // order: king > andy > matthew > bob > catherine
t.birth("bob", "alex"); // order: king > andy > matthew > bob > alex > catherine
t.birth("bob", "asha"); // order: king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // return ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
t.death("bob"); // order: king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // return ["king", "andy", "matthew", "alex", "asha", "catherine"]
Approach: We can make a N-ary tree and do a preorder traversal.
Implementation in C#:
public class ThroneInheritanceNode
{
public string Name {get; private set;}
public bool IsDead {get; private set;}
public List<ThroneInheritanceNode> Children {get; set;}
public ThroneInheritanceNode(string name)
{
this.Name = name;
this.IsDead = false;
this.Children = new List<ThroneInheritanceNode>();
}
public void MarkDead()
{
this.IsDead = true;
}
}
public class ThroneInheritance
{
public ThroneInheritance(string kingName)
{
this.root = new ThroneInheritanceNode(kingName);
this.nodeMap = new Dictionary<string, ThroneInheritanceNode>();
this.nodeMap[kingName] = root;
}
public void Birth(string parentName, string childName)
{
if (!nodeMap.ContainsKey(parentName))
{
return;
}
ThroneInheritanceNode node = new ThroneInheritanceNode(childName);
this.nodeMap[childName] = node;
this.nodeMap[parentName].Children.Add(node);
}
public void Death(string name)
{
if (!nodeMap.ContainsKey(name))
{
return;
}
this.nodeMap[name].MarkDead();
}
public IList<string> GetInheritanceOrder()
{
return this.GetInheritanceOrderDFS(this.root);
}
private IList<string> GetInheritanceOrderDFS(ThroneInheritanceNode node)
{
List<string> result = new List<string>();
if (node == null)
{
return result;
}
if (!node.IsDead)
{
result.Add(node.Name);
}
foreach (var child in node.Children)
{
result.AddRange(this.GetInheritanceOrderDFS(child));
}
return result;
}
private ThroneInheritanceNode root;
private Dictionary<string, ThroneInheritanceNode> nodeMap;
}
/**
* Your ThroneInheritance object will be instantiated and called as such:
* ThroneInheritance obj = new ThroneInheritance(kingName);
* obj.Birth(parentName,childName);
* obj.Death(name);
* IList<string> param_3 = obj.GetInheritanceOrder();
*/
Complexity: Birth - O(1), Death - O(1), GetInheritanceOrder - O(n)
