新鲜亚麻Prime Video SDE II昂赛，时间线，以及大概率跪，经，求米

yangmyfly 发表于 2020/02/08 09:41:25
我感觉他们现在流行故意不把题目条件全部告送你，容易想复杂想歪

太同意了，有时候出的原题就容易忘记确认某些细节。或者以为自己明白了。上次onsite就很大感觉，他们的问题太模糊了。

pansinyoung 发表于 2020-2-11 03:45
改变后你怎么得到Max Min呢？搜索Hashmap的所有值来获得Max Min吗？这样的搜索操作不是O(1)，是O(n)啊。

你确定hashmap 搜索是on?

匿名者 发表于 2020-2-10 12:03
三个结构：

一个HashMa ...

楼主能具体说说怎么 O(1)保持double link sorted 的吗

大熊不能飞 发表于 2020-2-10 18:44
你确定hashmap 搜索是on?

Map.get是O（1）。我说的不是Hashmap.get，而是找更新之后的min max。

如果你用hashmap存key -> count: 假设现在map里有{"key1" -> 1, "key2" -> 1, "key3" -> 1}，当前的min，max都是1；当我们调用increment("key1")后，max可以直接得出来是2，但是min呢？你是不是要在map里找最小的value，或者找比2小的值，是不是需要遍历一个这个map里的所有value，是不是On呢？


如果你用hashmap存count -> set of keys，不说别的，getCount(String key) 就不是O（1）。

所以只用一个hashmap做不到让所有method都O（1）啊

ivy9199 发表于 2020-2-10 18:55
楼主能具体说说怎么 O(1)保持double link sorted 的吗

Double linked list的node是知道它的前后节点的。而通过hashmap我们是知道一个key存在哪个node里的。当increment/decrement的时候，我们只需要把key从当前节点里remove，add到当前节点的 后面/前面的节点里去，这个操作是O（1）。同时，我们需要看看需不需要更新max/min，同样是O（1）。这个操作里面要注意的点是，在移动key的时候要看看前面/后面需不需要insert节点。

有用的话求个米

清蓬村民 发表于 2020/02/11 06:27:33
太同意了，有时候出的原题就容易忘记确认某些细节。或者以为自己明白了。上次onsite就很大感觉，他们的问题太模糊了。

哈哈，有时候感觉把题assumption猜对比做题难，有道题没见过，他一开始没跟说stream是sorted，貌似想让猜。。然后我分析半天跟他说这题没有唯一解。。

匿名者 发表于 2020-2-11 09:13
Double linked list的node是知道它的前后节点的。而通过hashmap我们是知道一个key存在哪个node里的。当in ...

Node 里面存一个 count 和一个 set<Key>，相当于每个count对应一个bucket of keys

楼主能说说怎么设计prime video嘛

匿名者 发表于 2020-2-10 11:59
哈哈哈哈，这样的吗？为啥啊？
我不管哪个组了，能先上岸再说啊

楼主三个月后感觉PV咋样呀