休斯顿最火初创 SocialGear 的一道onsite面经题

zsz1990ustc

上周去休斯顿一家很火的startup，叫SocialGear的公司去onsite。

7 P8 I; Q& J: X! e这是他家网站： https://socialgear.us/
. N0 I7 s$ d7 z% ~
onsite一个半小时，考了一些Web开发的基本知识，如Spring是啥，如RESTful是啥。然后一道程序设计题，设计抽奖系统。接着还有洗牌程序。我跟着面试官的提示，算是解决了。

最后一道算法题，懵了。求 多叉树 的最底层 所有 叶子的最小公共祖先。面试官先让我试试 二叉树，我用DFS（其实应该用BFS）找到最底层的那些叶子，然后两两找公共祖先（LCA）。最后是O(n^2)的复杂度。后来真想不到怎么优化了。面试官很nice，教了我一通，我当时是明白了。回家之后又忘了。

) [- D5 s. \) c
) P( v& N' K' j于是这几天一直在钻研这道题，并回忆当时面试官的指导，现在算是解决出来啦！

  B3 m6 o# {9 ?; R( n: T
& V1 l& q0 K, G/ m我们先考虑最基本的Binary Tree的两个node的LCA 怎么做（没有parent node）。一般网上的解法都用Divide and Conqure，就是左子树递归不为null，柚子树递归不为null, 则当前node为LCA。 我回忆当时那个面试官思路后，另辟蹊径，写出以下解法。看懂我解决多叉树那道题的前提，就是要看懂这个解法。
* ^: i' E2 P' G* R- ]& q8 a
9 }) V! j  |! C
求p点和q点的LCA, 一次DFS回溯遍历搞定，找到第一个target后（比如p），记录回溯时到达的shallowest level，和对应的那个节点（就是LCA candidate），回溯过程中突然发现第二个target (比如q)，这是 此前回溯过程中到达的shallowest level和对应的那个节点 tempLCA就是LCA啦。

$ w' O' X0 [% ~# H; E6 o
/**
) E; D6 V0 l* K; ^. f+ \* | * Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
" u; n+ @/ [; M# d( t *     TreeNode(int x) { val = x; }
! J) Q/ I& u' c+ T- c * }
1 P# |5 H4 g# w  \+ U' x& G */
public class Solution {
0 v4 T3 f* q( R( Y/ q6 B, D        int shallowest = 0;   // the shallowest level that I visited in backtracking after I got the first target node
! F' a2 s& d% y5 A        boolean getFirstTarget = false;    // whether I got the first target node
        TreeNode tempLCA;   // the node corresponding the shallowest level, which is a LCA candidate
        TreeNode LCA;    // the result, LCA
) u) Q8 H7 f) ?6 U        
( g* P6 V8 ?0 `) p5 Q7 x" K    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return root;
. a, I2 i+ u- T                dfsFind(root, p, q, 0);
                return LCA;
    }
$ O, K) S  G1 X! X7 V9 r& y& J
0 T- w5 K) F# A; j& d    public void dfsFind(TreeNode root, TreeNode p, TreeNode q, int curLev){
; Q+ Y8 x$ }7 g! N2 o5 o0 q* i( Z                if (root == p || root == q) {
                        if (!getFirstTarget){
. ~# f5 G( o0 j2 x9 {; u" i                                getFirstTarget = true;
                                shallowest = curLev;
/ E% ?3 C5 P0 c7 V3 e5 t7 L                                tempLCA = root;
8 ]/ {( b" Z9 E8 Y' g                        }
                        LCA = tempLCA;
                }
5 }4 x, y% k& }               
# F! m: `; H# Q3 k3 L/ v            if (getFirstTarget && curLev <= shallowest) {  //after get the first deepest leaf node candidate, mark the shallowest level when backtracking
/ b& |3 A; M5 U; C  ~! q                        shallowest = curLev;
                        tempLCA = root;
                }
1 F9 n5 O, `( a               
                if (root.left != null){   // dfs for left node
                    dfsFind(root.left, p, q, curLev + 1);
                    if (getFirstTarget && curLev <= shallowest) {   //mark the shallowest level when backtracking
                            shallowest = curLev;
: N5 S  D$ H1 d                            tempLCA = root;
                    }
! H; w6 b8 h% q+ Q- r8 Z4 n+ W                }
               
                if (root.right != null){   //dfs for right node
& O" A" W- d" v0 r, b9 w                    dfsFind(root.right, p, q, curLev + 1);
( |% w; g! Y( I/ y                    if (getFirstTarget && curLev <= shallowest) {    //mark the shallowest level when backtracking
! [& v% M! C3 z                            shallowest = curLev;
( `! n+ K' {- u  ~. R                            tempLCA = root;
                    }
                }
        }
}
! ~5 x. K: u8 {9 I8 D
- s# n+ K* g+ ?/ _2 V2 Q! c如果看官能理解我上面的解法。就能看懂我解决多叉树那个原题啦。

  I' j2 _: O1 J* Z& A* N// defination for N-ary TreeNode.
- j  g; ?; X  G+ v0 N

class TreeNode{

        int val;

        ArrayList<TreeNode> children = new ArrayList<TreeNode>();

        public TreeNode(int val){

                this.val = val;

        }

}

5 v. G$ ^+ `7 s

public class MultiTree {

        int shallowest = 0; // the shallowest level that I visited in backtracking after I got the first deepest leaf node candidate

        int deepest = 0;        // the deepest leaf node level

        boolean getFirstTarget = false; // whether I got the first deepest leaf node candidate

        TreeNode tempLCA;   // the node corresponding the shallowest level, which is a LCA candidate

        TreeNode LCA;  // the result, LCA

0 e, f+ Y& S9 |( A

        public TreeNode findLCA(TreeNode root){

                if(root == null) return root;

                dfsFind(root, 0);

                return LCA;

        }

        public void dfsFind(TreeNode root, int curLev){

                if (root.children.isEmpty()) {        //get a leaf node

                        if (!getFirstTarget){                 // if hasn't yet get the first deepest leaf node

                                getFirstTarget = true;

                                shallowest = curLev;

                                deepest = curLev;

                                tempLCA = root;

                        }

                        if (curLev == deepest){        //if current level is the deepest, the candidate LCA might be the result

                                LCA = tempLCA;

                        }

: c3 |  x5 p0 v( N9 p9 x. w& y

                        if (curLev > deepest){  //if current level is larget than deepeest, reset all the marks

                            deepest = curLev;

                            getFirstTarget = false;

                            shallowest = curLev;

                                deepest = curLev;

                                tempLCA = root;

                                LCA = tempLCA;

                    }

                }

            if (getFirstTarget && curLev <= shallowest) {        

                        shallowest = curLev;  //after get the first deepest leaf node candidate, mark the shallowest when backtracking

                        tempLCA = root;

                }

5 Y4 x- @4 a, A# t  H: S0 E  @

                ArrayList<TreeNode> children = root.children;

                for (TreeNode child : children){

                        dfsFind(child, curLev + 1);

                        if (getFirstTarget && curLev <= shallowest) {

                            shallowest = curLev;         //mark the shallowest when backtracking

                            tempLCA = root;

                    }

                }

        }

}

注释已经写得比较清楚了。我懒得打字解释了，你们画画图就明白了。要是还不明白，我再画画图给你们解释~~

% T" f# ?  b* t2 g

这家StartUp最近似乎又拿了一轮融资。bar比较高，也是可以理解。我还没有收到他家后续消息。

/ n- Y5 Y# H7 ^8 m

Anyaway，在这里发个帖子，求攒人品~~ 也求版主多给些米，我的阅读权限太低，好多帖子看不了。。

祝大家都有好offer！

0 `2 k$ o' Z' H/ r# O6 y8 A& T8 j4 y

running_man

感谢zsz1990ustc分享~~~

Helen

感谢zsz1990ustc分享~~~好人一生平安~~~