一亩三分地论坛

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

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

Twitter电面

[复制链接] |试试Instant~ |关注本帖
lqzgz 发表于 2015-10-10 05:22:06 | 显示全部楼层 |阅读模式

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

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

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

x
游客,本帖隐藏的内容需要积分高于 1 才可浏览,您当前积分为 0。 查看如何攒积分


祝大家offer多多


补充内容 (2015-10-10 06:16):. 1point3acres.com/bbs
面完才一小时,就听说Twitter要大规模雷人 sigh

评分

2

查看全部评分

liyanjia92 发表于 2015-10-23 08:05:01 | 显示全部楼层
请问第一题优化空间的技巧是什么呢?只记录边缘?第二题BFS的话也要维护一个空间存放所有边缘节点吧,会不会和你用的map差不多呢?谢谢啦
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-10-23 11:31:04 | 显示全部楼层
liyanjia92 发表于 2015-10-23 08:05
请问第一题优化空间的技巧是什么呢?只记录边缘?第二题BFS的话也要维护一个空间存放所有边缘节点吧,会不 ...

1. 就是用一个一维vector去记录结果 dp[0] = 0, dp += dp[i - 1]
2. 三姐当时的意思是,用BFS的话,实际有不少地方不会去访问,用二维数组比较浪费,所以就用map了,你说的没错,用map的话,最差的情况空间复杂度也是n * m,当时三姐觉得make sense就不继续问了
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-10-23 11:32:53 | 显示全部楼层
liyanjia92 发表于 2015-10-23 08:05
请问第一题优化空间的技巧是什么呢?只记录边缘?第二题BFS的话也要维护一个空间存放所有边缘节点吧,会不 ...

顺便问下你Hulu面的是哪几个组?我下个月去面,打算面ads跟content publishing
回复 支持 反对

使用道具 举报

liyanjia92 发表于 2015-10-23 11:44:58 | 显示全部楼层
lqzgz 发表于 2015-10-23 11:32
顺便问下你Hulu面的是哪几个组?我下个月去面,打算面ads跟content publishing
.鐣欏璁哄潧-涓浜-涓夊垎鍦
ads组就是那第一个美国人,content是那个印度人,还面了core,是中国人,mobile是香港人
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-10-23 11:59:54 | 显示全部楼层
liyanjia92 发表于 2015-10-23 11:44. Waral 鍗氬鏈夋洿澶氭枃绔,
ads组就是那第一个美国人,content是那个印度人,还面了core,是中国人,mobile是香港人

多谢,感觉他家B格真是高,下次去要被虐TwT
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-10-31 03:36:45 | 显示全部楼层
lqzgz 发表于 2015-10-23 11:31
1. 就是用一个一维vector去记录结果 dp[0] = 0, dp += dp
2. 三姐当时的意思是,用BFS的话,实际有不少 ...

第一题不是要比较从上面过来和从左边过来哪个更小吗? 如果只是一维,如何比较?
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-11-3 23:38:02 | 显示全部楼层
hyliu0000 发表于 2015-10-31 03:36
.1point3acres缃第一题不是要比较从上面过来和从左边过来哪个更小吗? 如果只是一维,如何比较?

leetcode unique paths的discussion里有讲
回复 支持 反对

使用道具 举报

wk93210 发表于 2015-11-9 10:27:09 | 显示全部楼层
谢谢楼主分享,先来看看隐藏内容
回复 支持 反对

使用道具 举报

returning 发表于 2015-12-7 07:29:03 | 显示全部楼层
楼主啊,第一题,什么叫写了两个八阿哥?. more info on 1point3acres.com

补充内容 (2015-12-7 07:30):
晕,一个回车就g出去了。我想问的是第二题,是求从起点到终点最短路径长度,而不是unique path number,对吧。这个题难道不是从两个点开始一起做bfs?难点是需要有一个map维护已经走过的点。
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-12-7 08:49:34 | 显示全部楼层
returning 发表于 2015-12-7 07:29. visit 1point3acres.com for more.
楼主啊,第一题,什么叫写了两个八阿哥?

补充内容 (2015-12-7 07:30):

八阿哥=bug
求最短路径用最简单的BFS不就行了么,你说的那个是双向BFS吧,除非你搞过ACM,不然大部分人现场是写不出来bug free的双向BFS
回复 支持 反对

使用道具 举报

returning 发表于 2015-12-7 10:03:02 | 显示全部楼层
lqzgz 发表于 2015-12-7 08:49
八阿哥=bug
求最短路径用最简单的BFS不就行了么,你说的那个是双向BFS吧,除非你搞过ACM,不然大部分人 ...

对,我就是说双向BFS,其实双向BFS还好了,leetcode上有两道题都是可以用双向bfs的,讨论区里有答案。这题关键是,双向bfs也需要多余的内存开销,感觉不知道怎么继续优化space。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 10:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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