google onsite面经

umd2011 发表于 2016-1-8 11:03
恭喜楼主 !
马上要去Mountain View onsite了，希望能沾沾楼主的喜气。 Big bless

加油，多看面经，版上的面经很有用的

zn88358800 发表于 2016-1-8 11:10
big cong 沾沾喜气

谢谢！！！

首先恭喜楼主啦 不过关于这个.“给一个complete tree，返回最后一个level的叶子（用二分的思路）” 怎么用二分的思路解决啊 ？ 这个题是要返回整个树的最后一层的最后一个节点吗

zjuzqh 发表于 2016-1-8 11:24
恭喜楼主拿到了Offer.然后有几点不清楚要问下楼主。1.第一题题目意思看不大懂，是给一个序列（时间点，股票 ...

1.第一题可以这么想，就是stream序列里有一个object，object包含时间点和股票的价格，让求当前历史数据里股票的最大值和最小值，然后给一个时间点，删除时间点上的股票，然后最大值和最小值可能就要更新了，因为删除的时间点上的可能就是之前的最大值或最小值。我的做法就是把历史股票全部都放在一个max heap里，然后删除的时候，把删除的股票放在map里，然后看max heap的root是否在被删除的map里，如果在就把这个点从heap里删除，这样找最大值，最小值同理。
2.complete tree这题怪我没有说清楚，是返回最后一个level的最后一个叶子，就是先找左右两个树的最左边一个分支的深度，如果两个深度一样，就说明这个要找的叶子在右树，否则在左树这样。。
3.是的，二分就是比如说输入给你一个（3，4）说明位置(3,4)这个格子的点是黑色的，然后我们按列做二分，看从0到4得中间那一列也就是第2列，遍历第二列看第二列有没有黑色的点，如果没有，说明第二列左边也没有黑色的点，因为前面说过，黑色的格子是全部connected的，也就是说，左边的边界在第二列的右边这样，按照这个规律二分
语言表达能力有限，不知道说清楚了没

bobzhang2004 发表于 2016-1-8 11:39
请问楼主股票那题求timestamp最大值是什么意思。一个time stamp不是只有一个值吗？还有请问complete tree楼 ...

是返回最后一个level的最后一个叶子，解答见上面一层

yjfox 发表于 2016-1-8 12:06
那个找边界，如果lz是对上下边界用binary search，那么左右一定要全走一遍才能确定边界吧。
如果这题意我 ...

解答我写在14楼啦

恭喜妹子！一直看你id！总算有了好结果了！

感谢LZ的分享！受益匪浅啊

第一轮的题目 楼主的解法 remove 操作是O（1）  getMax 和 getMin 操作是O（n）

另一种解法可以自己写一个indexed heap 通过在内部使用hashMap 将remove getMax getMin操作都变为 O（logn）

补充内容 (2016-1-10 07:34):
如果只是查询 那getMax getMin都是 O（1） remove还是O（logn）

第三轮合并 可以第一个binary search搜 0的边界  第二次搜1的边界  稍微改改就行