《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2270|回复: 4
收起左侧

twitter电面

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

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

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

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

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

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
后半小时,两道coding 题:

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


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>. From 1point 3acres bbs


要求log(V),当输入edge数量特别多时,算法最终复杂度cap在V log(V)。. Waral 鍗氬鏈夋洿澶氭枃绔,

问这题之前面试官还问我了不了解map reduce,我说一点点吧。其实这题是map reduce的思想,不是太难想,就是各种hash。但是本人对map reduce没有太多了解,厚颜无耻的问了tip,给了O(V)的算法。但是面试管对于复杂度的讨论不是很满意,最后告知一个小优化可以达到log(V),感觉挺tricky的一个东西,当然可能map reduce大牛觉得很简单,囧。
. visit 1point3acres.com for more.
后来网上查了一下还是篇2012年的paper,想仔细了解的同学可以去看看,.1point3acres缃
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
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-19 15:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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