Google刚面完新鲜出炉Onsite3.9

tanis 发表于 2015-3-10 22:15
这不是标准的Inversions count么。。

是的呀，但是脑子一时短路，然后就悲剧了呀

分数的那个复杂度可以做到NlogN

例如k=5，可以构造出k-1个sorted arry list

1/2<2/3<3/4<4/5

1/3<2/4<3/5

1/4<2/5

1/5

然后直接把这几个sorted array list combine就好了

这样不用可以hashmap记录duplicate和最后再sort

第一题楼主存的是每一行的prefix sum？

第一题的第二个问没太看懂，给两个坐标，算围成的矩形的面积，不是直接坐标相减，然后长乘以宽就行了么？

楼主可以再细讲下么

感谢分享！

恕我孤陋寡闻，我觉得三哥都是很阴险的，要么就是笑面虎，要么就是板着一块脸。我和三哥面试基本上就没成功过。

ryuichist 发表于 2015-3-11 10:31
感谢分享！

恕我孤陋寡闻，我觉得三哥都是很阴险的，要么就是笑面虎，要么就是板着一块脸。我和三哥面试 ...

估计你太帅了，面了这么多， 没被三哥挂过。。

ryuichist 发表于 2015-3-11 10:31
感谢分享！

恕我孤陋寡闻，我觉得三哥都是很阴险的，要么就是笑面虎，要么就是板着一块脸。我和三哥面试 ...

感觉一般面试最难的是国人吧。。面试难度就最大

lzd1127 发表于 2015-3-11 11:31
感觉一般面试最难的是国人吧。。面试难度就最大

我觉得还是看人，三哥有的是很坑，但是国人真的题超难的，我遇过最难的题是国人出的。。也有同学被国人黑过。。但是也有人被国人照顾，真是难说...

第一题貌似出现过很多次了, 最优解法是二维树状数组或者线段树吗?时间复杂度两个function都是O(lognlogn)?

averillzheng 发表于 2015-3-10 21:57
surpass count 用merge sort的思想来做。

could you PLS explain the merge part ?  thanks!