狗家虚拟现场表演

ZionHuang 发表于 2020-9-15 09:44
第三轮 交换new & old 因为只能修改一次
如果len(new) == len(old) 那么只可能 替换某个段落
如果len(new ...

len(old) != len(new) 也可能是替换，比如：
'aaabbcc" -> "aaa123123"

这里就是把"bbcc" 替换成了“123123”

最后一轮：
不断有<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第二轮的老哥主要是觉得你project那方面做得不对呢，是主要针对设计或者用的tech stack吗，还是觉得管理或者process方面不合理呢？多谢分享！

tm1234 发表于 2020-9-16 03:39
请问lz第二轮的老哥主要是觉得你project那方面做得不对呢，是主要针对设计或者用的tech stack吗，还是觉得 ...

应该说是针对设计吧。我说为了实现功能，我用了几个thread作concurrency. 然后说完他说我这个并不是concurrency啊，我就给他解释了一下为什么是，他觉得还是不是。

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

最后一题我的想法是创建一个双向 linkedlist, 并用 hash set 去记录每个用户的 node, 最好的情况是 binary search insert 到 list 里面, 所以是 insert o(logn)  top k 是 o(k)

dlwlrma 发表于 2020-9-14 07:53
求问第三轮思路，第四轮只想到了O(n^2)的解法，求lz赐教

补充内容 (2020-9-14 08:59):

有点没懂怎么用单调栈？如果对于每个数都找前后比他大的不是直接比较就好了？用单调栈可以one pass直接过吗？不用每个点都前后比较一遍？

已跪。coding不过关

请问一下第三题是什么思路？

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

请问lz findTopK的return需要maintain 存款顺序吗?
如果<a, 10> <b, 20> return的结果一定得是<a, 10> <b, 20>还是也可以 <b, 20><a, 10>

我觉得最后一题可以maintain一个counter map，一个top K sorted list，以及top K entity 和他们当前所在sorted list位置的map。

当你获得一个新数据的时候，存在四种情况：1. 更新的counter不在topK，小于topK里最小的值，只需要更新counter，是o(1); 2.更新的counter不在topK，但是现在比topK的最小大，去掉topK的最小值然后binary search insert, 是log(K); 3. 更新的counter在topK内并且没有改变topK排位，是o(1); 4. 更新的counter在topK内并且改变了topK排位，要对它重新binary search insert,是log(K)。

返回的恒定o(1).