找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

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

[复制链接]

4

主题

1

精华

61

积分

资深会员

Rank: 2

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

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

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

x
本帖最后由 Sophia 于 3-16-2016 03:16 PM 编辑
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& O5 J6 o* N) L9 u! l( e  c9 p" V
这是他家网站: https://socialgear.us/
' _2 p. ^1 v  F1 G- ?5 M! d) E- S3 j1 y
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
/ [8 d  g9 I1 T" E
于是这几天一直在钻研这道题,并回忆当时面试官的指导,现在算是解决出来啦!
% r+ e2 [8 l0 u8 y. {. {3 o$ ~! T6 B, w5 n+ L

7 v: }4 h/ v1 \% h我们先考虑最基本的Binary Tree的两个node的LCA 怎么做(没有parent node)。一般网上的解法都用Divide and Conqure,就是左子树递归不为null,柚子树递归不为null, 则当前node为LCA。 我回忆当时那个面试官思路后,另辟蹊径,写出以下解法。看懂我解决多叉树那道题的前提,就是要看懂这个解法。. [5 a! p+ S  d/ L, y, F- ?1 w9 ]
9 _. y# r) F* K

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
! @2 K; @  [% `; a
/**
0 `9 L& c2 s8 ~ * Definition for a binary tree node.0 E( u' [( s( O* A5 r
* public class TreeNode {
0 S2 d% y; E' ~: n *     int val;  a. x  @! s' Y: A
*     TreeNode left;. p) X) d! t6 E0 G5 z( R' h
*     TreeNode right;: u) Q# g. j* N
*     TreeNode(int x) { val = x; }! w! p( l8 T) [0 A7 X) v+ W
* }3 b- _  ^6 V% h& @: r
*/! t) L4 S! i$ Z# v! D* W. m; Y
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& p% K( ?) C4 ~0 u! Q2 z" u
        TreeNode tempLCA;   // the node corresponding the shallowest level, which is a LCA candidate' r; o9 x* m# k6 J# B8 e$ C
        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;9 G  i# f% q" F, a) M8 m7 R
                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, b7 X) V; m( e$ U# w
    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){' u& J0 \5 E3 ^# n4 o; O! I3 ]+ D
                                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;% \& ^9 t+ G+ `6 I  f
                }
6 ?* Y) `% a+ L& l; W0 D& ^5 F                " l8 A5 d2 ]/ z  t; K
            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;% s( z$ k4 Z& u2 J% s  u+ |
                        tempLCA = root;
0 O) S. ]5 V/ s* s" b6 s' s                }, o- R+ z- a# v$ n
               
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/ |. Y0 Z2 x1 I, _) t! O) U5 i
                            shallowest = curLev;* Q2 R1 S, v% p( b: K1 K
                            tempLCA = root;
: _. s2 j! B* p, A' E3 Q: V5 o                    }* _1 M/ x; d0 _% g+ }) E+ R" r  `
                }; ~7 j, [, q% ]- h+ E
        }
7 k- x; B+ c+ v, |; n* Z% x' y4 C$ t8 L}& W& q. T, t  _2 ]9 R

1 o5 M! W, e% f( M  n如果看官能理解我上面的解法。就能看懂我解决多叉树那个原题啦。4 b' p( p+ `, j% V9 T) M
5 p7 @' Q" T: I1 Y
// defination for N-ary TreeNode.: R! N& g' c, Z* k* G
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
0 I0 G+ k# m7 J+ u% t
        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;
                        }
3 U# j, G( Q" ?& n% f+ r
                        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;
                    }
                }
& H: b& m3 M9 j5 [
            if (getFirstTarget && curLev <= shallowest) {        
                        shallowest = curLev;  //after get the first deepest leaf node candidate, mark the shallowest when backtracking
                        tempLCA = root;
                }
( a' x/ n  A4 t. M' q: Y* M; j! }
                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;
                    }
                }
        }
}
0 L5 q6 s" x$ }" W- K( s  w) i
注释已经写得比较清楚了。我懒得打字解释了,你们画画图就明白了。要是还不明白,我再画画图给你们解释~~
/ g3 o4 q8 \9 w* L
这家StartUp最近似乎又拿了一轮融资。bar比较高,也是可以理解。我还没有收到他家后续消息。
9 @8 i  I1 w& h
Anyaway,在这里发个帖子,求攒人品~~ 也求版主多给些米,我的阅读权限太低,好多帖子看不了。。
祝大家都有好offer

+ y! O8 R- l) v* n' N
/ @8 x9 z, F9 P0 V4 u! E

评分

参与人数 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分享~~~好人一生平安~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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