📣 4th of July限时特惠: VIP通行证立减$68
楼主: 匿名
跳转到指定楼层
上一主题 下一主题
收起左侧

新鲜亚麻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?
回复

使用道具 举报

🔗
ivy9199 2020-2-11 08:55:13 | 只看该作者
全局:
匿名者 发表于 2020-2-10 12:03
三个结构:

一个HashMa ...

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

使用道具 举报

地里匿名用户
🔗
匿名用户-CYVZ9  2020-2-11 09:08:49
大熊不能飞 发表于 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)啊
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-CYVZ9  2020-2-11 09:13:57
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,貌似想让猜。。然后我分析半天跟他说这题没有唯一解。。
回复

使用道具 举报

🔗
lwill 2020-2-12 23:57:26 | 只看该作者
全局:
本帖最后由 lwill 于 2020-2-13 00:08 编辑
匿名者 发表于 2020-2-11 09:13
Double linked list的node是知道它的前后节点的。而通过hashmap我们是知道一个key存在哪个node里的。当in ...
Node 里面存一个 count 和一个 set<Key>,相当于每个count对应一个bucket of keys

回复

使用道具 举报

🔗
tanj 2020-4-22 14:03:51 | 只看该作者
全局:
楼主能说说怎么设计prime video嘛
回复

使用道具 举报

🔗
tanj 2020-5-10 16:50:23 | 只看该作者
全局:
匿名者 发表于 2020-2-10 11:59
哈哈哈哈,这样的吗?为啥啊?
我不管哪个组了,能先上岸再说啊

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表