Google phone

Had Google phone last week. Onsite next week.
1. In an array with positive, negative and zero floats, find continuous subarray that has maximum product, output the start and end index of this subarray.
2. Design a da

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

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

of keyword "final", what's the difference between "final" and "static", etc.

jasonyang04 发表于 2018-2-19 03:43
How did you implement adding interval? O(N) time? Do we need to merge the overlapped intervals like  ...

I kept all intervals sorted so insertion could be done in O(logn) time but I don't think I implemented it correctly - coded an O(n) solution, tried to optimize to O(logn) but may have made some mistakes.

With all intervals sorted, search can be done in O(logn) time for sure.

They let me pass anyway so I don't think bar is too high for a phone screen.

RC-ACK 发表于 2018-2-19 05:55
I kept all intervals sorted so insertion could be done in O(logn) time but I don't think I impleme ...

My consideration is that if you use List<> to store intervals, there is no way to be O(logN) because insertion for List<> is O(N). Even if you use binary search to find the position for an interval, insertion will still cost O(N).

我觉得O(n) 可以接受 毕竟worst case  interval 已经排序了 你从小加到大 也是O(n)  当然可以写个best log(n) 的
真.log(n) 不是不可能 而是得有一个balanced BST 楼上说的interval tree的前提也是balanced BST 但是电面总不至于写红黑树吧哈哈lol

第二道是用segment tree来做么

How did you implement adding interval? O(N) time? Do we need to merge the overlapped intervals like [1,2] and [1,5] ?

anywho 发表于 2018-2-19 01:43
第二道是用segment tree来做么

Segment tree does not allow insertion. Interval tree is more accurate.

RC-ACK 发表于 2018-2-19 05:55
I kept all intervals sorted so insertion could be done in O(logn) time but I don't think I impleme ...

You didn’t merge intervals?

jasonyang04 发表于 2018-2-19 12:14
My consideration is that if you use List to store intervals, there is no way to be O(logN) because ...

哈哈，大家怎么都用英语了..
我感觉和你差不多啊。这题应该就是插入O（n）,search O（logn）吧？有什么advanced的做法吗？

Kwang100 发表于 2018-2-21 08:54
哈哈，大家怎么都用英语了..
我感觉和你差不多啊。这题应该就是插入O（n）,search O（logn）吧？有什么a ...

在 ArrayList里面放 Interval如果每次加完新的 Interval之后要进行 mergeInterval的工作的话，也是很麻烦...而且两次二分法也是很烦...

感谢楼主分享，希望楼主 onsite顺利，offer多多