新鲜滚烫Twitter电面

说你有个Log文档， 记录一个spotify的账户使用情况， 这个账户被很多家人共享了，然后每个人只能做两种操作Play和Pause。
每行log文件格式如下：
操作时间， play,pause, 用户ID

//06:01:43 Play     1
//06:02:43 Pau

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

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

log最后一行有个Pause All，会让当天所有没有Pause的用户暂定，并且记录时间


LZ当时给了merge interval的nlogn解法，被告知不是最优解。

用一个int cout=0;来记录当前在听音乐的人数，有人play就count++，当count==1记录起始时间。有人pause就减一，为零时计算时间。O(n)

merge interval 也是O(N)吧? 就是多站了写空间??

machdebagua 发表于 2019/06/27 09:10:32
用一个int cout=0;来记录当前在听音乐的人数，有人play就count++，当count==1记录起始时间。有人pause就减一，为零时计算时间。O(n)

对的，就是这样。厉害👍

xlblue 发表于 2019/06/27 09:51:18
merge interval 也是O(N)吧? 就是多站了写空间??

不是这样的，你可以看看楼上的回复

我以为算重叠的时间也算呢，猜一个followup，如果要算所有人播放时间综合，包括重叠的话，可以用hashmap<userId, timestamp>, init的时候是0，然后play的时候，记录time，第二次pause的时候，相减求值，time归0 。应该是也是O(n)的时间，但是space也是n。能优化吗

wangbd 发表于 2019-6-27 10:08
不是这样的，你可以看看楼上的回复

感谢分享！
请问你说的nlogn的解法是因为用了sorted，如果输入就是sorted的话我觉得merge interval也是O(n)
另一个层主说的O(n)也是要求输入是sorted的

谢谢分享！感觉这题关键在于理解

xlblue 发表于 2019-6-27 09:51
merge interval 也是O(N)吧? 就是多站了写空间??

merge  interval 要看条件， 有可能要先排个序这样就是 nlongn

请问楼主面的是哪个team