一亩三分地论坛

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

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

Twitter电面

[复制链接] |试试Instant~ |关注本帖
u-r-the-one 发表于 2016-4-20 04:36:51 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Twitter - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
地里Twitter面经不多 给小伙伴们发来面经参考 希望自己能赶快找到工作
是印度小哥 LZ第一次跟印度人面试 其实感觉还不错 一上来没有问任何问题、简历、之类的 直接就说我们做题吧 题目是:print all acyclic path in a graph

就只有这一句很简单话 LZ先问 有向图吗 小哥说 你可以自己假设 LZ选择了假设有向图 然后我问图中有环吗 小哥说了acyclic path LZ当时就以为没有环 然后写了基本的DFS 写完之后 小哥说 看起来不对啊 然后小哥给我写了一个test case(没写这个case的答案)然后我才明白过来原来有环 然后很快就改好了代码 然后run 小哥又说不对!此时LZ内心是崩溃的 你到底要怎样 小哥这才把他写的test case的正确结果给了出来

大概是这样的 输入1-->2 1-->3 1-->4 2-->3 3-->1 3-->2  然后LZ的code print的是 1,2,3   1,3,2  1,4  但是小哥要的其实是1; 1,2; 1,2,3; 1,3; 1,3,2; 1,4 就是要把每条路上的所有结果都print出来 但是没时间改了 小哥说没关系就这样吧 然后他问了时间复杂度 我分析了之后 小哥就说结束了


鏉ユ簮涓浜.涓夊垎鍦拌鍧.
希望大家都offer多多


补充内容 (2016-4-19 16:41):
忘记说了 输入还有告诉你start node 就是path从哪个点开始走

补充内容 (2016-4-19 16:44):. 1point3acres.com/bbs
还有就是 如果这是一个complete graph 告诉start node 那么一共有多少条path

评分

2

查看全部评分

monolock 发表于 2016-4-20 11:00:49 | 显示全部楼层
这样做可以吗:
1. 先loop一遍,分别把每个节点的后序节点存起来到hashmap<node, List<node>>里
2. 从起始点开始,做dfs,用hashmap记录这次路径上出现过的点,遇到出现过的或者没有后续节点的就停止(按照楼主的提示,应该每一层都加到结果的List里。。)
时间复杂度感觉是O(n!)?。。不太会算。。
回复 支持 1 反对 0

使用道具 举报

jy_121 发表于 2016-4-20 05:39:15 | 显示全部楼层
感谢分享,问下楼主时间复杂度应该是多少?
回复 支持 反对

使用道具 举报

 楼主| u-r-the-one 发表于 2016-4-20 05:41:13 | 显示全部楼层
忘记说了 输入还有一个start node 就是告诉你path从哪里开始走
回复 支持 反对

使用道具 举报

 楼主| u-r-the-one 发表于 2016-4-20 05:48:43 | 显示全部楼层
jy_121 发表于 2016-4-19 16:39
感谢分享,问下楼主时间复杂度应该是多少?

我觉得worst case是n^n吧。。。
回复 支持 反对

使用道具 举报

lzk031 发表于 2016-4-20 05:59:06 | 显示全部楼层
感谢分享!
感觉Twitter好难啊,电面就出这么复杂的图,又是烙印,楼主居然轻松搞定,太厉害了!zhu楼主offer多多~
回复 支持 反对

使用道具 举报

ffllgg 发表于 2016-4-20 10:36:27 | 显示全部楼层
什么时候收到电面通知的?
回复 支持 反对

使用道具 举报

 楼主| u-r-the-one 发表于 2016-4-20 12:27:34 | 显示全部楼层
monolock 发表于 2016-4-19 22:00-google 1point3acres
这样做可以吗:
1. 先loop一遍,分别把每个节点的后序节点存起来到hashmap里
2. 从起始点开始,做dfs,用 ...

对!我大概就是这么做的 还有就是每次recursion都先print一下 这样才能得到1; 1,2; 1,2,3这种  时间复杂度我也不会很会算 感觉像是n! 因为给定起点的complete graph有(n-1)!条能包含所有node的path
回复 支持 反对

使用道具 举报

 楼主| u-r-the-one 发表于 2016-4-20 12:28:24 | 显示全部楼层
ffllgg 发表于 2016-4-19 21:36
什么时候收到电面通知的?

大概在4.8号 他们家hr很慢。。。这是上周面的
回复 支持 反对

使用道具 举报

lihannan 发表于 2016-4-20 13:31:29 | 显示全部楼层
所以楼主pass 了? 恭喜哇
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-4-25 09:28:17 | 显示全部楼层
请问求总path数怎么算呢?
就是第一问结果的size()吗?
感觉烙印自己定义什么是path。。。
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-4-28 07:40:19 | 显示全部楼层
感觉楼主没有说清啊。。。。
是要打印出所有的环路径嘛?
为什么还要1,4?????
回复 支持 反对

使用道具 举报

todayand 发表于 2016-4-28 10:19:01 | 显示全部楼层
jiebour 发表于 2016-4-28 07:40
.鐣欏璁哄潧-涓浜-涓夊垎鍦感觉楼主没有说清啊。。。。
是要打印出所有的环路径嘛?
为什么还要1,4?????

acyclic非环,按照test case的意思,就是一道简单的bfs/dfs, 打印出从start node开始,所有能到达的path
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 18:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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