Y*******u
发帖数: 4 | 1 国内大三下学生，投了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.
See http://goo.gl/Rn8eaW
Accepted by Google Summer Of Code 2015, project is implementing Filesystem
functions from tr2 namespace on Wine.
我的简历在LinkedIn：https://www.linkedin.com/in/yonghaohu
原题:https://leetcode.com/problems/wiggle-sort-ii/
一上来就是问题， 一个数组，排序成这样x0 < x1 > x2 < x3 > < > <
然后我就分析，make sure understand the question，
然后说能不能用method like insertion sort， 他说make sense
然后我用插入排序的思想跑了一遍， 然后是可以work的
然后问我时间复杂度，我最好最坏平均都分析了：
best time: On
worst: On^2
time complexity: O(n^2)
n is the size of array
然后问我有没有办法优化。。我一直尝试用了几个方法，但是都不行，最后他举例子，
提示了一下
5 < 7 > 5 < 7 > 5 < 7 > 6
然后排序后 ，提醒我有什么规律，我分析出最后两个数可以交换
然后他问我为什么可以交换成立
于是我重回一些例子，分析了一下，中间有一点跑偏了，我立马问他，what is our
question.
然后他说， 是为什么交换可以成立有什么规律。
最后分析出了奇数，偶数下， 可以比较最后两个数，然后交换不
最后我说写pseducode， 他说好。
然后就写， 在写的时候已经比较正式，就是比较了是否为空数组，
而且swap可以不做用其他方法，等等
写完了他就说没有时间了，结束
伪代码是这样的：
if(nums.size())
....
vector new_array;
new_aray.push_back(nums[0]);
if(size > 1) {
if（num[1] > num[0])
push_back(num[1]);
else
inserttobegin(num[1]);
}
for(int i=2;i
{
if(i%2 == 0) //i&1 {
if(new_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
}
}
} |
l**g
发帖数: 133 | 2 店面吗？我觉得做的很不错，如果这样还跪，那就只能多刷题了（前提是你没有做过这
道题）
另外关于题目：wiggle sort ii是去掉等号的，这个难度加大很多。需要求中值（这个
O(n)算法就很有技巧了），然后再partition，再wiggle，每个子问题都不简单。不刷
题必死无疑 |
Y*******u
发帖数: 4 | 3 @lygg
我是没有做过这道题目。。第一次见，怪我leetcode没有刷完。
现在问题是，我没有写real code， 虽然我有展示coding的技能：就是swap那里的优化。
但是感觉得分不会搞
anyway，求rp，求内推
国内面国外真的超级难， 两个月要来一个面试都好了！
谢谢你~~ |
Y*******u
发帖数: 4 | 4 @lygg
是电面
我是没有做过这道题目。。第一次见，怪我leetcode没有刷完。
现在问题是，我没有写real code， 虽然我有展示coding的技能：就是swap那里的优化。
但是感觉得分不会搞
anyway，求rp，求内推
国内面国外真的超级难， 两个月要来一个面试都好了！
谢谢你~~ |
l****u
发帖数: 1764 | 5 如果复杂度都O(N^2)了，会不会先sort下会更好？sort完把后面一半大数往前面小的中
间插，感觉能控制在O(NlogN)了 |
Y*******u
发帖数: 4 | |
l**g
发帖数: 133 | 7 你才大三，没什么好郁闷的，这种题让谁在45分钟内做出来都非常难，只能多刷题了。
明年大四再试一次呗，何况说不定并没有跪 |
l****u
发帖数: 1764 | 8 哦 那就不能sort了，需要用tricky的二分法了。。
【在 Y*******u 的大作中提到】
: @laoqiu
: 最后的方法是O(n)的
|
r***a
发帖数: 36 | 9 这题其实不难，最简单的直接sort后前半填奇数位后半填偶数位这种解法应该想都不用
想就能说出来，O（n）的解法也不难想。你代码风格不太好，既然你要开另外一个数组
干嘛不直接一开始就弄一个vector然后把输入调一次copy过去，后面弄那么多if else
和push_back太不好看
我觉得你的背景直接申美国工作基本上没什么机会，f家不从国内招g家今年招的主要都
是北京和上海的，而g家在国内招进去的人要么真的非常强要么得有非常好的运气，你
无论背景还是有点弱，你的本科学校我听都没听说过，无acm竞赛经历项目也没亮点，
当然google summer project算是个亮点但也只能帮你过google的简历关。而且你是本
科这就是你明年4月份没版本抽H1B，就算一次抽中最早也得2018年10月才能去上班，除
了有海外office的公司能安排你去parking外基本上其他公司不会冒这个风险去招你 |
e*******s
发帖数: 1979 | 10 wiggle ii 是难一些 总觉得这一系列wiggle的题都很恶心 做得没有美感 起鸡皮疙瘩
【在 Y*******u 的大作中提到】
: 国内大三下学生，投了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.
: See http://goo.gl/Rn8eaW
: Accepted by Google Summer Of Code 2015, project is implementing Filesystem
: functions from tr2 namespace on Wine.
|
