亚麻一轮VO BQ + Coding

亚麻一轮VO，早就看地里说一轮VO不再是OA2 followup了 所以心里有准备。

面试者是一个在亚麻11年的白叔叔，不苟言笑，话很少。（长者架子）

上来先是疯狂BQ，记不太住了 大家记得每个故事都讲清楚。

然后直接撸题目，说来也巧，楼主上周面了别家公司，原题。。。所以二话不说直接最优解。

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

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

最后问问题，我强颜欢笑的跟他开玩笑，还是一直不笑。。真的难。

感觉自己做的最好了，如果亚麻爸爸不要的话就真的没办法了。

积分写的少一点，当初自己只有100积分的时候。特别难受，都懂。

发帖攒人品，求大叔看在我code写的还行的份上 拉我一把。


补充内容 (2018-12-13 08:52):
收到offer啦，感谢大叔抬我一手。报一下自己timeline
内推：8.12
OA1: 10.27
OA2: 11.3
VO invitation: 12.3
VO: 12.10
offer: 12.12
祝大家好运连连

funyaoleo 发表于 2018-12-13 02:55
楼主，想问下这道题的解法是不是把端点和bandwidth做成一个class，端点开始处是正bandwidth，结束处是负， ...

Good point。其实这已经是我第三次在面试/笔试中碰见这个题了。我之前想过你的解法，你的解法已经很优化了，但是不如pq好。

原因：假设有s个video，但是最多只会有n个video在同一时间播放（n< s），那么按照你的做法，sort + loop，time O（slog s ），空间O（2s）=O（s）

pq的解法是，先按视频的开始时间sort，然后pq中按结束时间sort，对于每一个视频，查看pq top是不是小于当前视频，如果是，那么pop。然后把当前视频push in queue。这样pq中永远是出现在同一时刻的视频。

这样的解法 时间复杂度O（slogn），空间O（n）。当然最坏的情况仍然是一样的。

MacJordan 发表于 2019-2-1 09:40
楼主请问这题是相当于meeting room II 嘛？给一堆时间段，求最少的会议室能满足所有的meetings？

还有 ...

是meeting room,后来发现其实leetcode的解法更简单，我的有点麻烦了。

1. sort [start, end] by start time in increasing order
   
2. init priority_queue by end time in increasing order
   
3. 
   
4. for item in input vector(sorted):
   
5.     if item.starttime > pq.front.endtime:
   
6.         pq.pop
   
7.     else
   
8.         pq.push(item)

复制代码

同时记录最大值就好啦！

补充内容 (2019-2-1 09:46):
不好意思 上面if应该是while

请问楼主你啥时候做的OA2呀，

Emmmma123 发表于 2018-12-11 06:57
请问楼主你啥时候做的OA2呀，

一个多月了...发邮件催 两天之后在垃圾箱里发现了VO邀请

求问楼主VO都不会问OA2了么，还有楼主OA2和vitual interview的时间隔了多久哇，谢谢

jellyjellyz 发表于 2018-12-11 08:31
求问楼主VO都不会问OA2了么，还有楼主OA2和vitual interview的时间隔了多久哇，谢谢

感觉不是全部都不问OA2，但是11月初的好多都是OA2，但是11月中到现在很多都是tech，就跟三轮一毛一样的。OA2和VO相隔了一个多月，最后发邮件给小蜜催的。

楼主，想问下这道题的解法是不是把端点和bandwidth做成一个class，端点开始处是正bandwidth，结束处是负，然后根据端点sort，然后依次循环过去，遇到开始端点就加上带宽，遇上结束端点就减去带宽，然后每次加的时候记得更新最大值？
想问问你是怎么做的以及pq在这里的用法？

wangshiyu1995 发表于 2018-12-13 03:26
Good point。其实这已经是我第三次在面试/笔试中碰见这个题了。我之前想过你的解法，你的解法已经很优化 ...

非常感谢楼主，你的解法确实很长棒，赞一个！
有个地方不是很明白，你说对所有视频先按开始时间排序，那么时间复杂度不应该也是nlogn么？

funyaoleo 发表于 2018-12-13 05:30
非常感谢楼主，你的解法确实很长棒，赞一个！
有个地方不是很明白，你说对所有视频先按开始时间排序，那 ...

哈哈哈哈对的对的....！确实没有太大的performance提升

wangshiyu1995 发表于 2018-12-13 05:47
哈哈哈哈对的对的....！确实没有太大的performance提升

谢谢lz的时间！