狗家虚拟现场表演

楼主最后pass了么？

ja0b 发表于 2020-9-16 02:51
最后一轮：
不断有pairs进来的input stream. Key: String, Value: positive integer. 要求自己定义数据结 ...

谢谢楼主分享，如果K=1，pairs: <a,10> <b,10>就是有并列的情况，这个时候返回什么？<a,10> <b,10> 还是按字母排序返回<a,10>？

ja0b 发表于 2020-9-16 02:51
最后一轮：
不断有pairs进来的input stream. Key: String, Value: positive integer. 要求自己定义数据结 ...

请问应该怎么解呢？

我能想到的方法很笨，如下。还有什么高招吗？

用heap（或者list）保存最大的K个，同时用dictionary保存key value的pair，当add（key,value）来了分两种情况：
1. 更新的key小于heap的最小值，更新dictionary即可
2. 更新的key大于等于heap的最小值，heap需要重新排序， heapify O(K)
如果K<<N，这样的复杂度似乎不高

第二轮类似skyline.
存(start, end, 人), 然后按时间扫描维护一个当前值班的人的set。start就加进来，end就减出去，同时计算interval，和对应的人集

第三轮貌似就从左右分别扫描，遇到不同的字符就可以停止。
是不是我想简单了？

第五轮迷宫，就是在n*n matrix里dfs一条路径吧。每次选取下一步的时候，用随机数决定方向。

第四轮可以用一个queue存sliding window minimum，不知道这个思路对不对

菜某样 发表于 2020-10-17 07:34
我觉得最后一题可以maintain一个counter map，一个top K sorted list，以及top K entity 和他们当前所在sor ...

按照这个想法，对于top K list的维护不一定需要binary search insert 吧？只要复杂度为nlogn的排序方法应该都可以？ 不知道是不是我对层主的意思没理解对
更新： 不好意思我上面的想法是错误的，支持层主

followjason 发表于 2020-9-14 11:18
我的想法：用一个buckets array, 每一个小时 作为一个bucket，存oncall的人名的linkedlist or hashset,
...

我也是这么做的，但是这个办法感觉复杂度不止O(n)
假设整个起始时间为s，结束时间为e，输入一共有N个人，这个办法的复杂度应该是O(n*(s-e))

感谢！很有用