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

写一个shuffle数组的算法
给一个数组A[]，里面的数是无序的，比如 A[]={1,2,3,7,3,2,5}
shuff

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

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

strong>
改正 :比如一种可能的结果是 A[]={1,7,3,5,2,3,2}

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

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

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

我感觉可以用调整算法.

从第一个数开始往右扫描， 我们要做的是当扫描到第i个数的时候， 前i个数必须满足 a[0] <=a[1] >= a[2] .... a， 当i为n就结束了

当i为0, 2, 4...，前i - 1个元素已经满足了。 如果a[ i ] > a[i + 1] 交换a[ i ] 和 a[i + 1]， 这样使得前i个都满足, 因为a[i + 1] 必然小于a[ i - 1]。
当i为1,3,5... 同理， 如果a[ i ] < a[i + 1], 交换使得前i个满足， 因为a[i + 1] 必然大于a[i - 1]。其余的情况不用理会

我们每一步都能保证当前和之前的元素都满足这个规律， 所以必然有解。

先把数组由小到大排序
然后从中间分成两个数组，
把第二部分reverse。
再把两个数组合并。

北美农民 发表于 2014-3-14 11:44
我感觉可以用调整算法.

从第一个数开始往右扫描， 我们要做的是当扫描到第i个数的时候， 前i个数必须满足 ...

请写code

wyh11 发表于 2014-3-14 11:43
先把数组由小到大排序
然后从中间分成两个数组，
把第二部分reverse。

你这个是nlogN的算法。题目只要求一个偏序关系。有没有更快的？

wyh11 发表于 2014-3-13 22:43
先把数组由小到大排序
然后从中间分成两个数组，
把第二部分reverse。

其实不用排序， partition直到中间点为pivot就行

wyh11 发表于 2014-3-14 11:43
先把数组由小到大排序
然后从中间分成两个数组，
把第二部分reverse。

+1，偶数个数跟奇数个数要分开讨论？

北美农民 发表于 2014-3-14 11:51
其实不用排序， partition直到中间点为pivot就行

partitin有点难描述，连续两次partition的pivot在中点不同侧就可以。不一定要中点为pivot

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

写代码是不是不太好写啊？这个题当时只剩下10分钟了。做完还要向面试官提问的环节。

Linzertorte 发表于 2014-3-14 12:08
写代码是不是不太好写啊？这个题当时只剩下10分钟了。做完还要向面试官提问的环节。

嗯，不过google面试我感觉代码完成度不是特别重要。比较看重沟通的过程吧。
bless楼主