我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
查看: 9938|回复: 75
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
Linzertorte 发表于 2014-3-14 11:32:07 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

2014(1-3月) 码农类General 硕士 全职@Google - 内推 - Onsite  | Other |

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
写一个shuffle数组的算法
给一个数组A[],里面的数是无序的,比如 A[]={1,2,3,7,3,2,5}
shuffle完之后,使之满足A[0]<=A[1]>=A[2]<=A[3]..
比如一种可能的结果是 A[]={1,7,3,5,2,2,1} 来源一亩.三分地论坛.

void shuffle(int A[], int n).留学论坛-一亩-三分地
{
}. 留学申请论坛-一亩三分地
写出算法,并且证明其正确性。. 1point 3acres 论坛



补充内容 (2014-3-14 11:36):
改正 :比如一种可能的结果是 A[]={1,7,3,5,2,3,2}

评分

6

查看全部评分


上一篇:GOOGLE电面面经 估计跪了
下一篇:春假扭腰Bloomberg一游

本帖被以下淘专辑推荐:

我的人缘0
ototsuyume 发表于 2014-3-14 13:34:49 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
google电面的时候被问了这道题,这题也就看上去吼人而已,nlogn的算法是一下子能想出来的,线性的算法仔细想一下也能想到
nlogn是排序后在偶数位填上后一半的数,然后在奇数位填上前一半的数
线性算法是当奇数位判断是否比前一个数小,不符合就交换,偶数位判断时候比前一个数大,不符合就交换
证明用反证法
回复 支持 1 反对 0

使用道具 举报

我的人缘0
北美农民 发表于 2014-3-14 11:44:15 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
本帖最后由 北美农民 于 2014-3-13 22:45 编辑

我感觉可以用调整算法.

从第一个数开始往右扫描, 我们要做的是当扫描到第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]。
其余的情况不用理会

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

评分

3

查看全部评分

回复 支持 1 反对 0

使用道具 举报

我的人缘0
wyh11 发表于 2014-3-14 12:53:10 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
回复 支持 1 反对 0

使用道具 举报

我的人缘0
wyh11 发表于 2014-3-14 11:43:53 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
先把数组由小到大排序
然后从中间分成两个数组,
把第二部分reverse。
再把两个数组合并。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2014-3-14 11:48:35 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
北美农民 发表于 2014-3-14 11:44
我感觉可以用调整算法.

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

请写code
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2014-3-14 11:51:11 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
wyh11 发表于 2014-3-14 11:43
先把数组由小到大排序
然后从中间分成两个数组,. From 1point 3acres bbs
把第二部分reverse。

你这个是nlogN的算法。题目只要求一个偏序关系。有没有更快的?
回复 支持 反对

使用道具 举报

我的人缘0
北美农民 发表于 2014-3-14 11:51:55 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
wyh11 发表于 2014-3-13 22:43
先把数组由小到大排序
然后从中间分成两个数组,.1point3acres网
把第二部分reverse。

其实不用排序, partition直到中间点为pivot就行
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
JOJULUBBI 发表于 2014-3-14 11:55:37 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
wyh11 发表于 2014-3-14 11:43
先把数组由小到大排序
然后从中间分成两个数组,
把第二部分reverse。

+1,偶数个数跟奇数个数要分开讨论?
回复 支持 反对

使用道具 举报

我的人缘0
wyh11 发表于 2014-3-14 12:01:25 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
北美农民 发表于 2014-3-14 11:51
其实不用排序, partition直到中间点为pivot就行

partitin有点难描述,连续两次partition的pivot在中点不同侧就可以。不一定要中点为pivot
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2014-3-14 12:08:55 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
wyh11 发表于 2014-3-14 12:01
partitin有点难描述,连续两次partition的pivot在中点不同侧就可以。不一定要中点为pivot
. more info on 1point3acres
写代码是不是不太好写啊?这个题当时只剩下10分钟了。做完还要向面试官提问的环节。
回复 支持 反对

使用道具 举报

我的人缘0
wyh11 发表于 2014-3-14 12:13:52 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
Linzertorte 发表于 2014-3-14 12:08 . From 1point 3acres bbs
写代码是不是不太好写啊?这个题当时只剩下10分钟了。做完还要向面试官提问的环节。
.本文原创自1point3acres论坛
嗯,不过google面试我感觉代码完成度不是特别重要。比较看重沟通的过程吧。
bless楼主
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2014-3-14 12:15:52 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
wyh11 发表于 2014-3-14 12:13
嗯,不过google面试我感觉代码完成度不是特别重要。比较看重沟通的过程吧。
bless楼主
. Waral 博客有更多文章,
面试大哥一顿用手机whiteboard拍照啊。一个劲催,can you write the code?..
回复 支持 反对

使用道具 举报

我的人缘0
wyh11 发表于 2014-3-14 12:41:47 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
Linzertorte 发表于 2014-3-14 12:15 . visit 1point3acres for more.
面试大哥一顿用手机whiteboard拍照啊。一个劲催,can you write the code?..

move on等结果吧,自己的感觉有时候和面试官给的反馈差异很大。
其他的面的怎么样啊? 题难么?
回复 支持 反对

使用道具 举报

我的人缘0
北美农民 发表于 2014-3-14 12:42:17 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
wyh11 发表于 2014-3-13 23:01
partitin有点难描述,连续两次partition的pivot在中点不同侧就可以。不一定要中点为pivot
. 1point3acres
第一感觉没觉得Make sense,懒得细想了, 解释下?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2014-3-14 12:43:59 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
wyh11 发表于 2014-3-14 12:41
move on等结果吧,自己的感觉有时候和面试官给的反馈差异很大。
其他的面的怎么样啊? 题难么?

谢谢啊。
回复 支持 反对

使用道具 举报

我的人缘0
lixiang.xjtu 发表于 2014-3-14 12:45:34 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
法1,先sort,然后折半,reverse,一插。O(nlogn)
证明很简单,都排序了,后一半大于前一半。
-google 1point3acres
法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]中间比较大的值。
证明的话,每次对调都不会影响前面已经处理好的序列,这样一直到最后。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
wyh11 发表于 2014-3-14 12:54:35 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

其它题目方便介绍一下么?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2014-3-14 13:23:44 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
wyh11 发表于 2014-3-14 12:54
其它题目方便介绍一下么?
  1. void shuffle(int A[],int n). 围观我们@1point 3 acres
  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. }
复制代码

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2014-3-14 13:28:49 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
wyh11 发表于 2014-3-14 12:54
其它题目方便介绍一下么?

有个关于四分树(quad-tree)的题
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-28 13:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表