一亩三分地论坛

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

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

Google intern 面经

[复制链接] |试试Instant~ |关注本帖
maktf 发表于 2015-10-8 06:12:52 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 本科 实习@Google - 内推 - 技术电面 |Other其他

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

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

x
 楼主| maktf 发表于 2015-10-8 06:20:29 | 显示全部楼层
一不小心手滑没写东西就发出去了……
简单一说
第一个是给一个数组,数组里都是digit,组成一个数字,要求给数字加1,本身很简单,关键是得考虑到【1,2,-3,2】的不valid的情况以及负数的情况. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二个是地里有人说过的,给一个2d array 为update多query少,query多update少以及一样多设计算法
第三个是给一个每个元素都不重复的array,生成随机不重复序列,时间复杂度O(N)
第四个是有无穷多的数据,没有设备可以单独储存,设计sort方法
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-10-8 06:23:45 | 显示全部楼层
多谢分享!每轮做两题?都要求写code吗?我感觉有的好像只是设计题。
回复 支持 反对

使用道具 举报

jy_121 发表于 2015-10-8 06:30:36 | 显示全部楼层
楼主是内推还是自己投简历的啊?
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2015-10-8 06:38:40 | 显示全部楼层
小柯西 发表于 2015-10-8 06:23
多谢分享!每轮做两题?都要求写code吗?我感觉有的好像只是设计题。
-google 1point3acres
是的,标准每轮两题,一般来说都要写code,我只有最后那个是设计题(因为我第三个用的时间太长了,一直在跟recruiter讨论概率的问题)
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2015-10-8 06:39:25 | 显示全部楼层
jy_121 发表于 2015-10-8 06:30. 1point 3acres 璁哄潧
楼主是内推还是自己投简历的啊?
. 1point3acres.com/bbs
内推的,自己投简历几乎没用,除非在香港新加坡什么的还有希望
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-10-8 06:55:45 | 显示全部楼层
maktf 发表于 2015-10-8 06:20
一不小心手滑没写东西就发出去了……-google 1point3acres
简单一说 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一个是给一个数组,数组里都是digit,组成一个数字,要 ...

请问lz,负数是个什么意思?[-2, 0, 0, 0] -> [-1, 9, 9, 9]吗
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2015-10-8 07:34:05 | 显示全部楼层
nothingtrouble 发表于 2015-10-8 06:55
请问lz,负数是个什么意思?[-2, 0, 0, 0] -> [-1, 9, 9, 9]吗

对,但是负数不能出现在中间
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-8 09:50:10 | 显示全部楼层
第三个题是要用洗牌算法么?还是随机生成排列?
回复 支持 反对

使用道具 举报

xnature 发表于 2015-10-8 09:59:29 | 显示全部楼层
第三题像是随机生成permutation?. 鍥磋鎴戜滑@1point 3 acres

第四题是外排序?
回复 支持 反对

使用道具 举报

mooc 发表于 2015-10-8 10:23:09 | 显示全部楼层
LZ, 除了出题之外,有问背景或者一些计算机基础知识吗?

补充内容 (2015-10-8 10:29):. visit 1point3acres.com for more.
还有,第二题和第三题需要写出代码来吗?感觉没啥可写的。。。
回复 支持 反对

使用道具 举报

goo 发表于 2015-10-8 17:31:56 | 显示全部楼层
写了第一 第三题 有错误或者优化请指正
  1. vector<int>plusone(vector<int> nums){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  2. int k=checkvalid(nums);
  3. if(k==-1) return vector<int>();. 1point3acres.com/bbs
  4. if(k==nums.size()) nums[k-1]=1;
  5. else  if(nums[k]>0){
  6.        for(int i=nums.size()-1;i!=k;i--){
  7.         if(nums[i]==9). visit 1point3acres.com for more.
  8.                   nums[i]=0;
  9.           else{nums[i]++;return nums;}.鐣欏璁哄潧-涓浜-涓夊垎鍦
  10.                           }-google 1point3acres
  11.         if(nums[k]==9){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  12.                       nums[k]=0;
  13.                             if(k==0) nums.insert(nums.begin(),1);
  14.                                 else nums[k-1]=1;
  15.                                 }
  16.            else {nums[k]++;}. 1point3acres.com/bbs
  17.                 }

  18. else if(nums[k]<0){
  19.                for(int i=nums.size()-1;i!=k;i--){
  20.         if(nums[i]==0)        nums[i]=9;
  21.           else{nums[i]--;return nums;} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.                      }
  23.         if(nums[k]==-1){nums[k]=0;
  24.                                    if(k+1<nums.size())   nums[k+1]*=-1;. from: 1point3acres.com/bbs
  25.                                   }. Waral 鍗氬鏈夋洿澶氭枃绔,
  26.            else  nums[k]++;
  27. }
  28. return nums;-google 1point3acres
  29. }. Waral 鍗氬鏈夋洿澶氭枃绔,

  30. int  checkvalid(vector<int> nums){  //检查有效性并返回首个不为0的数字位置
  31. int k=0,len=nums.size();
  32. while(k<len &&nums[k]==0)
  33. k++;

  34. for(int i=k+1;i<len;i++){
  35. if(nums[i]<0) return -1;
  36. }
  37. return k;

  38. }. 鍥磋鎴戜滑@1point 3 acres
  39. . 1point 3acres 璁哄潧

  40. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  41. //第三题  感觉这个ischange好蠢 求一个更好一点的算法.1point3acres缃
  42. vector<int> randarray(vector<int> nums){
  43. bool ischange=false;
  44. int k=nums.size();
  45. if(k<=1) return nums;
  46. while(!ischange){.1point3acres缃
  47. while(k>1){
  48. int rand_num=rand()%k;
  49. if(rand_num!=k-1) ischange=true;
  50. swap(nums[rand_num],nums[k-1]);
  51. k--;
  52.    }}
  53. return nums;


  54. }
复制代码

补充内容 (2015-10-8 17:42):
第三题代码忘了一句srand((unsigned)time(0));
回复 支持 反对

使用道具 举报

xnature 发表于 2015-10-9 02:45:33 | 显示全部楼层
goo 发表于 2015-10-8 17:31
写了第一 第三题 有错误或者优化请指正

补充内容 (2015-10-8 17:42):

第三题为啥要判断某个位置上的数字是否改变?我觉得也可以没有和其他元素调换啊。
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2015-10-13 11:40:57 | 显示全部楼层
zxy_snow 发表于 2015-10-8 09:50
第三个题是要用洗牌算法么?还是随机生成排列?

就是随机生成排列,别想太复杂
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2015-10-13 11:41:44 | 显示全部楼层
xnature 发表于 2015-10-8 09:59
第三题像是随机生成permutation?

第四题是外排序?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
可以这么理解吧,第四题的关键应该是mapreduce
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2015-10-13 11:42:14 | 显示全部楼层
mooc 发表于 2015-10-8 10:23
LZ, 除了出题之外,有问背景或者一些计算机基础知识吗?

补充内容 (2015-10-8 10:29):

就是做题,啥也没问,都要写代码,除了最后那个
回复 支持 反对

使用道具 举报

mooc 发表于 2015-10-13 23:14:10 | 显示全部楼层
lz,第二题改怎么做?
回复 支持 反对

使用道具 举报

cszeus 发表于 2015-10-14 03:04:39 | 显示全部楼层
我也想问问,第二题怎么做的啊?
回复 支持 反对

使用道具 举报

goo 发表于 2015-10-22 21:39:03 | 显示全部楼层
xnature 发表于 2015-10-9 02:45
第三题为啥要判断某个位置上的数字是否改变?我觉得也可以没有和其他元素调换啊。

我又看了一下我的代码 while循环这里的有问题
修改后
  1. vector<int> randarray(vector<int> nums){
  2. bool ischange=false;
  3. int k=nums.size();. from: 1point3acres.com/bbs
  4. if(k<=1) return nums;
  5. srand((unsigned)time(0));
  6. while(!ischange){. 1point3acres.com/bbs
  7. k=nums.size();
  8. while(k>1){
  9. int rand_num=rand()%k;
  10. if(rand_num!=k-1) ischange=true;
  11. swap(nums[rand_num],nums[k-1]);
  12. k--;
  13.    }}
  14. return nums;


  15. }
复制代码
这个ischange的作用是确保新生成的序列与输入序列不一样(至少有一位改变过),如果题意允许这种情况,就可以去掉ischange了,这题目没说清,可加可不加
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2015-10-23 00:22:58 | 显示全部楼层
mooc 发表于 2015-10-13 23:14
lz,第二题改怎么做?

哦对, 忘了说query是要计算从1个点到另一个点组成的方阵的和
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 00:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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