脸家电面

热乎乎的脸家电面：
一个白人大哥PM，不知道为什么是PM面我技术coding：
1. 蠡口 物流领 变形了一点，但是不难。我先把最基础的说了一遍，然后用标准的presum加hashmap的方式写了。问了时间和空间复杂度，所有可能的test cases
2.

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

rong>补充内容 (2020-2-24 14:09):
刚刚接到电话说过了！看来脸家也不是需要最优解还是看思考过程的

luyulzs 发表于 2020-2-25 09:53
应该不会，我刚刚通知过了应该线性扫描是可以的。为了造福后人可以让他们在面试提一下线段树的方法作为imp ...

我又想了一下，这是个离线问题，也就是说只需要直方图最后的状态，所以也可以这样做：

维护一个长度2M+2的数组，对每一个区间先取和[-M,M]的交集，归一化，然后做如下更新

[1 3] & [-5 5]  + 5 => [6, 8]     [0 0 0 0 0 -1 0 0 1 0 0    0]
                                               0 1 2 3 5  6 7 8 9 10 11 12

[4 5] & [-5 5]  + 5 =>[10, 11]    [0 0 0 0 0 -1 0 0 1 -1   0   1]
                                                0 1 2 3  5  6 7 8 9 10 11 12

[-5 2] & [-5 5]  + 5 =>[0, 7]     [-1 0 0 0 0 -1 0 1 1 -1   0   1]
                                                0 1 2 3  5  6 7 8 9 10 11 12

最后从左到右做后缀和得到最后的直方图
[0 1 1 1 1 1 2 2 1 0   1   1]
  0 1 2 3 5 6 7 8 9 10 11 12

这里的下标总共偏移了6，减去6后得到最大的两项是1,2

如果有N个区间，复杂度是O(MN)，全部都扫的话是O(M^2N)

convexopt 发表于 2020-2-25 12:55
如果重合的部分不在[-M M]里就不能算啊

我觉得这个判断一下就可以吧？比如说如果M是3.然后给了一个{[-5, -2], [-6, -1]}。扫的时候如果不在range就不作数

             -6   -5    -2    -1   
cnt          1    2     1     0     
maxInt    0    0     1     0     
result                  -2

convexopt 发表于 2020-2-25 09:35
我觉得这题和meeting room不一样，
1. Meeting room 里任何区间的重合都算，这题必须在[-M, M]这个范围 ...

我不知道是不是我没理解题意？我还是看不出来为什么不能用meeting room算？因为出现最多的数字第一个肯定是一个start point，题目不是说随便输出一个就好了吗？用一个counter计算有多少个重合的interval，增长的时候记录一下start point。这样不可以吗？-M，M感觉无所谓吧？

楼主第二题是不是？ https://www.lintcode.com/problem ... the-sky/description
遇到interval start point++,遇到end point--. 看过程中point max是多少

rexue70 发表于 2020/02/25 04:21:50
楼主第二题是不是？ https://www.lintcode.com/problem/number-of-airplan...

有点不一样不是算interval的个数是求interval之间的数字哪个在最多的区间里。我有想过merge interval然后来算但是更麻烦也没有节省太多时间复杂度

luyulzs 发表于 2020-2-25 04:30
有点不一样不是算interval的个数是求interval之间的数字哪个在最多的区间里。我有想过merge interval然后 ...

我没有很理解，请问楼主可以再给个例子解释一下嘛？是否是去计算被interval overlap最多的数字？

rexue70 发表于 2020/02/25 04:48:17
我没有很理解，请问楼主可以再给个例子解释一下嘛？是否是去计算被interval overlap最多的数字？

不好意思我觉得我最近表达能力变差了。你理解的是对的就是被interval overlap最多的数字

补充内容 (2020-2-24 12:51):
如果有多个随便输出一个就好

luyulzs 发表于 2020-2-25 04:51
不好意思我觉得我最近表达能力变差了。你理解的是对的就是被interval overlap最多的 ...

感谢楼主，祝楼主onsite顺利

luyulzs 发表于 2020-2-25 04:30
有点不一样不是算interval的个数是求interval之间的数字哪个在最多的区间里。我有想过merge interval然后 ...

其实是一样的，找到最大值的时候存一下start point就可以了，最大值不就是interval重合的次数吗，start point就是出现最多的第一个数

cloudycloud 发表于 2020/02/25 06:33:47
其实是一样的，找到最大值的时候存一下start point就可以了，最大值不就是interval重合的次数吗，start...

嗯 我有点理解你的意思但是有点没想明白，能具体讲下怎么找start points出现的最多的次数。不是很明白因为start points在扫数组的时候会改变吧

luyulzs 发表于 2020-2-25 07:10
嗯 我有点理解你的意思但是有点没想明白，能具体讲下怎么找start points出现的最多的次数。不是很明白因为 ...

我觉得这题和meeting room不一样，
1. Meeting room 里任何区间的重合都算，这题必须在[-M, M]这个范围里
2. Meeting room 只需要输出最大的重合个数，这题要输出具体的数字

楼主的答案应该没问题的，非说能优化那就是带区间同时更新的线段树RMQ了，不可能考这个。

convexopt 发表于 2020/02/25 09:35:31
我觉得这题和meeting room不一样，
1. Meeting room 里任何区间的重合都算，这题必须在[-M,...

多谢你的回答，我怎么忘记线段树了！