一亩三分地论坛

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

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

Google最新电面

[复制链接] |试试Instant~ |关注本帖
kkk123 发表于 2016-2-3 22:45:08 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Fail在职跳槽

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

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

x
老美面试官,一个large array, remove 其中的even number,duplicate其中的odd number,必须in place。看起来简单,但是面试时有点晕,写了半天没写出完全能通过所有test case的code,肯定挂了~~~

评分

1

查看全部评分

erbenmo 发表于 2016-2-4 13:36:16 | 显示全部楼层
  1. int pass(int* arr, int N) {-google 1point3acres
  2.     int i=N-1;
  3.     int j=2*N;
  4.    
  5.     for(; i>=0; i--) {. 鍥磋鎴戜滑@1point 3 acres
  6.         if(arr[i] % 2 == 1) {
  7.             arr[j-1] = arr[i];
  8.             arr[j-2] = arr[i];
  9.             j -= 2;
  10.         }
  11.     }

  12.     for(i=0; j<2*N; i++, j++) {
  13.         arr[i] = arr[j];
  14.     }

  15.     return i;
  16. }
复制代码
回复 支持 3 反对 0

使用道具 举报

googlerr 发表于 2016-2-3 23:08:59 | 显示全部楼层
谢谢分享!楼主还记得什么test case没能通过吗?
回复 支持 反对

使用道具 举报

 楼主| kkk123 发表于 2016-2-3 23:10:42 | 显示全部楼层
odd number 很少但是even number很多的情况比如1,2,4,,6,8,10,.....
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-2-3 23:25:15 | 显示全部楼层
kkk123 发表于 2016-2-3 23:10
odd number 很少但是even number很多的情况比如1,2,4,,6,8,10,.....

谢谢。remove是把后面的往前移就行了,假如长度为l的数组remove了k个数,那么新的array只要确保最左边的l-k个数是正确的就行是吧?

除了2 pointer + HashMap,还有更好的解没?
回复 支持 反对

使用道具 举报

 楼主| kkk123 发表于 2016-2-3 23:27:43 | 显示全部楼层
googlerr 发表于 2016-2-3 23:25
谢谢。remove是把后面的往前移就行了,假如长度为l的数组remove了k个数,那么新的array只要确保最左边的l ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
问过能不能用其他data structure,说只能用这一个array,应该是确保左边就行了,面试官没明说
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-2-3 23:44:25 | 显示全部楼层
kkk123 发表于 2016-2-3 23:27
问过能不能用其他data structure,说只能用这一个array,应该是确保左边就行了,面试官没明说

谢谢。你是怎么做的呢?你举的那个例子通不过在什么地方?如果没有time要求,sort一遍也行,这样应该不用extra space
回复 支持 反对

使用道具 举报

 楼主| kkk123 发表于 2016-2-3 23:56:22 | 显示全部楼层
googlerr 发表于 2016-2-3 23:44
谢谢。你是怎么做的呢?你举的那个例子通不过在什么地方?如果没有time要求,sort一遍也行,这样应该不用 ...

time要求o(n),我是用的先统计odd number的数量,然后从2*count - 1的位置往前merge,如果even number就不merge,如果odd number就放两次。但是当2*count-1小于原来长度的时候1,2,4,6,8,10,3,就不能从3的位置开始因为最后一个是odd。在最后我其实想出来可以先partition array把所有odd放到左边然后再算count的方法但是已经没有时间改了
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-4 03:32:36 | 显示全部楼层
请问这个duplicate要管顺序吗,还是只要加到array里就行了?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-4 03:54:25 | 显示全部楼层
kkk123 发表于 2016-2-3 23:56
time要求o(n),我是用的先统计odd number的数量,然后从2*count - 1的位置往前merge,如果even number就 ...

直接用2个pointers不行么?
面试官又说,原array的length足够长度去做in place么
回复 支持 反对

使用道具 举报

 楼主| kkk123 发表于 2016-2-4 05:34:11 | 显示全部楼层
johnjavabean 发表于 2016-2-4 03:32
请问这个duplicate要管顺序吗,还是只要加到array里就行了?

没明说,他给的test case都是sorted,比如1,3,7和1,2,3,4,我觉得可能相对顺序还是得保持吧
回复 支持 反对

使用道具 举报

 楼主| kkk123 发表于 2016-2-4 05:35:22 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-2-4 03:54
直接用2个pointers不行么?
面试官又说,原array的length足够长度去做in place么

有说是个很大的array有unlimited length
回复 支持 反对

使用道具 举报

xhuaoe 发表于 2016-2-4 05:57:20 | 显示全部楼层
kkk123 发表于 2016-2-3 23:56
time要求o(n),我是用的先统计odd number的数量,然后从2*count - 1的位置往前merge,如果even number就 ...

和你想法差不多,先遍历一遍数组把奇数放到左边,再从右到左向数组内写数
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-2-4 06:41:10 | 显示全部楼层
好吧,理解错了。还以为删除偶数和删除重复的奇数。。。所以[1, 2, 4, 6]就会变成[1, 1]?
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-4 07:10:46 | 显示全部楼层
这很像quick sort 的 partition
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-4 07:19:38 | 显示全部楼层
One pass should work.
回复 支持 反对

使用道具 举报

 楼主| kkk123 发表于 2016-2-4 07:39:01 | 显示全部楼层
googlerr 发表于 2016-2-4 06:41
好吧,理解错了。还以为删除偶数和删除重复的奇数。。。所以[1, 2, 4, 6]就会变成[1, 1]?
-google 1point3acres
对的,[1,1,2,3]就要变成[1,1,1,1,3,3]
回复 支持 反对

使用道具 举报

 楼主| kkk123 发表于 2016-2-4 07:39:47 | 显示全部楼层

one pass怎么duplicate odd number?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-2-4 13:15:59 | 显示全部楼层
贴一个2 Pass的Java代码,供参考:
  1.         public void removeEvenDuplicateOdd(int[] nums) {
  2.                 int N = nums.length, pEven = -1;-google 1point3acres
  3.                 for(int i=0; i<N; i++) {. 1point 3acres 璁哄潧
  4.                         if(nums[i]%2==0) {
  5.                                 if(pEven==-1) pEven = i;
  6.                         }
  7.                         else {
  8.                                 if(pEven!=-1) {
  9.                                         swap(nums, pEven, i);
  10.                                         ++pEven;
  11.                                 }
  12.                         }
  13.                 }
  14.                 for(int i=pEven; i>=1; i--) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  15.                         nums[2*i-1] = nums[2*i-2] = nums[i-1];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.                 }
  17.         }
  18.         private void swap(int[] nums, int i, int j) {
  19.                 int temp = nums[i];
  20.                 nums[i] = nums[j];
  21.                 nums[j] = temp;
  22.         }
复制代码
回复 支持 反对

使用道具 举报

aloua 发表于 2016-2-4 14:03:27 | 显示全部楼层
请问是保证odd的数目小于数组一半么? 然后如果even多于一般,最后剩余的even怎么处理呢? 不管么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 03:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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