一亩三分地论坛

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

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

处女面-Zillow电面

[复制链接] |试试Instant~ |关注本帖
guii 发表于 2014-11-6 04:12:30 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Zillow - 网上海投 - 技术电面 |Other

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

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

x
Hi guys,
人生处女面就这样结束啦,再来个处女贴吧。之前在地里看了很多人的面经,很受用,所以也想向大家学习,及时分享。
一个Manager面的,Graff,美白。
1. 自我介绍:他先说说他自己,我再说说我最近的proj,其实就是简历里前两个proj。
2. 做题之前他说他自己非常喜欢tree,我心想:完b。
    题目:lca (lowest common ancestor), with parent pointer。之前在地里见过这道题,所以心里还算放松。但是觉得有parent比较简单就没有多去留意,面之前没写带parent的代码。
    一边讨论一边做题,说了很多让他觉得兴奋的东西,我心想:至此表现还不错。大家面试时候一定多交流,会增加好感度我觉得。. visit 1point3acres.com for more.
    题目不难,我用了HashSet保存一个node的parent,然后遍历另一个,time: O(logN), space: O(logN)。
    写出来之后他说在编译器上运行没错,great。
    但是此次面试从现在开始就是跪的节奏了。
    follow up来了,让优化。我心想:都是logN了还优化什么。. more info on 1point3acres.com
    最终没有给出优化代码,一直在讨论,我也慌了,所以脑子一直动不起来。
    面完想了想优化的方法,他最后也提到了,not faster, just constant space。
    我觉得好像只保存该node,node.prarent, node.parent.left (or right)就可以吧?欢迎大家指点。
-google 1point3acres3. 最后我问了问zillow有啥关于big data的技术,因为我实习有接触过一些Hadoop,MapReduce的东西。
    他说zillow也在研究如何应用MapReduce。
无论如何都要move on,因为这只是个开始。希望分享的东西对大家有帮助。
Best,
Guii

评分

3

查看全部评分

kurtwang 发表于 2014-11-6 04:18:29 | 显示全部楼层
第一题感觉可以先找到两个node的深度然后把两个node上升到一个level,然后再一起向上遍历直到parent相等
回复 支持 1 反对 0

使用道具 举报

mayingjie116 发表于 2014-11-6 04:21:32 | 显示全部楼层
郭总咱们一起加油!
回复 支持 反对

使用道具 举报

 楼主| guii 发表于 2014-11-6 04:24:58 | 显示全部楼层
kurtwang 发表于 2014-11-6 04:18. 1point3acres.com/bbs
第一题感觉可以先找到两个node的深度然后把两个node上升到一个level,然后再一起向上遍历直到parent相等
.鐣欏璁哄潧-涓浜-涓夊垎鍦
对对对,应该是这样。哎,第一次面,感觉遇到预想之外的问题就很慌,静不下心。感谢!赶紧写一遍!
回复 支持 反对

使用道具 举报

 楼主| guii 发表于 2014-11-6 04:25:25 | 显示全部楼层
mayingjie116 发表于 2014-11-6 04:21. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
郭总咱们一起加油!
. 1point 3acres 璁哄潧
哈哈哈,好像名字太明显了!木啊!!!
回复 支持 反对

使用道具 举报

guomin1314 发表于 2014-11-21 14:40:17 | 显示全部楼层
lz是用递归写的吗
回复 支持 反对

使用道具 举报

guomin1314 发表于 2014-11-21 14:42:12 | 显示全部楼层
是BST还是just BT
回复 支持 反对

使用道具 举报

guomin1314 发表于 2014-11-21 14:42:17 | 显示全部楼层
是BST还是just BT
回复 支持 反对

使用道具 举报

 楼主| guii 发表于 2014-11-22 10:38:06 | 显示全部楼层

是BT,就是一个普通二叉树
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-11-22 10:59:18 | 显示全部楼层
guii 发表于 2014-11-6 04:24
对对对,应该是这样。哎,第一次面,感觉遇到预想之外的问题就很慌,静不下心。感谢!赶紧写一遍!

这样复杂度太高了。。我觉得先用parent指针找root,然后分治找LCA。BTW,楼主你的算法不是O(logn)的,考虑不平衡的二叉树
回复 支持 反对

使用道具 举报

yzl232 发表于 2014-11-22 11:03:26 | 显示全部楼层
是的 。可以优化到O(1) space.  但是不容易想
回复 支持 反对

使用道具 举报

 楼主| guii 发表于 2014-11-22 11:08:22 | 显示全部楼层
shinichish 发表于 2014-11-22 10:59
这样复杂度太高了。。我觉得先用parent指针找root,然后分治找LCA。BTW,楼主你的算法不是O(logn)的,考 ...

多谢补充!没错!他出题时候提到了,就考虑平衡树,所以我也没多想,就给了他O(logn)
回复 支持 反对

使用道具 举报

lcl3356897 发表于 2014-11-22 11:22:37 | 显示全部楼层
感谢分享!. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
上的Web课在用Zillow的API. visit 1point3acres.com for more.
楼主加油!
回复 支持 反对

使用道具 举报

纠结帝 发表于 2014-11-22 12:06:19 | 显示全部楼层
lz你这个做法不算time: O(logN)吧, 保存了hashset之后遍历另一个node的时候每遇到一个parent 都要在hashset里面找存不存在这个node  这个查找本身就是logN了
所以logN = H, 应该是O(H^2) ?
回复 支持 反对

使用道具 举报

狂暴CNM地 发表于 2014-11-22 12:59:45 | 显示全部楼层
如果不用额外空间的话 就BFS找出层数 然后一起往上
. 1point3acres.com/bbs
或者两个NODE走到根 然后反过来找第一个不同的点。。 毕竟HASH不是严格的O(1) 当然hash也可以
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-11-22 13:18:51 | 显示全部楼层
guii 发表于 2014-11-22 11:08
多谢补充!没错!他出题时候提到了,就考虑平衡树,所以我也没多想,就给了他O(logn)

加油楼主!我提交了zillow的assignment,2周过去了,为啥还是没有任何消息。。。
回复 支持 反对

使用道具 举报

 楼主| guii 发表于 2014-11-22 13:26:00 | 显示全部楼层
shinichish 发表于 2014-11-22 13:18
加油楼主!我提交了zillow的assignment,2周过去了,为啥还是没有任何消息。。。

貌似他们有点儿忙,本来这周给我二面,结果HR说他们太忙改到下周了。加油啦
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-11-22 13:31:45 | 显示全部楼层
guii 发表于 2014-11-22 13:26
貌似他们有点儿忙,本来这周给我二面,结果HR说他们太忙改到下周了。加油啦

嗯,加油
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-11-24 01:49:00 | 显示全部楼层
时间的确很难再优化了,空间优化的话就是让两个节点到达同样的深度(通过parent可以方便的计算出深度信息)然后再同时网上寻找第一个共同的节点
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-12-12 02:01:56 | 显示全部楼层
pyemma 发表于 2014-11-23 09:49
时间的确很难再优化了,空间优化的话就是让两个节点到达同样的深度(通过parent可以方便的计算出深度信息) ...

有道理,我去实现一下
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 01:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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