空气床电面跪经

上周四电面空气床，今天一早在去别家onsite的路上收到拒信。电面过程有点憋屈， 但说到底还是自己太渣，太久没电面经验不足。把题目分享出来给大家做个参考.

开头重说三，空气床家的代码一定要当场跑通！空气床家的代码一定要当场跑通！空气床家的代码一定要当场跑通！只要面试官没有明确表示异议，你感觉没什么问题就不要犹豫的点运行！

四十五分钟的电面，电话沟通， Coderpad敲代码。Recuiter之前沟通时明确告诉我不需要apply(于是也没有update profile什么的)，结果面试当天进入CoderPad后干等了五分钟，才等到一个国人名字的小哥上线，打字问我：你号码还是XXX吗？打了没人接。。。恩于是面试的前五分钟就这样浪费了。

上来先让自我介绍，说一下做过的project什么的，大概又花了10分钟。然后正式开始做题。

题目大意如下：

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

题目不难，但是因为需要自己从input开始建tree, 各种helper class, helper function比较繁琐。小哥除了叙述题目之外，全程单字“嗯”回应，一度安静到可以听得见电话那头小哥同事的交谈声。。。
因为小哥全程缺乏feedback,为了防止冷场，LZ只能一边敲码一边说话，解释思路也调节气氛。事后回想这其实真的很影响思维和写码速度，只要开头解释清楚了思路，中间可能还是专注赶快敲完比较好。

写完和手动过完test case后还剩不到十分钟，LZ先是说了一句“I think this is it”,本来想得到小哥点头后点运行，结果小哥完全没有回应。。。好几秒的安静(能听到电话那头背景音的程度)，LZ只能再说了一次(其实应该明确问“May I try running the code?”, 还是经验不足啊)，小哥还是没回应。当时就有点慌，以为出了傻叉Bug小哥都不屑理我，又手动run了一个test case, 还是觉得没什么问题。这时候小哥才说，提醒你一下这个代码要跑过的。。。(一口老血)。这时候时间只剩下五分钟多点，LZ只来的及运行了一次，改了一个syntax error (所以还是自己渣，怪不得别人)，小哥就说时间差不多了，你有什么问题问我。于是当时就知道，凉凉了。

最近打算先暂缓面试，多刷点题和system design, 求大家加些米方便看面经呀！

1. class Solution {
   
2.     static class Node {
   
3.         String name;
   
4.         List<Node> children;
   
5. 
   
6.         Node(String name) {
   
7.             this.name = name;
   
8.             this.children = new ArrayList<>();
   
9.         }
   
10.     }
    
11. 
    
12.     public String solve(List<List<String>> input, String p, String q) {
    
13.         Map<String, Node> m = new HashMap<>();
    
14.         Node root = new Node(input.get(0).get(0));
    
15.         m.putIfAbsent(input.get(0).get(0), root);
    
16.         for (List<String> l : input) {
    
17.             m.putIfAbsent(l.get(0), new Node(l.get(0)));
    
18.             Node r = m.get(l.get(0));
    
19.             for (int i = 1; i < l.size(); i++) {
    
20.                 m.putIfAbsent(l.get(i), new Node(l.get(i)));
    
21.                 Node n = m.get(l.get(i));
    
22.                 r.children.add(n);
    
23.             }
    
24.         }
    
25.         return lca(root, p, q).name;
    
26.     }
    
27. 
    
28.     private Node lca(Node root, String p, String q) {
    
29.         if (root == null) {
    
30.             return null;
    
31.         }
    
32.         if (root.name.equals(p) || root.name.equals(q)) {
    
33.             return root;
    
34.         }
    
35. 
    
36.         Node ancestor = null;
    
37. 
    
38.         for (Node next : root.children) {
    
39.             Node n = lca(next, p, q);
    
40.             if (n == null) continue;
    
41.             if (ancestor == null) {
    
42.                 ancestor = n;
    
43.             } else {
    
44.                 return root;
    
45.             }
    
46.         }
    
47. 
    
48.         return ancestor;
    
49.     }
    
50. 
    
51.     public static void main(String[] args) {
    
52.         List<List<String>> input = new ArrayList<>();
    
53.         input.add(new ArrayList<>(Arrays.asList("Earth", "North America", "South America")));
    
54.         input.add(new ArrayList<>(Arrays.asList("North America", "United States", "Canada")));
    
55.         input.add(new ArrayList<>(Arrays.asList("United States", "New York", "Boston")));
    
56.         input.add(new ArrayList<>(Arrays.asList("Canada", "Ontario", "Quebec")));
    
57.         input.add(new ArrayList<>(Arrays.asList("South America", "Brazil")));
    
58.         Solution s = new Solution();
    
59.         System.out.println(s.solve(input, "Quebec", "New York"));
    
60.         System.out.println(s.solve(input, "Canada", "South America"));
    
61.         System.out.println(s.solve(input, "Canada", "Quebec"));
    
62.     }
    
63. }

复制代码

谢谢分享。其实一个Map就可以了哈

public String findSmallestRegion(List<List<String>> regions, String A, String B) {

    if (regions == null || regions.size() == 0) {
      return null;
    }

    Map<String, String> parentRegions = new HashMap<>();

    for (List<String> regs : regions) {
      String parent = regs.get(0);
      for (int i = 1; i < regs.size(); i++) {
        parentRegions.put(regs.get(i), parent);
      }
    }

    List<String> aParents = new ArrayList<>();

    while (A != null) {
      aParents.add(A);
      A = parentRegions.get(A);
    }

    while (B != null) {
      if (aParents.contains(B)) {
        return B;
      }
      B = parentRegions.get(B);
    }

    return null;
  }

汐风悠远 发表于 2019-5-30 08:34
不用建tree的做法当时确实没有想到，挂了不冤枉。
每个region至多一个直接parent，这个是问了的(虽然不 ...

list之间的大小关系不确定的话，每一个list的第一个region都可能是root, 你无法确定root。而且有可能这是多个树或者多张图，不一定所有的region都能连一起。结果可能就是找不到共同的parents。如果这些没clarify清楚，你一开始就说建树，我相信面试官第一印象就很差了。 这题的最好的解法就是我说得那种，然后bfs 从两个target region 同时跑，分别记录两端visited的node， 第一个重复就是共同的parent。

看面试官吧 如果面试官是那种很投入的, 我会和他交流一下大概思路, 然后猛写..
如果明显面试官在做别的事情, 我就自己写, 然后赶紧run 赶紧debug

其实不用把tree建出来。用hashmap把每个点的所有ancestor作为set建出来。Map ｛node =》set（ancestors）｝然后找那两个点对应的set的intersection。这个intersection就是all common ancestors。然后在这个intersection里面，对每个点trace它的anscestor，然后把它们从set里去掉。最后剩下的那个就是lowest

foryou 发表于 2019-5-29 12:44
[mw_shl_code=java,true]class Solution {
    static class Node {
        String name;

完全没想到可以这样做，剩下一大把写helper的时间！

话说这个代码是不是需要隐藏一下，感觉直接透题了hhh

完全不知道为什么要建树，首先复杂，第二根据条件，除了每个list开头的region最大这一条件以外，各个list之间的顺序，list中其他region的顺序都不确定， 所以每个list的第一个element都有可能是root， 你怎么知道是哪个?  第三这完全可以不是一个nary tree的结构，有没有可能有loop， 有没有可能一个child 有multiple parents, 有没有可能这是两个或多个tree 或者两个或多个graph？这些你都没clarify清楚。要我说，直接用hashtable 来表明node之间的关系，然后bfs找最小的相同的parent 就行了。

chenyijia055 发表于 2019-5-30 08:29
完全不知道为什么要建树，首先复杂，第二根据条件，除了每个list开头的region最大这一条件以外，各个list之 ...

不用建tree的做法当时确实没有想到，挂了不冤枉。
每个region至多一个直接parent，这个是问了的(虽然不清楚follow-up会不会出现多个parent的情况)， region也一定能在graph里面找到。

汐风悠远 发表于 2019-5-30 03:21
完全没想到可以这样做，剩下一大把写helper的时间！

话说这个代码是不是需要隐藏一下，感觉直接透题了 ...

list之间顺序不确定的话, 比较难做, 那就变成了这题是LCA of directed graph了. 我的解法默认了第一行的第一个就是root

foryou 发表于 2019-5-30 14:18
list之间顺序不确定的话, 比较难做, 那就变成了这题是LCA of directed graph了. 我的解法默认了第一行的 ...

list之间的顺序的确是不确定的，这一点我特意和面试官确认过。Earth的那个list并不一定是第一个，只是当时给的样例长这样。
我当时的理解是，这些regions是属于一张图中的，也确认了不存在找不到region或者有多个direct parent的情况。hashmap的解法在这些前提下仍然可行，至于followup会不会出现node找不到，多个parents，或者干脆不在同一张图里的情况就不知道了。。。