Google on-site最后一面非常难的一道题目

wyh11 发表于 2014-3-14 12:13
嗯，不过google面试我感觉代码完成度不是特别重要。比较看重沟通的过程吧。
bless楼主

面试大哥一顿用手机whiteboard拍照啊。一个劲催，can you write the code?..

Linzertorte 发表于 2014-3-14 12:15
面试大哥一顿用手机whiteboard拍照啊。一个劲催，can you write the code?..

move on等结果吧，自己的感觉有时候和面试官给的反馈差异很大。
其他的面的怎么样啊？ 题难么？

wyh11 发表于 2014-3-13 23:01
partitin有点难描述，连续两次partition的pivot在中点不同侧就可以。不一定要中点为pivot

第一感觉没觉得Make sense，懒得细想了， 解释下？

wyh11 发表于 2014-3-14 12:41
move on等结果吧，自己的感觉有时候和面试官给的反馈差异很大。
其他的面的怎么样啊？ 题难么？

谢谢啊。

法1，先sort，然后折半，reverse，一插。O(nlogn)
证明很简单，都排序了，后一半大于前一半。

法2. 遍历所有奇数位的数，k=1，3，5，7，9...
比较a[k] 和 a[k-1],a[k+1] 的大小。如果a[k]小于两边的值，则对调a[k]和a[k-1],a[k+1]中间比较大的值。
证明的话，每次对调都不会影响前面已经处理好的序列，这样一直到最后。

北美农民 发表于 2014-3-14 12:42
第一感觉没觉得Make sense，懒得细想了， 解释下？

好像说错了。 =。=
我想想。

Linzertorte 发表于 2014-3-14 12:43
谢谢啊。

其它题目方便介绍一下么？

wyh11 发表于 2014-3-14 12:54
其它题目方便介绍一下么？

1. void shuffle(int A[],int n)
   
2. {
   
3.       int increase=1;
   
4.       for(int i=1;i<n;i++){
   
5.           int local=A[i]>=A[i-1]?1:0;
   
6.           if(increase!=local) swap(A[i],A[i-1]);
   
7.           increase^=1;
   
8.      }
   
9. }

复制代码

wyh11 发表于 2014-3-14 12:54
其它题目方便介绍一下么？

有个关于四分树(quad-tree)的题

google电面的时候被问了这道题，这题也就看上去吼人而已，nlogn的算法是一下子能想出来的，线性的算法仔细想一下也能想到
nlogn是排序后在偶数位填上后一半的数，然后在奇数位填上前一半的数
线性算法是当奇数位判断是否比前一个数小，不符合就交换，偶数位判断时候比前一个数大，不符合就交换
证明用反证法