一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 6760|回复: 75
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
Linzertorte 发表于 2014-3-14 11:32:07 | 显示全部楼层 |阅读模式

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

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

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

x
写一个shuffle数组的算法.1point3acres缃
给一个数组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)
{
}
写出算法,并且证明其正确性。



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

评分

6

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

北美农民 发表于 2014-3-14 11:44:15 | 显示全部楼层
本帖最后由 北美农民 于 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]。. Waral 鍗氬鏈夋洿澶氭枃绔,
当i为1,3,5... 同理, 如果a[ i ] < a[i + 1], 交换使得前i个满足, 因为a[i + 1] 必然大于a[i - 1]。
其余的情况不用理会

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

评分

3

查看全部评分

回复 支持 1 反对 0

使用道具 举报

wyh11 发表于 2014-3-14 12:53:10 | 显示全部楼层
回复 支持 1 反对 0

使用道具 举报

wyh11 发表于 2014-3-14 11:43:53 | 显示全部楼层
先把数组由小到大排序
然后从中间分成两个数组,
把第二部分reverse。
再把两个数组合并。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2014-3-14 11:48:35 | 显示全部楼层
北美农民 发表于 2014-3-14 11:44
我感觉可以用调整算法.

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

请写code
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2014-3-14 11:51:11 | 显示全部楼层
wyh11 发表于 2014-3-14 11:43 . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
先把数组由小到大排序
然后从中间分成两个数组,
把第二部分reverse。

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

使用道具 举报

北美农民 发表于 2014-3-14 11:51:55 | 显示全部楼层
wyh11 发表于 2014-3-13 22:43 .1point3acres缃
先把数组由小到大排序
然后从中间分成两个数组,
把第二部分reverse。

其实不用排序, partition直到中间点为pivot就行
回复 支持 反对

使用道具 举报

JOJULUBBI 发表于 2014-3-14 11:55:37 | 显示全部楼层
wyh11 发表于 2014-3-14 11:43
先把数组由小到大排序. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后从中间分成两个数组,
把第二部分reverse。

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

使用道具 举报

wyh11 发表于 2014-3-14 12:01:25 | 显示全部楼层
北美农民 发表于 2014-3-14 11:51
其实不用排序, partition直到中间点为pivot就行

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴partitin有点难描述,连续两次partition的pivot在中点不同侧就可以。不一定要中点为pivot
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2014-3-14 12:08:55 | 显示全部楼层
wyh11 发表于 2014-3-14 12:01
partitin有点难描述,连续两次partition的pivot在中点不同侧就可以。不一定要中点为pivot
. from: 1point3acres.com/bbs
写代码是不是不太好写啊?这个题当时只剩下10分钟了。做完还要向面试官提问的环节。
回复 支持 反对

使用道具 举报

wyh11 发表于 2014-3-14 12:13:52 | 显示全部楼层
Linzertorte 发表于 2014-3-14 12:08
写代码是不是不太好写啊?这个题当时只剩下10分钟了。做完还要向面试官提问的环节。

嗯,不过google面试我感觉代码完成度不是特别重要。比较看重沟通的过程吧。
bless楼主
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2014-3-14 12:15:52 | 显示全部楼层
wyh11 发表于 2014-3-14 12:13
嗯,不过google面试我感觉代码完成度不是特别重要。比较看重沟通的过程吧。
bless楼主

面试大哥一顿用手机whiteboard拍照啊。一个劲催,can you write the code?..
回复 支持 反对

使用道具 举报

wyh11 发表于 2014-3-14 12:41:47 | 显示全部楼层
Linzertorte 发表于 2014-3-14 12:15
面试大哥一顿用手机whiteboard拍照啊。一个劲催,can you write the code?..

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

使用道具 举报

北美农民 发表于 2014-3-14 12:42:17 | 显示全部楼层
wyh11 发表于 2014-3-13 23:01
partitin有点难描述,连续两次partition的pivot在中点不同侧就可以。不一定要中点为pivot

.鐣欏璁哄潧-涓浜-涓夊垎鍦第一感觉没觉得Make sense,懒得细想了, 解释下?
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2014-3-14 12:43:59 | 显示全部楼层
wyh11 发表于 2014-3-14 12:41
move on等结果吧,自己的感觉有时候和面试官给的反馈差异很大。
其他的面的怎么样啊? 题难么?
. 1point3acres.com/bbs
谢谢啊。
回复 支持 反对

使用道具 举报

lixiang.xjtu 发表于 2014-3-14 12:45:34 | 显示全部楼层
法1,先sort,然后折半,reverse,一插。O(nlogn)
证明很简单,都排序了,后一半大于前一半。

法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

查看全部评分

回复 支持 反对

使用道具 举报

wyh11 发表于 2014-3-14 12:54:35 | 显示全部楼层

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

使用道具 举报

 楼主| Linzertorte 发表于 2014-3-14 13:23:44 | 显示全部楼层
wyh11 发表于 2014-3-14 12:54
其它题目方便介绍一下么?
  1. void shuffle(int A[],int n)
  2. {
  3.       int increase=1;. 鍥磋鎴戜滑@1point 3 acres
  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

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2014-3-14 13:28:49 | 显示全部楼层
wyh11 发表于 2014-3-14 12:54
其它题目方便介绍一下么?

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 06:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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