找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 3084|回复: 12
收起左侧

[Startup公司] 休斯顿最火初创 SocialGear 的一道onsite面经题

[复制链接]

4

主题

1

精华

61

积分

资深会员

Rank: 2

积分
61
发表于 3-13-2016 10:51 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 3-16-2016 03:16 PM 编辑 6 V( I) p8 C" B) {% ]% k
, ?+ ?+ N, e" t: _
上周去休斯顿一家很火的startup,叫SocialGear的公司去onsite6 a2 j. t  D3 Y# w

7 P8 I; Q& J: X! e这是他家网站: https://socialgear.us/
. N0 I7 s$ d7 z% ~1 [3 Z$ H  h+ {5 i4 @9 ?" T& i- ^
onsite一个半小时,考了一些Web开发的基本知识,如Spring是啥,如RESTful是啥。然后一道程序设计题,设计抽奖系统。接着还有洗牌程序。我跟着面试官的提示,算是解决了。0 R5 n4 p- {; n/ c; K4 O0 E
3 v+ i( P  d" x$ B: \
最后一道算法题,懵了。求 多叉树 的最底层 所有 叶子的最小公共祖先。面试官先让我试试 二叉树,我用DFS(其实应该用BFS)找到最底层的那些叶子,然后两两找公共祖先(LCA)。最后是O(n^2)的复杂度。后来真想不到怎么优化了。面试官很nice,教了我一通,我当时是明白了。回家之后又忘了。) `) k$ ^# P- G6 A" |6 a. g& @

) [- D5 s. \) c

) P( v& N' K' j于是这几天一直在钻研这道题,并回忆当时面试官的指导,现在算是解决出来啦!9 d1 s' ^" C: e% \7 H  t

  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
4 ?5 U" [3 c% F3 P$ O* q& l5 s( z2 m
求p点和q点的LCA, 一次DFS回溯遍历搞定,找到第一个target后(比如p),记录回溯时到达的shallowest level,和对应的那个节点(就是LCA candidate),回溯过程中突然发现第二个target (比如q),这是 此前回溯过程中到达的shallowest level和对应的那个节点 tempLCA就是LCA啦3 b8 Z. D# H2 e8 Y& t

$ w' O' X0 [% ~# H; E6 o
% Z8 z8 h# t$ ?. G. K
/**
) E; D6 V0 l* K; ^. f+ \* | * Definition for a binary tree node.. U/ Q1 i" J: N8 W7 \
* public class TreeNode {* z' O# Z' l6 _7 m! [2 C# `
*     int val;1 V) v+ b, |3 }* ~) ~3 o) |0 h
*     TreeNode left;4 o' y2 L6 M/ |1 p) E# @1 j, L7 F
*     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 */" O) }; a6 `. m9 @
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( s. e( L7 H* n% p% S! s! ~
        TreeNode tempLCA;   // the node corresponding the shallowest level, which is a LCA candidate/ W7 J- c, K* P  w
        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) {3 F) v: P* X7 W/ E- f. a
        if(root == null) return root;
. a, I2 i+ u- T                dfsFind(root, p, q, 0);4 H8 W) \2 T/ D$ L- H
                return LCA;! n2 m* J; t, ~& K9 G
    }
$ 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) {4 p5 p/ F" a+ @7 k! _
                        if (!getFirstTarget){
. ~# f5 G( o0 j2 x9 {; u" i                                getFirstTarget = true;& c7 L) M: ^+ T: X' F
                                shallowest = curLev;
/ E% ?3 C5 P0 c7 V3 e5 t7 L                                tempLCA = root;
8 ]/ {( b" Z9 E8 Y' g                        }( _2 O  x; w& `' z
                        LCA = tempLCA;( m* E! O1 }. q+ C( |, [& V
                }
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;' h2 B* I; a, z2 |
                        tempLCA = root;2 m# \/ U8 V4 _5 a- P, O
                }
1 F9 n5 O, `( a                / [4 ?: R; o1 \( B" @9 F
                if (root.left != null){   // dfs for left node # ~2 Z0 M8 q% n( j: w
                    dfsFind(root.left, p, q, curLev + 1);8 M2 U/ O' v6 E1 x1 O7 C
                    if (getFirstTarget && curLev <= shallowest) {   //mark the shallowest level when backtracking# M1 C0 _2 F- \, F3 J- z! s
                            shallowest = curLev;
: N5 S  D$ H1 d                            tempLCA = root;  Z7 Q% k/ H$ [0 g9 R
                    }
! H; w6 b8 h% q+ Q- r8 Z4 n+ W                }5 ]7 U! ]. ?1 P* U5 T
                2 w+ T+ W$ L$ g+ r% ^
                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;7 M0 z, n) k) ]  m6 t# ]. y
                    }8 G9 e- {0 b* ?
                }) Z/ H+ X% n' G# }6 G: \
        }% e) \4 T* {0 u% W
}
! ~5 x. K: u8 {9 I8 D
- s# n+ K* g+ ?/ _2 V2 Q! c如果看官能理解我上面的解法。就能看懂我解决多叉树那个原题啦。9 G$ }4 G2 j  g

  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;
        }
1 k: y* |7 @( S3 t
        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;
                        }
- i5 c* ~$ [- q# R7 g
                        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;
                    }
                }
  m( C- B, \( r6 X- o, ]- @& H
            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;
                    }
                }
        }
}
  N+ h& ]9 j( s' V, l& M; ?5 f1 h: O
注释已经写得比较清楚了。我懒得打字解释了,你们画画图就明白了。要是还不明白,我再画画图给你们解释~~

% T" f# ?  b* t2 g
这家StartUp最近似乎又拿了一轮融资。bar比较高,也是可以理解。我还没有收到他家后续消息。

/ n- Y5 Y# H7 ^8 m
Anyaway,在这里发个帖子,求攒人品~~ 也求版主多给些米,我的阅读权限太低,好多帖子看不了。。
祝大家都有好offer
5 W2 f; V; \* q( q2 S% {# \: i

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

评分

参与人数 1金钱 +6 收起 理由
Sophia + 6 感谢您的认真和用心的分享!大米满满送上!

查看全部评分

0

主题

0

精华

10

积分

新米人

Rank: 1

积分
10
发表于 3-13-2016 08:47 PM 来自美国米群网手机版 | 显示全部楼层
感谢zsz1990ustc分享~~~

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 3-14-2016 09:16 PM | 显示全部楼层
感谢zsz1990ustc分享~~~好人一生平安~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表