楼主: fangwei007
跳转到指定楼层
上一主题 下一主题
收起左侧

Facebook 脸书 莫名其妙跪经

🔗
ydzhang 2018-11-2 06:05:11 | 只看该作者
全局:
第一题 空间复杂度就是K啊,你只能每次放k个数进去去top那个然后再取第二个。没有比这个更优化做法目前。是不是K很大?如果是,你理解错了,如果K很大是类似系统设计的题吧?
回复

使用道具 举报

🔗
sshic 2018-11-2 07:03:55 来自APP | 只看该作者
全局:
fangwei007 发表于 2018/11/02 01:39:33


这两个月运气差到爆炸, 开了三年的车, lease到期的前一个月被淹了, 引擎全换, 花了1.5W, 艾玛, 所有事情全在这俩月

摸摸 来年再战 运气这东西都是一阵一阵的
回复

使用道具 举报

🔗
BeStrong2017 2018-11-2 08:39:48 | 只看该作者
全局:
pat pat, recruiter有说是挂在debrief还是hc阶段了吗?
回复

使用道具 举报

全局:
https://leetcode.com/problems/merge-k-sorted-lists/solution/
solution 5,其实就是merge sort,时间nlogk,空间constant
供参考
回复

使用道具 举报

🔗
guid-uuid 2018-11-2 12:18:01 | 只看该作者
全局:
groundzyy1 发表于 2018-11-2 03:51
记不太清了,也没仔细看全文,之前面亚麻也是merge这个,好像外排序的方式在时间复杂度上更好。

我觉得不是时间复杂度更好,是可以并行执行,最后变成了多线程(甚至是分布式)和单线程的区别把。

补充内容 (2018-11-2 12:21):
空间复杂度确实是merge sort比priority queue要好 尤其是当k很大的时候
回复

使用道具 举报

🔗
 楼主| fangwei007 2018-11-2 22:11:34 | 只看该作者
全局:
ydzhang 发表于 2018-11-2 06:05
第一题 空间复杂度就是K啊,你只能每次放k个数进去去top那个然后再取第二个。没有比这个更优化做法目前。是 ...

heap的size就是K啊, 我们一直再算时间复杂度; 如果两两merge, 空间复杂度可不止K. 原题问的也是每一行的n可能很大, 这是coding轮, 跟系统设计没关系.
回复

使用道具 举报

🔗
 楼主| fangwei007 2018-11-2 22:12:32 | 只看该作者
全局:
张个灯结彩 发表于 2018-11-2 11:31
https://leetcode.com/problems/merge-k-sorted-lists/solution/
solution 5,其实就是merge sort,时间nl ...

请看清楚我的题目, 是sorted arrays不是lists, 不是lists, 不是lists!!!!
回复

使用道具 举报

🔗
zhang835 2018-11-2 22:28:37 | 只看该作者
全局:
和楼主情况类似 昂赛之后等offer 结果过了10天之后被拒 说very tough decision
回复

使用道具 举报

🔗
ydzhang 2018-11-3 03:37:19 | 只看该作者
全局:
fangwei007 发表于 2018-11-2 22:11
heap的size就是K啊, 我们一直再算时间复杂度; 如果两两merge, 空间复杂度可不止K. 原题问的也是每一行的n ...

I am confused.

time complexity is you have to process every elements, and each will go into the heap
so, n*log(k)

space complexity is k (k elements in the heap at a time)
回复

使用道具 举报

🔗
 楼主| fangwei007 2018-11-3 04:41:29 | 只看该作者
全局:
ydzhang 发表于 2018-11-3 03:37
I am confused.

time complexity is you have to process every elements, and each will go into the ...

没错的, 本来就这样, 前面有个人算错了复杂度, heap的解法时间复杂度 nklogk, 空间复杂度k. 这里的n是每一行的元素个数, 跟你说的其实是一样的, 不用confused, 你是对的.

之前有个人胡说了个说log(nk), 还装的跟自己很对似的
回复

使用道具 举报

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

本版积分规则

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