Google Japan 店面

国内大三下学生，投了Google Japan 求RP， 感觉是跪了。  
此外，求大神们内推，邮箱christopherwuy at gmail.com  
简介： C > C++ = PHP > Python = R  
Contributor of WineHQ, had sent more than 50 patches about VC++ runtime(msvcr/msvcp).  Some of them are the implementation of tr2::Filesystem Library, tests of tr2::Threads and implementation of complex istream and ostream::operator.

Accepted by Google Summer Of Code 2015, project is impleme

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

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

_array[i-1] > a[i]) {
                        puish_back(a[i]);

                        swap(a[i-1], a[i]);
/*
int tmp = a[i-1]；

a[i-1] = a[i];

a[i] = tmp;

*/

}else {
                push_back(a[i];

}
}else {
        if(new_array[i-1] < a[i]) {
                push_bak(a[i];

        swap(a[i..);

}else{
        xx
}

}       
}

shuyangsheng 发表于 2016-7-27 05:59
worst case 应该是O(nlogn)吧，这不是完整的quick sort。我不是很确定。。。

其实这题greedy就可以了 ...

这道题用 greedy 是不对的，
如果题目是 a1 >= a2 <= a3 >= a4 <= a5

那么用 greedy 是对的。

比如， 5,5,5, 1,2,3,4,6,7,8,9,  你看看能不能用greedy?

mkcing 发表于 2016-7-27 05:04
average 是 O(n)  worst case是 O(n^2)

worst case 应该是O(nlogn)吧，这不是完整的quick sort。我不是很确定。。。

其实这题greedy就可以了：

1.     def wiggleSort(self, nums):
   
2.         # Write your code here
   
3.         for i in range(1,len(nums)):
   
4.             if (i%2==0 and nums[i] > nums[i-1]) or (i%2==1 and nums[i] < nums[i-1]):
   
5.                 nums[i],nums[i-1] = nums[i-1],nums[i]

复制代码

举个例子 a=[3,1,4]，那么要求就是[a0 a1] 上升，[a1,a2] 下降。
第一步 [a0 a1] 交换，得到[1,3,4]，这时候[a0 a1] 满足了上升条件。
第二步 [a1 a2]=[3,4] 要求下降，所以要交换成[1,4,3]。
我们知道 3 是大于 1 的，而 4 > 3,  所以 4 必然大于 3，所以 4 > 1 必然成立，也就是说后面的交换并不影响前面已经wiggle排好的序列。

找中位数的做法我写了半天也不太对，可能智商有限，数列长度是奇数的时候中间那个元素怎么处理有点捉急。。。

mkcing 发表于 2016-7-27 03:32
O(n)  就可以了，https://en.wikipedia.org/wiki/Quickselect

直接用QuickSelect找中位数最差情况应该不是O(n)吧。每次Select是O(n)，但是找到的pivot不一定是中位数，还要视pivot的位置递归左半边或者右半边。

倒是有找到一个O(n)的算法，但是有点follow不上了

http://cs.stackexchange.com/questions/1914/to-find-the-median-of-an-unsorted-array

归并排序 log2n，然后分一半，奇数位放前一半，偶数位放后一半，保证奇数位肯定小于偶数位，这样可否？

uuisafresh 发表于 2016-7-26 18:26
归并排序 log2n，然后分一半，奇数位放前一半，偶数位放后一半，保证奇数位肯定小于偶数位，这样可否？

可以。leetcode上有这么做的，但是他想要比类似插入排序更快方法，which就是他引导出来的办法。 O(n)就可以了。
ps： 归并排序是 O(n log(n))吧

HR 骗我说必须先做google apac test才能申谷歌。。。 早知道我也直接申了

YongHaoHu 发表于 2016-7-26 18:30
可以。leetcode上有这么做的，但是他想要比类似插入排序更快方法，which就是他引导出来的办法。 O(n)就可 ...

sorry，太久没做题，是nlogn

n次，过一遍，找中位数，用中位数把数组分两组，大的放偶位，小的放奇位，这样能否O(n)

zkern 发表于 2016-7-26 18:30
HR 骗我说必须先做google apac test才能申谷歌。。。 早知道我也直接申了

应该我是参加过gsoc，而gsoc当时说，只要成功参加就有内推的

uuisafresh 发表于 2016-7-26 18:43
sorry，太久没做题，是nlogn

n次，过一遍，找中位数，用中位数把数组分两组，大的放偶位，小的放奇位 ...

正解，但是把大的放在偶数位，小的放在奇数位，而且不用extra space 也需要技巧，https://en.wikipedia.org/wiki/Dutch_national_flag_problem,  需要用到这个技术

uuisafresh 发表于 2016-7-26 18:43
sorry，太久没做题，是nlogn

n次，过一遍，找中位数，用中位数把数组分两组，大的放偶位，小的放奇位 ...

找中位数需要nlogn了吧？

jyttwc901231 发表于 2016-7-27 01:57
找中位数需要nlogn了吧？

O(n)  就可以了，https://en.wikipedia.org/wiki/Quickselect