fb E4 onsite 过经

匿名用户-LXWS1 *2021-7-18 04:05:51* · 2021-7-18 04:05:51

patriotJ 发表于 2021-7-17 15:59
这个好像是🈚️罢以？

看了下还真的是这道不是fb tag题准备的时候没见过这道题 O(n)的解法还现场想了挺久的最后用栈写出来了

timzyt

匿名者发表于 2021-7-17 13:02
merge 后 quick select

感谢楼主分享。我觉得merge以后仍然可以用max-heap来做吧！
当然QS的平均复杂度要低一点！

已加米

匿名用户-LXWS1 *2021-7-18 05:13:02* · 2021-7-18 05:13:02

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

parchment

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

匿名用户-LXWS1 *2021-7-18 06:04:44* · 2021-7-18 06:04:44

parchment 发表于 2021-7-17 17:53
Lz tql请问两个follow up都写了吗写个k-merge + quick sort还挺费时间的

没有只要求写最开始的问题剩下一直在讨论不同解法的时间复杂度和空间复杂度上的tradeoff

timzyt

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

匿名用户-LXWS1 *2021-7-18 07:51:52* · 2021-7-18 07:51:52

timzyt 发表于 2021-7-17 18:21
楼主，关于这题：给一个array，中间有一部分array是unsorted的, 比如 [0, 1, 2, 6, 5, 4, 7, 8] 找出这个区 ...

楼上已经有人指出来了是原题
🈚️罢以

BrightFeather

>followup2: 如果所有array的值都在0-100 之间? 答用hashmap/counter 解决

这里能详细说一下嘛？谢谢

BrightFeather

BrightFeather 发表于 2021-7-18 15:33
>followup2: 如果所有array的值都在0-100 之间? 答用hashmap/counter 解决

这里能详细说一下嘛？谢谢

似乎记录下每个数字出现的个数就好了。然后按顺序找第k个。奈斯！

BrightFeather

这个system design题目之前没看到过诶。楼主觉得有什么重点和红线可以分享下吗？