Airbnb 2018年春季E6 package

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 3629|回复: 25
收起左侧

狗昂赛

[复制链接] |试试Instant~ |关注本帖
我的人缘0
yesterdaysea 发表于 2017-11-9 09:54:58 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  94% (72)
 
 
5% (4)  踩

2017(10-12月) 码农类General 硕士 全职@Google - 内推 - Onsite  | Other | 在职跳槽

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

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

x
MTV onsite.
1. 有n路公交线,已知每路公交的经停车站,公交是bi-direction,问从车站A到车站B最少需要几次换乘。
2. 设计一个class存储股票价格。支持update某个timestamp的价格。query目前价格以及历史最高价格。
3. 设计一个class log process执行顺序。每个process都会start和finish,当一个process finish的时候才可以写入log,但是log必须按照时间顺序排好,先start的要写在前面。
4. 给一个word list,有一个char stream, 如果stream中出现list中的word要return true。
5. 乐扣散久久。


补充内容 (2017-11-9 10:08):
第二轮先问了hashmap如何实现。写完后讨论每个操作的复杂度,如何优化。
第三轮followup是多线程下是否thread safe。
第四轮先自我介绍聊了简历。
第五轮讨论用dfs bfs的优缺点,选择的原因。
希望对大家有帮助。

评分

参与人数 5大米 +18 收起 理由
feng + 3 很有用的信息!
xiayank + 5 给你点个赞!
quingogo + 2 给你点个赞!
丑猪宝 + 5 给你点个赞!
reliveinfire + 3 给你点个赞!

查看全部评分


上一篇:求问drawbridge新OA
下一篇:狗狗匹兹堡跪经
我的人缘0
 楼主| yesterdaysea 发表于 2017-11-10 03:49:59 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  94% (72)
 
 
5% (4)  踩
reliveinfire 发表于 2017-11-9 13:45
想讨论一下 看看想法对不对

第一题, 请问bfs 可以呢?

第一题我觉得你的方法应该可行。我觉得更好的方法是,用公交线建图,先找出每条公交线和其他哪些公交线相交,然后把所有能到达起点车站的公交线加到queue里进行bfs。优化是可以从起点和终点双边bfs。. from: 1point3acres
第四题你的方法应该也可行吧。我是用sliding window加上trie做的。先找出list中最长单词的长度k。然后维护一个长度为k的window。建trie的时候注意是反向建,每个单词从最后一个字母开始往前建。同时查的时候也是从window的最右边往前查。
回复

使用道具 举报

我的人缘0
edyyy 发表于 2017-11-9 09:58:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (79)
 
 
15% (15)  踩
谢谢楼主分享。
感叹:狗家题真是各种虐待人啊
回复

使用道具 举报

我的人缘0
reliveinfire 发表于 2017-11-9 12:00:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
请问第5题, . 牛人云集,一亩三分地
dfs/bfs 要怎么分析呢?跟选择呢?
回复

使用道具 举报

我的人缘0
reliveinfire 发表于 2017-11-9 13:45:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
想讨论一下 看看想法对不对

第一题, 请问bfs 可以呢?
建一个map, 车站 map 每路公交
每次将能到达的车站, 看看是否有可新搭公交, 跟检查是否能到

请问这想法是否可行 ?
还是lz怎么作的呢?

第4题

建trie, 每次new char 进来, 就新增一个TreeNode* idx = root
跟移动之前保存的idx

请问这想法是否可行?
-google 1point3acres还是lz是怎么作的呢?
回复

使用道具 举报

我的人缘0
 楼主| yesterdaysea 发表于 2017-11-10 03:51:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (72)
 
 
5% (4)  踩
reliveinfire 发表于 2017-11-9 12:00. 围观我们@1point 3 acres
请问第5题,
dfs/bfs 要怎么分析呢?跟选择呢?

这个我答的并不好,答了很多,但感觉都不是面试官想要的答案。我最后是用dfs写的。
回复

使用道具 举报

我的人缘0
wqq0717 发表于 2017-11-10 11:18:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
请问第3题要怎么做?
回复

使用道具 举报

我的人缘0
 楼主| yesterdaysea 发表于 2017-11-11 08:34:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (72)
 
 
5% (4)  踩
wqq0717 发表于 2017-11-10 11:18
请问第3题要怎么做?

priority queue 加hashmap。queue按start sort。map记录process有没有finish。这题不难。
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
Lynn_Wang 发表于 2017-12-7 12:53:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
yesterdaysea 发表于 2017-11-10 03:49
第一题我觉得你的方法应该可行。我觉得更好的方法是,用公交线建图,先找出每条公交线和其他哪些公交线相 ...

感谢楼主分享。请教一下,第四题建Trie的时候反向建&从window的最右边开始查是为了提高效率吗?用常规建Trie insert & search 的方式可行吗?
回复

使用道具 举报

我的人缘0
get_bits 发表于 2017-12-7 17:23:17 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  40% (2)
 
 
60% (3)  踩
马克一下 谢谢楼主!
回复

使用道具 举报

我的人缘0
hychin 发表于 2017-12-8 00:49:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (236)
 
 
18% (53)  踩
mark 这些题出的都挺好
回复

使用道具 举报

我的人缘0
Lynn_Wang 发表于 2017-12-8 01:10:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
Lynn_Wang 发表于 2017-12-7 12:53
感谢楼主分享。请教一下,第四题建Trie的时候反向建&从window的最右边开始查是为了提高效率吗?用常规建T ...

请忽略这个问题 ,囧, 我想明白了...
回复

使用道具 举报

我的人缘0
cocaptainco 发表于 2017-12-8 04:09:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (48)
 
 
12% (7)  踩
问一下第二题怎么做?
回复

使用道具 举报

我的人缘0
jiebour 发表于 2017-12-8 04:13:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  70% (22)
 
 
29% (9)  踩
yesterdaysea 发表于 2017-11-10 03:49
第一题我觉得你的方法应该可行。我觉得更好的方法是,用公交线建图,先找出每条公交线和其他哪些公交线相 ...

所以并不是什么动态的char stream,就是一个string 或者说一个char数组  对吧?不会随着时间的改变而新进char对吧?
回复

使用道具 举报

我的人缘0
dongsancu 发表于 2017-12-8 06:17:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (6)
 
 
14% (1)  踩
yesterdaysea 发表于 2017-11-11 08:34
priority queue 加hashmap。queue按start sort。map记录process有没有finish。这题不难。
. 围观我们@1point 3 acres
是不是只要priority queue就行了,每次有process结束就从队首一直remove已经结束的?

补充内容 (2017-12-8 06:19):
哦,得要hashmap,得知道是哪个process结束了
回复

使用道具 举报

我的人缘0
YUANSHAO 发表于 2017-12-27 11:39:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (41)
 
 
2% (1)  踩
第三题能举个例子吗 谢谢
回复

使用道具 举报

我的人缘0
jy_121 发表于 2017-12-28 09:40:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (120)
 
 
4% (5)  踩
Lynn_Wang 发表于 2017-12-8 01:10
请忽略这个问题 ,囧, 我想明白了...

求问为什么,谢谢。
回复

使用道具 举报

我的人缘0
Augustus 发表于 2017-12-30 07:24:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (294)
 
 
20% (76)  踩
jy_121 发表于 2017-12-28 09:40
求问为什么,谢谢。
.留学论坛-一亩-三分地
你怎么老抢在我前头
回复

使用道具 举报

我的人缘0
Juliang 发表于 2017-12-30 07:31:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
yesterdaysea 发表于 2017-11-11 08:34. from: 1point3acres
priority queue 加hashmap。queue按start sort。map记录process有没有finish。这题不难。

Priority queue 太慢了吧,O(logn) 啊。 用linked list可以做到 amortized O(1)
回复

使用道具 举报

我的人缘0
Lynn_Wang 发表于 2018-1-6 05:22:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
jy_121 发表于 2017-12-28 09:40
求问为什么,谢谢。

我是这样理解的:因为输入是string steam, 当用户每输入一个char, 从window的右边界(也就是stream的最后一个新输入的char)开始对比反向建的Trie, window的size是keyword的最大长度。如果是正向建Trie并从window的左边界对比的话,没法办得知stream.length(), 因为用户是持续输入的.... 不知道说明白了没有 囧
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-7-17 02:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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