一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4555|回复: 36
收起左侧

休斯顿初创企业 SocialGear onsite面经

[复制链接] |试试Instant~ |关注本帖
zsz1990ustc 发表于 2016-3-7 10:30:25 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@SocialGear - 网上海投 - Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x



最近在找工作,到处网上找内推或者海投。忘了在哪个网页上看到的什么 Top Startup in Houston 排名,看到了一家叫 SocialGear的, 点进去发现这是一个以基于event的网络社交平台,感觉蛮有新意的。


主页上发现他们也有招聘信息,就在他们留言板块留个言。没想到很快就有邮件联系我了。于是我发了简历给他们。哈哈哈,人品不错,半小时的电话面,随便聊聊,又问了一道比较easy的算法题,后来就拿到 onsite了 :D

. Waral 鍗氬鏈夋洿澶氭枃绔,
这家公司在离AMC 30 不远的地方,一个写字楼里面。办公室环境优雅,还有清丽的背景音乐。面试官是一位中国小哥,很友善的感觉。先是聊聊简历,互相介绍一下。然后就开始进入主题了。

我也是有备而来,已经注册了SocialGear账号并explore了各种功能。我叙述了我对他们平台的了解和建议,他表示很满意。他家因为是做网络社交的,就问了我一些网络开发的一些基本概念。什么是前端,什么是后端,Spring是啥,RESTful是啥,与网页互动有哪几种形式(Get,Post, Put, Delete)等等。答完了之后,他又给我展示他们的平台功能,然后到了lottery那一页。他就问我系统设计题,如何设计抽奖功能。就是点抽奖的按钮,反馈一个我最熟悉java,就在白板上用java写,写了类叫lottery,假设有个类叫User,那么我就开始用HashMap来存User,我想key是整数,然后value是user,就random函数 pick 一个key嘛。。结果就二了,arraylist不就行了嘛。。这个可能要扣分。。抽到了这个user,那我下次摇奖的时候,还要考虑如何不要重复上次中奖的那个user。还有一点是他们是event based的,就是进入这个event,参加抽奖的 user 是这个event的 user,其他event的 user不算。面试官各种 follow up讨论细节,我答得也是磕磕绊绊。然后又问我如何洗牌,我说产生两个 random,然后swap,这样不断很多次,就洗牌了,注意的是要保证每个牌都要access到,那我就for loop一下。

接着又来了一道算法题。求 多叉树 的最底层 所有 叶子的最小公共祖先。面试官先让我试试 二叉树,我用DFS(其实应该用BFS)找到最底层的那些叶子,然后两两找公共祖先(LCA)。最后是O(n^2)的复杂度。后来真想不到怎么优化了。面试官特别nice,他说没关系,然后他教我做,用DFS去找,同时记录每个访问的depth,然后找的时候就存 可能的最底层叶子 和 LCA,然后后面发现更深的node,前面的就删,然后再记录 可能的最底层叶子 和 LCA。然后这样一次DFS就搞定啦,O(n)时间。
. Waral 鍗氬鏈夋洿澶氭枃绔,

面了1个半小时吧,真是很烧脑的。。。毕竟挺火的start up,招人的bar挺高。

对了,这是公司网站:
https://socialgear.us/
. 1point 3acres 璁哄潧
主页就有留言板,地里的朋友有兴趣的可以投个简历试试。


发个面经在这,求攒人品啦~~~
. 1point3acres.com/bbs





补充内容 (2016-3-7 11:43):
和面试官已线下联系,本人可同时提供内推~

补充内容 (2016-4-2 10:14): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
最近SocialGear据说又拿到一笔融资。他们的App也进入了3.0版。4月9日,他们将举办新闻发布会也是鸡尾酒宴会。届时可以投简历给公司高层,方便的话估计直接可以onsite了。这是活动具体信息:http://goo.gl/hvR1UL

评分

6

查看全部评分

songyangUSTC 发表于 2016-4-20 09:08:39 | 显示全部楼层
Wrath 发表于 2016-4-15 09:30
这个case会返回2,是不是应该返回7才对?
. 1point3acres.com/bbs
class TreeNode:
    def __init__(self, value):.1point3acres缃
        self.value = value
        self.children = []

def dfs(root, depth):
    if len(root.children) == 0:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        return [root, depth]
    children = root.children
. Waral 鍗氬鏈夋洿澶氭枃绔,
    max_depth = 0
    max_depth_LCA = None
    for child in children:. more info on 1point3acres.com
        cur = dfs(child, depth + 1)
        if cur[1] > max_depth:
            max_depth = cur[1]
            max_depth_LCA = cur[0] 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        elif cur[1] == max_depth:
            max_depth = cur[1]
            max_depth_LCA = root

    return [max_depth_LCA, max_depth]


def treeLCA(root):. From 1point 3acres bbs
    if root == None:
        return None
    return dfs(root, 0)[0]

谢谢你的指正,我之前写的代码有bug,这是我改正优化好的代码。
回复 支持 1 反对 0

使用道具 举报

 楼主| zsz1990ustc 发表于 2016-3-7 10:53:51 | 显示全部楼层
刚看了一下那个留言板好像不能用了,估计是系统在升级吧。想投简历直接给hr发邮件吧,support@socialgear.us
回复 支持 反对

使用道具 举报

cicean 发表于 2016-3-7 11:12:34 | 显示全部楼层
楼主能内推么?请问留言板是什么
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-3-7 11:16:22 | 显示全部楼层
zsz1990ustc 发表于 2016-3-7 10:53. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
刚看了一下那个留言板好像不能用了,估计是系统在升级吧。想投简历直接给hr发邮件吧,
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主能详细说说多叉树那道题么?
回复 支持 反对

使用道具 举报

bitcpf 发表于 2016-3-7 11:18:51 | 显示全部楼层
在Houston的,我一直以为是在Austin。。。
回复 支持 反对

使用道具 举报

dm37537 发表于 2016-3-7 11:28:18 | 显示全部楼层
他们竟然有office了
回复 支持 反对

使用道具 举报

 楼主| zsz1990ustc 发表于 2016-3-7 11:38:15 | 显示全部楼层
cicean 发表于 2016-3-7 11:12
楼主能内推么?请问留言板是什么

留言板因为系统升级不能用暂时。我和面试官线下联系了。他说欢迎我的朋友们也投简历。我邮箱是 zsz1990ustc@gmail.com。发我邮件,“SDE SocialGear” as 主题,然后一段第三人称自我介绍,附上你的简历。我帮你内推!
回复 支持 反对

使用道具 举报

谎言之躯 发表于 2016-3-7 11:50:10 | 显示全部楼层
楼主,这个公司给不给外州的人出onsite的机票钱?
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-3-7 12:48:58 | 显示全部楼层
cicean 发表于 2016-3-7 11:12
楼主能内推么?请问留言板是什么
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
你不是有offer了么,怎么还找工作啊
回复 支持 反对

使用道具 举报

bitcpf 发表于 2016-3-7 13:12:00 | 显示全部楼层
cicean 发表于 2016-3-6 21:12
楼主能内推么?请问留言板是什么

师姐还在TX呢?
回复 支持 反对

使用道具 举报

cicean 发表于 2016-3-7 14:57:35 来自手机 | 显示全部楼层
zxl9171 发表于 2016-3-7 12:48. visit 1point3acres.com for more.
你不是有offer了么,怎么还找工作啊

上面说不是中国小哥很nice 么楼主package 多少?
回复 支持 反对

使用道具 举报

songyangUSTC 发表于 2016-3-11 17:04:45 | 显示全部楼层
求楼主详细说说多叉树那道题!万分感谢!!!
回复 支持 反对

使用道具 举报

tldxk 发表于 2016-3-12 12:29:58 | 显示全部楼层
楼主,那道算法题,用DFS找到当前可能的最底层叶子和LCA,每次在找LCA时,是否也是在找两两之间的LCA呢?这样复杂度也很高啊,而且貌似还不如直接找到最底层的叶子再找LCA呢?
回复 支持 反对

使用道具 举报

 楼主| zsz1990ustc 发表于 2016-3-13 23:56:11 | 显示全部楼层
zxl9171 发表于 2016-3-7 11:16
楼主能详细说说多叉树那道题么?

这几天一直在钻研这道题,并回忆当时面试官的指导,现在算是解决出来啦!


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


求p点和q点的LCA, 一次DFS回溯遍历搞定,找到第一个target后(比如p),记录回溯时到达的shallowest level,和对应的那个节点(就是LCA candidate),回溯过程中突然发现第二个target (比如q),这是 此前回溯过程中到达的shallowest level和对应的那个节点 tempLCA就是LCA啦。


/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/. Waral 鍗氬鏈夋洿澶氭枃绔,
public class Solution {
        int shallowest = 0;   // the shallowest level that I visited in backtracking after I got the first target node
        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.鐣欏璁哄潧-涓浜-涓夊垎鍦
        
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return root;
                dfsFind(root, p, q, 0);
                return LCA;
    }

    public void dfsFind(TreeNode root, TreeNode p, TreeNode q, int curLev){. 鍥磋鎴戜滑@1point 3 acres
                if (root == p || root == q) {. 1point 3acres 璁哄潧
                        if (!getFirstTarget){
                                getFirstTarget = true;
                                shallowest = curLev;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                tempLCA = root;
                        }
                        LCA = tempLCA;
                }
               
            if (getFirstTarget && curLev <= shallowest) {  //after get the first deepest leaf node candidate, mark the shallowest level when backtracking
                        shallowest = curLev;
                        tempLCA = root;. more info on 1point3acres.com
                }
               
                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;
                            tempLCA = root;
                    }
                }
               
                if (root.right != null){   //dfs for right node. 1point 3acres 璁哄潧
                    dfsFind(root.right, p, q, curLev + 1);
.1point3acres缃                    if (getFirstTarget && curLev <= shallowest) {    //mark the shallowest level when backtracking
                            shallowest = curLev;
                            tempLCA = root;
                    }
                }.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
}.鐣欏璁哄潧-涓浜-涓夊垎鍦

如果看官能理解我上面的解法。就能看懂我解决多叉树那个原题啦。

// defination for N-ary TreeNode.
class TreeNode{
        int val;
        ArrayList<TreeNode> children = new ArrayList<TreeNode>();
        public TreeNode(int val){. 1point3acres.com/bbs
                this.val = val;
        }
}

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. Waral 鍗氬鏈夋洿澶氭枃绔,

        public TreeNode findLCA(TreeNode root){
                if(root == null) return root;.1point3acres缃
                dfsFind(root, 0);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                return LCA;
        }
      
        public void dfsFind(TreeNode root, int curLev){. Waral 鍗氬鏈夋洿澶氭枃绔,
                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;
                        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
                       . From 1point 3acres bbs
                        if (curLev == deepest){        //if current level is the deepest, the candidate LCA might be the result
                                LCA = tempLCA;
                        }
                       
                        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;. visit 1point3acres.com for more.
                }
            
                ArrayList<TreeNode> children = root.children;
                for (TreeNode child : children){
                        dfsFind(child, curLev + 1);.1point3acres缃
                        if (getFirstTarget && curLev <= shallowest) {.1point3acres缃
                            shallowest = curLev;         //mark the shallowest when backtracking
                            tempLCA = root;
                    }-google 1point3acres
                }
        }
}

一遍DFS回溯遍历搞定,O(n)时间。空间上就加了几个变量作为mark, 不考虑栈空间的话,那就是 O(1) 空间。

注释已经写得比较清楚了。我懒得打字解释了,你们画画图就明白了。要是还不明白,我再画画图给你们解释~~
回复 支持 反对

使用道具 举报

 楼主| zsz1990ustc 发表于 2016-3-14 06:09:03 | 显示全部楼层
tldxk 发表于 2016-3-12 12:29
楼主,那道算法题,用DFS找到当前可能的最底层叶子和LCA,每次在找LCA时,是否也是在找两两之间的LCA呢?这 ...
. 1point3acres.com/bbs
你看我的解法。并不是两两找LCA的。而是在回溯遍历的过程中,去标记可能的LCA,最后一次遍历即可得到答案。
回复 支持 反对

使用道具 举报

joana92 发表于 2016-3-14 07:23:25 | 显示全部楼层
所有叶子节点的最小公共祖先,为什么不是这棵树的根节点?
回复 支持 反对

使用道具 举报

 楼主| zsz1990ustc 发表于 2016-3-14 08:10:57 | 显示全部楼层
joana92 发表于 2016-3-14 07:23
所有叶子节点的最小公共祖先,为什么不是这棵树的根节点?

是最深的那些叶子
回复 支持 反对

使用道具 举报

谎言之躯 发表于 2016-3-16 02:33:29 | 显示全部楼层
楼主,. from: 1point3acres.com/bbs
if (curLev > deepest){  //if current level is larget than deepeest, reset all the marks
                            deepest = curLev;. visit 1point3acres.com for more.
                            getFirstTarget = false;
                            shallowest = curLev;
                                deepest = curLev;
                                tempLCA = root;
.1point3acres缃                                LCA = tempLCA;
                    }

这段代码应该移到if (!getFirstTarget)前面吧?
回复 支持 反对

使用道具 举报

 楼主| zsz1990ustc 发表于 2016-3-16 10:01:12 | 显示全部楼层
谎言之躯 发表于 2016-3-16 02:33. 1point3acres.com/bbs
楼主,. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
if (curLev > deepest){  //if current level is larget than deepeest, reset all the marks
   ...

当然不行啊,移到前面reset all marks, 那么 getFirstTarget 不一直都是 false了吗。
我自己都写了很多testcase测了,没问题。.鐣欏璁哄潧-涓浜-涓夊垎鍦
你要移到前面,你试试,一定会错的 :P
回复 支持 反对

使用道具 举报

谎言之躯 发表于 2016-3-16 10:33:02 | 显示全部楼层
zsz1990ustc 发表于 2016-3-16 10:01
当然不行啊,移到前面reset all marks, 那么 getFirstTarget 不一直都是 false了吗。
我自己都写了很多t ...

楼主,这题太他妈难了。我觉得工作上都用不到这算法。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
话说你拿到offer没有? 这公司跟我约电面,结果约着约着就失联了。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 10:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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