下个门新鲜出炉电面

新鲜电面面经，总共两轮技术电面
第一轮
1. 给两个时间intervals (startTIme, endTime), 找出他们overlap的duration
e.g.
interval1 = [1, 6]
interval2 = [5, 10]
那么duration就是 6 - 5 = 1
如果是[1, 5], [5, 10]算没有overlap
2. 一个面包店，给定一个busy time window interval e.g. [10, 15], 然后给出一些顾客进入面包店的时间intervals e.g. [1, 5], [8, 12], [10, 14]. 问在busy time window中有百分之多少的时间是有顾客的。对于给定的例子： 第一个用户[1, 5]，完全不在busy time window，第二个用户[8, 12]占到了 12 - 10 = 2. 第三个用户[10, 14] 占了14 - 10 = 4. 但是第三个用户和第二个用户在 [10, 12]是重叠的。题目不能考虑重叠，所以最终是 14 - 10 = 4是在time wind

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

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

ry，而是按照inclusive的数值。e.g. getRangeSum of [5, 10], 那么你要去在nums list里面找到所有的 num_i where 5 <= num_i <= 10, 然后求 sum of all num_i.

哇谢谢lz，想问一下lz两轮是一起面的吗还是分两次？

请问楼主有offer了吗

皮qq 发表于 2021-9-5 06:35
哇谢谢lz，想问一下lz两轮是一起面的吗还是分两次？

同一天面的

请问楼主第二题可以分享一下有什么特别解法吗

DuTrammm 发表于 2021-9-17 00:50
请问楼主第二题可以分享一下有什么特别解法吗

感觉是不是可以这样。
1. 先把num list sort一下
2. 算一个presum
3. 然后给给定的range(5, 10), 找到最左边5的index和最右边10的index, 用第二步的presum来弄一下presum[right+1] - presum[left] 就可以了

我觉得第二题的思路是先sort 然后建一个map存number到这个number的最左边index和最右边index的mapping，然后建map的过程中可以顺便求prefix sum。然后对于range（x，y）来说，直接用map找出x的最左index和y的最右边index，然后用prefix sum一减就行了，这样每次range（）都是O（1）的复杂度

小亩_ifzcfc4 发表于 2022-9-25 15:14
我觉得第二题的思路是先sort 然后建一个map存number到这个number的最左边index和最右边index的mapping，然 ...

我觉得这样做可以, 但是可能会被追问scale的问题. 空间复杂度和interval最大最小值成正比.如果日后想记录毫秒精度空间复杂度会很大.可以用prefixsum + binarysearch,不是按timestamp保存时间点,只用interval起始和结束做时间点就行. logn time n(num_interval) space

请问楼主是海投还是内推 谢谢

楼主有update吗