一亩三分地论坛

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

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

twitter电面

[复制链接] |试试Instant~ |关注本帖
kingyy 发表于 2015-5-29 07:38:05 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 博士 全职@Twitter - 内推 - 技术电面 |Pass在职跳槽

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

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

x
前半个小时完全是在讲楼主做过的项目,这是一个偏向于数据挖掘的码工职位,所以问了很多machine learning的东西。完全是对楼主做过的项目进行提问,为何要用这个算法,为了要用那个算法,如果换成这个算法会怎么样,诸如此类的。大家可借鉴的东西不多,就不写了。
. from: 1point3acres.com/bbs

后半小时,两道coding 题:

1. 给一个graph:一个vector里面存得所有node,每个node有个neighbor vector。如何找到connected components,即相互联通的所有vertices。
DFS或者BFS瞬秒。


2. 如果这个graph不是统一给你的,而是每次只给你一个edge,如何去做。比如:
(1). input: edge<1, 3>, output connected compoents: <1,3>
(2). input: edge <1, 5>, output connected compoents: <1,3,  5>
(3). input: edge <2, 6>, output connected components: <1, 3, 5>, <2, 6>
(4). input: edge <2, 3>, output connected compoenents: <1, 2, 3, 5, 6>

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
要求log(V),当输入edge数量特别多时,算法最终复杂度cap在V log(V)。

问这题之前面试官还问我了不了解map reduce,我说一点点吧。其实这题是map reduce的思想,不是太难想,就是各种hash。但是本人对map reduce没有太多了解,厚颜无耻的问了tip,给了O(V)的算法。但是面试管对于复杂度的讨论不是很满意,最后告知一个小优化可以达到log(V),感觉挺tricky的一个东西,当然可能map reduce大牛觉得很简单,囧。

后来网上查了一下还是篇2012年的paper,想仔细了解的同学可以去看看,
http://arxiv.org/pdf/1203.5387.pdf

评分

3

查看全部评分

blueseen 发表于 2015-5-29 16:34:35 | 显示全部楼层
第二题可以用并查集吧
回复 支持 反对

使用道具 举报

gbbbb 发表于 2015-6-18 17:42:38 | 显示全部楼层
...第二题并查集
回复 支持 反对

使用道具 举报

wegnahz 发表于 2015-9-30 09:03:09 | 显示全部楼层
并查集?map reduce怎么弄
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-10-1 01:43:37 | 显示全部楼层
请问dfs和bfs怎么做?只会union find。。。做这个题。lintcode上面有,为了用bfs,我把有向图转成无向图做的,保证a->b并且b->a
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 13:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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