一亩三分地论坛

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

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

Airbnb 新鲜skype

[复制链接] |试试Instant~ |关注本帖
Jasonyuan 发表于 2016-11-22 07:59:31 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 实习@Airbnb - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
第一轮,merge intervals,一个白人小哥面的,第二轮是找最少的点遍历整个graph,之前地里有人发过,面试官是个国人妹子。

求过求过。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

八月 发表于 2016-11-22 08:05:55 | 显示全部楼层
都是面经题,楼主应该没问题了
回复 支持 反对

使用道具 举报

 楼主| Jasonyuan 发表于 2016-11-22 08:09:06 | 显示全部楼层
八月 发表于 2016-11-22 08:05
都是面经题,楼主应该没问题了

给dalao递茶 哈哈哈哈
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-22 08:44:10 | 显示全部楼层
找最少的点遍历整个graph 是哪个经典算法啊?
回复 支持 反对

使用道具 举报

 楼主| Jasonyuan 发表于 2016-11-22 09:32:30 | 显示全部楼层
wtcupup 发表于 2016-11-22 08:44
找最少的点遍历整个graph 是哪个经典算法啊?

我是对每个node进行dfs做的,之前地里面那个贴子里有讨论这个。
回复 支持 反对

使用道具 举报

some3411 发表于 2016-11-22 11:37:09 | 显示全部楼层
Jasonyuan 发表于 2016-11-22 09:32
我是对每个node进行dfs做的,之前地里面那个贴子里有讨论这个。
. more info on 1point3acres.com
楼主能具体说下吗?不需要先把strongly connected component找出来吗
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-11-22 11:54:03 | 显示全部楼层
Jasonyuan 发表于 2016-11-22 09:32
我是对每个node进行dfs做的,之前地里面那个贴子里有讨论这个。

能再说下或给个链接吗?谢谢!
回复 支持 反对

使用道具 举报

han4011 发表于 2016-11-22 13:48:09 | 显示全部楼层
求个链接吧 第二个题 求求求!!
回复 支持 反对

使用道具 举报

peterharrison 发表于 2016-11-22 14:33:27 | 显示全部楼层
求问楼主是海投还是内推?大概投多久有回复?。。。
回复 支持 反对

使用道具 举报

 楼主| Jasonyuan 发表于 2016-11-23 23:47:55 | 显示全部楼层
peterharrison 发表于 2016-11-22 14:33. 1point3acres.com/bbs
求问楼主是海投还是内推?大概投多久有回复?。。。
. 鍥磋鎴戜滑@1point 3 acres
内推,2周
回复 支持 反对

使用道具 举报

 楼主| Jasonyuan 发表于 2016-11-23 23:48:27 | 显示全部楼层
0  1  2  3  4  5  6  7  8  9
0[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
1[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
2[0, 0, 0 ,0, 0, 0, 0, 0, 0, 1],
3[0, 0, 0, 1, 0, 1, 0, 1, 0, 0], . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
4[0, 0, 0, 0, 0, 0 ,0, 0, 1, 0], . more info on 1point3acres.com
5[0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
6[0, 0, 0, 0, 0, 0, 1, 0, 0 ,0],
7[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
8[0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
9[0, 0, 0, 1, 0, 0, 1, 0, 0, 0]]

这是当时的一个test case,找最少的点遍历所有点,结果是0,1,2.
回复 支持 反对

使用道具 举报

goodluck888 发表于 2016-11-24 01:48:31 | 显示全部楼层
请问第二题的做法是要先找strongly connected component吗?
如果有环,dfs怎么做呢?谢谢楼主!!
回复 支持 反对

使用道具 举报

 楼主| Jasonyuan 发表于 2016-11-24 05:14:38 | 显示全部楼层
goodluck888 发表于 2016-11-24 01:48
请问第二题的做法是要先找strongly connected component吗?
如果有环,dfs怎么做呢?谢谢楼主!!

我没找scc,用dfs遇到visited就return就好啦
回复 支持 反对

使用道具 举报

runningMajia 发表于 2016-11-24 07:11:40 | 显示全部楼层
Jasonyuan 发表于 2016-11-23 23:48
0  1  2  3  4  5  6  7  8  9
0[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
1[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

这个testcase的为什么是0,1,谢谢!2呢?楼主有原来题目的链接吗?xie'x
回复 支持 反对

使用道具 举报

 楼主| Jasonyuan 发表于 2016-11-24 12:48:07 | 显示全部楼层
runningMajia 发表于 2016-11-24 07:11
这个testcase的为什么是0,1,谢谢!2呢?楼主有原来题目的链接吗?xie'x

0,1,2呀。我找不到原来的链接啦,没有存
回复 支持 反对

使用道具 举报

期末求过 发表于 2016-11-25 04:22:54 | 显示全部楼层
楼主能不能把代码发一个,我看之前有个暴力的n次dfs的代码,求问你也是那样做的吗
回复 支持 反对

使用道具 举报

goodluck888 发表于 2016-11-27 01:14:16 | 显示全部楼层
Jasonyuan 发表于 2016-11-24 05:14. Waral 鍗氬鏈夋洿澶氭枃绔,
我没找scc,用dfs遇到visited就return就好啦

请问一下,如果是 1->2->3->1, 2->4这样的例子。答案是2。用dfs怎么找到2呢?谢谢楼主
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 22:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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