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

zsz1990ustc

0 L! d1 K. W4 o2 ^
, |5 w, R* K( C7 k) i0 D2 J上周去休斯顿一家很火的startup，叫SocialGear的公司去onsite。
' S# h: j. x! w2 x( U9 A" y& O& O
这是他家网站： https://socialgear.us/
' _2 p. ^1 v  F1 G
onsite一个半小时，考了一些Web开发的基本知识，如Spring是啥，如RESTful是啥。然后一道程序设计题，设计抽奖系统。接着还有洗牌程序。我跟着面试官的提示，算是解决了。
& \5 K* a) b! P6 {. j& B
% x+ [7 t9 d) z$ O, b% ?, x* V最后一道算法题，懵了。求 多叉树 的最底层 所有 叶子的最小公共祖先。面试官先让我试试 二叉树，我用DFS（其实应该用BFS）找到最底层的那些叶子，然后两两找公共祖先（LCA）。最后是O(n^2)的复杂度。后来真想不到怎么优化了。面试官很nice，教了我一通，我当时是明白了。回家之后又忘了。
9 F0 u- H; a: u. m
' L: E' g% ~; U3 R; H/ U4 @' q! Y
于是这几天一直在钻研这道题，并回忆当时面试官的指导，现在算是解决出来啦！
% r+ e2 [8 l0 u8 y. {

7 v: }4 h/ v1 \% h我们先考虑最基本的Binary Tree的两个node的LCA 怎么做（没有parent node）。一般网上的解法都用Divide and Conqure，就是左子树递归不为null，柚子树递归不为null, 则当前node为LCA。 我回忆当时那个面试官思路后，另辟蹊径，写出以下解法。看懂我解决多叉树那道题的前提，就是要看懂这个解法。


8 P/ {6 B! ?+ P% F求p点和q点的LCA, 一次DFS回溯遍历搞定，找到第一个target后（比如p），记录回溯时到达的shallowest level，和对应的那个节点（就是LCA candidate），回溯过程中突然发现第二个target (比如q)，这是 此前回溯过程中到达的shallowest level和对应的那个节点 tempLCA就是LCA啦。
  E! {: U  Q& R) i
) J% R) a; r$ I$ d% k# v
/**
0 `9 L& c2 s8 ~ * Definition for a binary tree node.
* public class TreeNode {
0 S2 d% y; E' ~: n *     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
' H6 @5 f. W* D; Z" o9 P        int shallowest = 0;   // the shallowest level that I visited in backtracking after I got the first target node
7 e& I# q# y- {        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: I- k1 F* {; W        
: h' j$ ~! J! Q) e5 I8 x: a0 I    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
1 P# t4 I/ q0 H* [0 @$ [: B        if(root == null) return root;
                dfsFind(root, p, q, 0);
( ^3 E% n7 m9 E# z5 R                return LCA;
# M( Q, o$ G$ N+ I! h    }
% x" z, P6 b+ ^! J  G" e
    public void dfsFind(TreeNode root, TreeNode p, TreeNode q, int curLev){
0 x  J4 D5 j" K6 d$ n                if (root == p || root == q) {
& m9 s$ i: a9 A" ?. d4 n9 l                        if (!getFirstTarget){
                                getFirstTarget = true;
* x: ~9 j" r4 }, i. Z9 J                                shallowest = curLev;
# R* {( E, e' U0 W                                tempLCA = root;
+ Z* I7 i# w0 d) x9 J& F* V, U                        }
5 v: z! g6 ~( |$ W/ x) P                        LCA = tempLCA;
                }
6 ?* Y) `% a+ L& l; W0 D& ^5 F               
            if (getFirstTarget && curLev <= shallowest) {  //after get the first deepest leaf node candidate, mark the shallowest level when backtracking
5 }1 R1 f9 u  x8 b6 M                        shallowest = curLev;
                        tempLCA = root;
0 O) S. ]5 V/ s* s" b6 s' s                }
               
3 [% l0 p, x5 E                if (root.left != null){   // dfs for left node
& n0 K8 c# Y  Z, `                    dfsFind(root.left, p, q, curLev + 1);
$ p7 Y: _& u/ B" {                    if (getFirstTarget && curLev <= shallowest) {   //mark the shallowest level when backtracking
3 c# q* S4 c' Q' Z7 l5 |2 T                            shallowest = curLev;
! Z6 a2 l/ H3 [0 K                            tempLCA = root;
* ?8 u1 Q9 O1 `) G9 G, x                    }
6 k3 F4 m. G& \: s5 _                }
: v1 h6 w* o; \- C               
- G' x& |( d# ~+ s* g) ?                if (root.right != null){   //dfs for right node
! i1 P' H! F" {4 c. f                    dfsFind(root.right, p, q, curLev + 1);
, p3 k  q$ x8 s' W1 q' b; Q* T+ U% r                    if (getFirstTarget && curLev <= shallowest) {    //mark the shallowest level when backtracking
                            shallowest = curLev;
                            tempLCA = root;
: _. s2 j! B* p, A' E3 Q: V5 o                    }
                }
        }
7 k- x; B+ c+ v, |; n* Z% x' y4 C$ t8 L}

1 o5 M! W, e% f( M  n如果看官能理解我上面的解法。就能看懂我解决多叉树那个原题啦。

// defination for N-ary TreeNode.

class TreeNode{

        int val;

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

        public TreeNode(int val){

                this.val = val;

        }

}

0 {; z. E6 X* C

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

        public TreeNode findLCA(TreeNode root){

                if(root == null) return root;

                dfsFind(root, 0);

                return LCA;

        }

/ {4 C+ ]7 k0 H/ Q6 ^. p( I6 ~

        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;

                        }

& F7 C) _1 @4 k% t

                        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;

                }

                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;

                    }

                }

        }

}

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

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

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

祝大家都有好offer！

+ y! O8 R- l) v* n' N

running_man

感谢zsz1990ustc分享~~~

Helen

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