一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 1844|回复: 21
收起左侧

狗昂赛

[复制链接] |试试Instant~ |关注本帖
yesterdaysea 发表于 2017-11-9 09:54:58 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 硕士 全职@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. 乐扣散久久。

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

评分

5

查看全部评分

 楼主| yesterdaysea 发表于 2017-11-10 03:49:59 | 显示全部楼层
reliveinfire 发表于 2017-11-9 13:45. 1point 3acres 璁哄潧
想讨论一下 看看想法对不对. 鍥磋鎴戜滑@1point 3 acres

第一题, 请问bfs 可以呢?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一题我觉得你的方法应该可行。我觉得更好的方法是,用公交线建图,先找出每条公交线和其他哪些公交线相交,然后把所有能到达起点车站的公交线加到queue里进行bfs。优化是可以从起点和终点双边bfs。
第四题你的方法应该也可行吧。我是用sliding window加上trie做的。先找出list中最长单词的长度k。然后维护一个长度为k的window。建trie的时候注意是反向建,每个单词从最后一个字母开始往前建。同时查的时候也是从window的最右边往前查。
回复 支持 2 反对 0

使用道具 举报

edyyy 发表于 2017-11-9 09:58:09 | 显示全部楼层
谢谢楼主分享。
感叹:狗家题真是各种虐待人啊. 1point 3acres 璁哄潧
回复 支持 反对

使用道具 举报

reliveinfire 发表于 2017-11-9 12:00:10 | 显示全部楼层
请问第5题, . Waral 鍗氬鏈夋洿澶氭枃绔,
dfs/bfs 要怎么分析呢?跟选择呢?
回复 支持 反对

使用道具 举报

reliveinfire 发表于 2017-11-9 13:45:09 | 显示全部楼层
想讨论一下 看看想法对不对

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

请问这想法是否可行 ?. from: 1point3acres.com/bbs
还是lz怎么作的呢?

第4题

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

请问这想法是否可行?
还是lz是怎么作的呢?
回复 支持 反对

使用道具 举报

 楼主| yesterdaysea 发表于 2017-11-10 03:51:20 | 显示全部楼层
reliveinfire 发表于 2017-11-9 12:00
请问第5题, .鐣欏璁哄潧-涓浜-涓夊垎鍦
dfs/bfs 要怎么分析呢?跟选择呢?

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

使用道具 举报

wqq0717 发表于 2017-11-10 11:18:54 | 显示全部楼层
请问第3题要怎么做?
回复 支持 反对

使用道具 举报

 楼主| yesterdaysea 发表于 2017-11-11 08:34:18 | 显示全部楼层
wqq0717 发表于 2017-11-10 11:18
请问第3题要怎么做?
. visit 1point3acres.com for more.
priority queue 加hashmap。queue按start sort。map记录process有没有finish。这题不难。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

get_bits 发表于 2017-12-7 17:23:17 来自手机 | 显示全部楼层
马克一下 谢谢楼主!
回复 支持 反对

使用道具 举报

hychin 发表于 2017-12-8 00:49:35 | 显示全部楼层
mark 这些题出的都挺好
回复 支持 反对

使用道具 举报

Lynn_Wang 发表于 2017-12-8 01:10:03 | 显示全部楼层
Lynn_Wang 发表于 2017-12-7 12:53. 鍥磋鎴戜滑@1point 3 acres
感谢楼主分享。请教一下,第四题建Trie的时候反向建&从window的最右边开始查是为了提高效率吗?用常规建T ...

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

使用道具 举报

cocaptainco 发表于 2017-12-8 04:09:01 | 显示全部楼层
问一下第二题怎么做?
回复 支持 反对

使用道具 举报

jiebour 发表于 2017-12-8 04:13:47 | 显示全部楼层
yesterdaysea 发表于 2017-11-10 03:49
第一题我觉得你的方法应该可行。我觉得更好的方法是,用公交线建图,先找出每条公交线和其他哪些公交线相 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
所以并不是什么动态的char stream,就是一个string 或者说一个char数组  对吧?不会随着时间的改变而新进char对吧?
回复 支持 反对

使用道具 举报

dongsancu 发表于 2017-12-8 06:17:26 | 显示全部楼层
yesterdaysea 发表于 2017-11-11 08:34
priority queue 加hashmap。queue按start sort。map记录process有没有finish。这题不难。

是不是只要priority queue就行了,每次有process结束就从队首一直remove已经结束的?

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

使用道具 举报

YUANSHAO 发表于 2017-12-27 11:39:19 | 显示全部楼层
第三题能举个例子吗 谢谢
回复 支持 反对

使用道具 举报

jy_121 发表于 2017-12-28 09:40:33 | 显示全部楼层
Lynn_Wang 发表于 2017-12-8 01:10
请忽略这个问题 ,囧, 我想明白了...

求问为什么,谢谢。
回复 支持 反对

使用道具 举报

Augustus 发表于 2017-12-30 07:24:24 | 显示全部楼层
jy_121 发表于 2017-12-28 09:40
求问为什么,谢谢。

你怎么老抢在我前头
回复 支持 反对

使用道具 举报

Juliang 发表于 2017-12-30 07:31:19 | 显示全部楼层
yesterdaysea 发表于 2017-11-11 08:34. 1point 3acres 璁哄潧
priority queue 加hashmap。queue按start sort。map记录process有没有finish。这题不难。

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

使用道具 举报

Lynn_Wang 发表于 2018-1-6 05:22:44 | 显示全部楼层
jy_121 发表于 2017-12-28 09:40. visit 1point3acres.com for more.
求问为什么,谢谢。

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-1-20 13:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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