Succession - 1point3acres

王位继承
有一个king，king会有孩子，孩子还能生孩子。实现几个function：

• void birth(String parent, String name) 父亲名字和孩子名字，生个娃
• void death(String name) 此人要死
• List<String> getOrder() 返回当前的继承顺序，string array/list

讨论得知，每个人的名字是唯一的，继承顺序符合如下规律:

假设王有大皇子二皇子三皇子，大皇子有长子次子三子，那么继承顺序是王->大皇子->大皇子长子->大皇子次子->大皇子三子->二皇子->三皇子

死掉的人不能出现在继承顺序里，但是如果上面例子中大皇子死了，只需把大皇子移除，原始继承顺序保持不变：王->大皇子长子->大皇子次子->大皇子三子->二皇子->三皇子

三个function会被反复调用，实现function细节。

getOrder函数的实现。一般大家好像是preorder traversel，但是看到有面试官要求O(1)实现，不知道有没有朋友有O（1）的做法？
用树形结构存，然后preOrder来找最先找到的非dead的node返回。如果要实现O(1)查询，可以每次调用dead()的时候把这个node从树里面删除，由它的长子来顶替它的位置，也就是说长子会成为次子的父亲。这样复杂度是amortized O(1)。

https://www.1point3acres.com/bbs ... read&tid=464318
https://www.1point3acres.com/bbs ... read&tid=429208

put nodes into double linked list, the double listed list keep the order of inheritance. 

Also, hashmap map name to the node, additionally each node has another pointer to his younger brother. this make birth O(1) again.

getOrder只要返回一个链表头而已 维护好链表肯定是O(1)呀 

      我用了 tree 来表示，没有用面经常用的 map。后面 follow up 做优化，我提到可以 pre-compute 继承的 order，用改良版 linkedlist 保存，每次调用 birth 和 death function 的时候可以O(1) update

         这一轮的 feedback 是最好的，我的感想是看面经可以知己知彼百战不殆，但是如果被面经束缚就不好了。解题有自己的思路和风格也可以在简单的面经轮脱颖而出

insert a node just before its younger brother. O(1)

sorry, should be "the youngest older brother"

Say, Here Tom has one son, Tom II, and two brothers, Frank and John. Here Tom points to Frank and Frank points to John via "brother pointer"

  

Tom <-> Tom II <-> Frank <-> John. 

Say Tom has another child, Tom III, then Tom uses brother pointer to find Frank, and insert a new node Tom III just before Frank. O(1).

what if younger brother is dead, or his descendants dead? how do we handle death in treeNode, wors ...

death(Tom)

1) use HashMap to find Tom's Node in double linked list, O(1)

2) update the double linked list and associated brother pointer by removing Tom, O(1)

3) remove Tom from HashMap, O(1)