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

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

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

ototsuyume 发表于 2014-3-14 13:34
google电面的时候被问了这道题，这题也就看上去吼人而已，nlogn的算法是一下子能想出来的，线性的算法仔细 ...

make sense

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

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

williamshyy 发表于 2015-3-20 09:50
void shuffle(int A[], int n)
          {
                  boolean isValley=false;

这题现在还在考？

timtam85 发表于 2015-3-20 12:33
这题现在还在考？

就前几天的事。。。

话说难度在什么地方？

1. public void shuffle(int[] arr) {
   
2.                 if(arr == null || arr.length < 2)        return;
   
3.                 for(int i = 1; i < arr.length; ++i) {
   
4.                         if(i % 2 == 0) {
   
5.                                 if(arr[i] > arr[i - 1]) {
   
6.                                         int tmp = arr[i - 1];
   
7.                                         arr[i - 1] = arr[i];
   
8.                                         arr[i] = tmp;
   
9.                                 }
   
10.                         } else {
    
11.                                 if(arr[i] < arr[i - 1]) {
    
12.                                         int tmp = arr[i - 1];
    
13.                                         arr[i - 1] = arr[i];
    
14.                                         arr[i] = tmp;
    
15.                                 }
    
16.                         }
    
17.                 }
    
18.         }

复制代码

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

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

感谢楼主面经，我最后一轮也是个这

我好久前就看到这道题。。。证明可能麻烦？
我一直想如果follow up问输出所有可能性，该怎么做。

求问一下
比如 [1, 2, 1, 1, 1, 1, 1, 1]这种情况的话
并没有办法shuffle出满意的结果
该如何证明呢