狗家虚拟现场表演

直接给的Onsite，一共五轮，四轮coding，一轮BQ.
第一轮：面试官有事，reschdule.
第二轮：国人大哥，满脸微笑。上来先跟我聊聊我之前的项目，后来面试官听完觉得我的项目哪里哪里做的不对啊，我花了不少时间解释，这里大概花去15min. 然后开始做题。这段把我整慌了，一是没期待问项目，二是他总否定我的项目内容，比较难受。
              给一个Oncall表 {张三：1 - 5， 李四： 5 - 7， 王五： 2 - 10} 这个格式是 “谁：什么时候”
              要求返回一个格式为“时间段：谁（们）”的表。比如上面的例子的return就是：
              1 - 2 张三
              2 - 5 张三 王五
              5 - 7 李四 王五
              7 - 10 王五
              return type没有规定，总之这个return能找某时间段有谁在Oncall

第三轮： 国人大哥。人很nice. 一直鼓励我，引导我。给两个string, 叫他们old和new吧，比较他们，已知old是通过改变了一个substring变成new的，分析出old是怎么变成new的。
              return三个东西，变化的种类（增加，减少，替换），

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

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

也没啥，让做题就做呗。
               题目内容：让我写一段代码来返回一个迷宫，没了。其他基本啥也没给，不是他不给信息，而是本身就不给什么限制，自由发挥。和面试官讨论能获得好的方向，比如，Input是什么, 迷宫要怎么表示，这个迷宫有几个解等等。
               input: 迷宫的宽，迷宫的高，起点，终点
               output: 一个设计好了的迷宫



总体来说题目都不难，就是面试的过程遇到不少意料之外的事情搞心态。
还有一轮，加油。

希望在准备面试的你也加油！


补充内容 (2020-9-16 02:45):
刚面完最后一轮， 题目我会放在回复里面，大家自己找找

为啥你面试都是国人！ 我为啥没这么好的运气。。。

最后一轮：
不断有<Key, Value>pairs进来的input stream. Key: String, Value: positive integer. 要求自己定义数据结构，写两个函数，第一个，addNewPair, 第二个：return the top K pairs.

怎么算TOP呢，对于某个key，算出他所有input  pair里面带这个key 的value的和（有点拗口，不过很好理解，看例子）

example:
K = 2
input addpair顺序：<a, 10> <b, 20> <c, 15> <a, 10>

每次addPair之后call findTopK() 的结果如下：
<a,10>
<a, 10> <b, 20>
<c, 15> <b, 20>
<a, 20> <b, 20>

你可以想像成一堆人来银行存款，给定一个K，不断return前K个存款最多的人。

lz遇到的好几个都是面经题， 运气不错
第二轮是：https://leetcode.com/discuss/int ... tervals-with-labels
第四轮是：https://www.1point3acres.com/bbs ... ngineer-617689.html 里面的第五轮
第五轮是个狗家的陈年老题 设计迷宫

第三轮我似乎也见过 找不到原帖了

第四轮的题感觉可以用incremental stack。

请问楼主第二轮有什么快速一点的方法求所有cover到的interval吗？

楼主，祝你最后一轮顺利通关！
想问下第二题需要输出这种5-5=[李四, 张三, 王五]吗

求问第三轮思路，第四轮只想到了O(n^2)的解法，求lz赐教

补充内容 (2020-9-14 08:59):
第四轮可以用单调栈找next smaller element吗？前后各扫一遍，将每个数的next smaller element的index存到两个array里，再和threshould比较？

谢谢LZ分享！请问下可以再提供第五题的细节吗？感觉很雾。。。迷宫的预期是什么 - 如果没啥预期return一个空白版也是个迷宫。。 /cry

感谢楼主！想问下第二轮，我能想到的是把non-overlap的intervals写出来，然后逐个检查各个人得startTime, endTime是不是落在这个区间里面……但有没有更快的方法呢？以及第三轮的问题，从old string到new string默认只用了一次变化种类操作吗？

BeTheBest 发表于 2020-9-14 09:15
感谢楼主！想问下第二轮，我能想到的是把non-overlap的intervals写出来，然后逐个检查各个人得startTime, e ...

第二题刚试了下扫描线+hashset(存从上个时间点到当前时间点所有oncall的人名)，能跑。如果N个区间，排序花O(2N*log2N), 扫一遍花O(2N)。不知道对不，求大家指点

xiaoxiao0801 发表于 2020-9-14 10:02
第二题刚试了下扫描线+hashset(存从上个时间点到当前时间点所有oncall的人名)，能跑。如果N个区间，排序 ...

我的想法：用一个buckets array, 每一个小时作为一个bucket，存oncall的人名的linkedlist or hashset,
loop oncall 表格来填buckets，
然后从头到尾loop buckets，顺便比较是否有相邻的buckets内容一样，O(n) time complexity