Google Pittsburgh Onsite 面经

oldady

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

hidden_track

oldady 发表于 2016-5-17 04:09
这题我觉得应该是考察trade off的能力看不同query pattern吧，毕竟不知道null操作占比多不多。我最开始说 ...

每次新来一个值不要sort一边吗？复杂度应该是nlogn吧

oldady

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

oldady

hidden_track 发表于 2016-5-17 04:13
每次新来一个值不要sort一边吗？复杂度应该是nlogn吧

新来的tuple直接看当前的state: min / max / recent需不需要更新就信，O(1)

jiebour

oldady 发表于 2016-5-17 04:05
噢忘记说了，题目是有一个sliding window size的，只关注最近这一段时间内的数据

貌似还是可以开俩heap，只是复杂度变成了N＊K

jiebour

oldady 发表于 2016-5-17 04:14
没仔细想，但这样似乎很繁琐。我是排序以后直接从左到右扫A / B，可能出现overlapping的情况一共有4种cas ...

A／B是啥意思？
另外排序是AB都拍？还是直拍一个？

oldady

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

jiebour

oldady 发表于 2016-5-17 04:39
A和B分别预处理sort + merge以后

while (iA < len(A) and iB < len(B)):

sounds awesome！！！

simonwoo

提示: 作者被禁止或删除内容自动屏蔽

wtcupup

楼主啥叫diff bwt intervals ? 比如 A: (1,2) (5,6) (9,10) B: (1,6) then diff = (3,4) ?

补充内容 (2016-5-17 19:42):
懂了， diff应该是 (3,4) (9,10)