刚面的google电面

刚面的google电面,电话那头小哥人特别nice,很友好地解释我不清楚的assumption,简历半句话都没问。
是一道OOD,实现一个接口

Interface Monarchy{
  void birth(String child_name, String parent);
  void death(String name);
  List<String> getOrderOfSuccession();
}

就是一个国王家族,有一个King作为Root,每个人都可以生儿子,也会死,对应前两个method。
而第三个method是把活着的家族成员都加到List:(举个例子)

          root_king
          /         \
       a1            a2
      /  \            /  \
    b1   b2      c1    c2
   /   \     \
d1    d2    d3

那么添加到List的顺序是:root_king -> a1 -> b1 -> d1 -> d2 -> b2 -> d3 -> a2 -> c1 -> c2(且死了的不添加到这个List里面)
也就是说按DFS顺序打印,或者说类似于Tree的PreOrder Traversal(这还是小哥提醒我的)

就只给你一个接口和三个要被实现的method叫你implements这个接口。我这图也只是第三个方法的演示,没说一定要按树的方式构造类,你要自己想办法去储存整个家庭成员,死和出生你看这两个method的传入参数应该很直观吧。

楼主用什么方式实现的呢 我想的是用hashmap来实现

对 我是自己先写了个class Member{},里面有个List存children,一个name,一个isAlive。(就像一个有多个子节点的树的节点)
我跟面试官沟通了可以让每个人名字不一样,所以我在实现接口的类里maintain一个HashMap<名字,对应的member>,每当插入就在HashMap里put一个新家族成员

有些没看明白,我想问一下它本身给你的是一个树的结果么,还有dead和live这俩函数是干啥的,让其中某个人死么。。

楼主你好,请问如果king挂了的话谁变成king呢?

这个king就最初那一个,这题没要求maintain king为继承人顺序中第一个没死的

高频题 马一下

我觉得,用邻接表的形式构建有向图吧。
用哈希表,key是parent, value 是一个heap, 按年龄从大到小排序,这样做dfs的时候就保证是年龄大的先遍历到。要是已经死了就不加入list。