热乎的Google MTV onsite面经

4.2 平面里若有三个点或者五个点这样奇数个点的时候怎么平分其他点呢？
不知道是不是我理解有误？
还是说找平面内任意两点而不是给定点？

moonyellow 发表于 2016-4-18 17:06
4.2 平面里若有三个点或者五个点这样奇数个点的时候怎么平分其他点呢？
不知道是不是我理解有误？
还是说 ...

假设偶数个点

请问 第一题follow up怎么做呀 如果用堆的话 不能实时更新呀

补充内容 (2016-4-22 23:32):
或者 这样 建一个k+1的堆 每次来一个 删掉旧的 然后再丢回去 那样一次更新的复杂度就是o（k）了

陈润鹏 发表于 2016-4-22 23:31
请问 第一题follow up怎么做呀 如果用堆的话 不能实时更新呀

补充内容 (2016-4-22 23:32):

并不需要实时更新

mwsak47 发表于 2016-4-23 13:24
并不需要实时更新

有考虑过实时更新怎么做吗？

陈润鹏 发表于 2016-4-24 06:46
有考虑过实时更新怎么做吗？

没 不会        

考的数学题好多啊。。。第四轮第二题用到高中解析几何的知识。每两个点确定的直线可以表示成ax+by+c = 0，对于其他不在直线上的点(x1,y1)一定会有ax1+by1+c < 0或者 ax1+by1+c > 0。平分所有点意味着大于0的点和小于0的点数量一样多。时间复杂度O(n^2)

补充内容 (2016-5-9 22:44):
复杂度应该是O(n^3)

楼主第二题第二个 不知道是不是我理解错了 这个是不是combination sum2啊感觉 target就是总和的一半。。

月涌大江流 发表于 2016-5-6 13:45
考的数学题好多啊。。。第四轮第二题用到高中解析几何的知识。每两个点确定的直线可以表示成ax+by+c = 0， ...

这个任取两点就已经复杂度N^2了吧 每次在checkn个点感觉是n^3啊

wangmengcathy 发表于 2016-5-9 18:46
这个任取两点就已经复杂度N^2了吧 每次在checkn个点感觉是n^3啊

是的，应该是O(n^3)...