狗昂赛

MTV onsite.
1. 有n路公交线，已知每路公交的经停车站，公交是bi-direction，问从车站A到车站B最少需要几次换乘。
2. 设计一个class存储股票价格。支持update某个timestamp的价格。quer

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第三轮followup是多线程下是否thread safe。
第四轮先自我介绍聊了简历。
第五轮讨论用dfs bfs的优缺点，选择的原因。
希望对大家有帮助。

reliveinfire 发表于 2017-11-9 13:45
想讨论一下 看看想法对不对

第一题, 请问bfs 可以呢?

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

Lynn_Wang 发表于 2018-1-6 05:22
我是这样理解的：因为输入是string steam, 当用户每输入一个char, 从window的右边界(也就是stream的最后 ...

你的想法思路应该很正确。补充一点应该是不需要知道stream.length(), 如果初始化给定的string stream不是空的，那么应该先从stream的最右边一个字符为起点搜索反向Trie，然后再从倒数第二个字符，倒数第三个依次内推。然后每当有新的字符加进stream就以该新加进的字符为起点开始搜索反向Trie.

谢谢楼主分享。
感叹：狗家题真是各种虐待人啊

请问第5题,
dfs/bfs 要怎么分析呢?跟选择呢?

想讨论一下 看看想法对不对

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

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

第4题

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

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

reliveinfire 发表于 2017-11-9 12:00
请问第5题,
dfs/bfs 要怎么分析呢?跟选择呢?

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

请问第3题要怎么做？

wqq0717 发表于 2017-11-10 11:18
请问第3题要怎么做？

priority queue 加hashmap。queue按start sort。map记录process有没有finish。这题不难。

yesterdaysea 发表于 2017-11-10 03:49
第一题我觉得你的方法应该可行。我觉得更好的方法是，用公交线建图，先找出每条公交线和其他哪些公交线相 ...

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

马克一下 谢谢楼主！