要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
系统
1分钟前
系统
1分钟前
系统
3分钟前
系统
6分钟前
系统
7分钟前
系统
40分钟前
全站
Warald 说: MemorialDay大礼包之七:【新功能】每日答题,答对了有大米奖励!加上每日登陆和每日签到,每天可以拿3颗大米!
40分钟前
系统
51分钟前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
全站
Warald 说: MemorialDay大礼包之五:【新功能】高级模式发帖,图片框里添加“大图片上传”,upto20张X10M
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
全站
Warald 说: MemorialDay大礼包之五:【新功能】小喇叭可以点击“发布”,可以在全局、板块或者帖子里发
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
全站
Warald 说: MemorialDay大礼包之四:【新功能】主题列表页显示图片,欢迎上图
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
全站
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
全站
Warald 说: MemorialDay大礼包之二:【新功能】论坛开启用户全局威望值,每楼右上方均可投票。
3小时前
全站
Warald 说: MemorialDay大礼包之一:【新功能】发帖后,可以邀请朋友参与讨论(自动功能)
3小时前
查看: 6096|回复: 39
收起左侧

Google Phone 9/30

[复制链接] |试试Instant~ |关注本帖
我的人缘0
ericlee27 发表于 2016-10-1 09:12:48 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

2016(7-9月) 码农类General 硕士 全职@Google - 猎头 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
面试官迟到了10分钟。。。。
-google 1point3acres据口音应该是个帅气白人哥,上来先自我介绍一番,在Google map做卫星*&……*&#!@#^^#什么什么的,太高大上,没怎么听懂。。。
然后接着就问了我两个beha问题:. 1point 3acres 论坛
1. What specific product in Google are you interested in and why.. 1point 3acres 论坛
2. Why you wanna work at Google.
胡扯了一堆然后大概时间过去了快20MIN..
coding..
.留学论坛-一亩-三分地一开始他问我知不知道circular buffer我说知道,然后让我简单写了一个,后来他说的东西把他自己都绕进去了。。。花了5分钟都没讲明白 然后他说never mid,let's move on.. - -####. Waral 博客有更多文章,
第二题问的是最大间隔.留学论坛-一亩-三分地

给一个unsorted array, for all a[i] <= a[j] 找出 j - i 最大的值。。。O(N) time O(N) Space
因为时间不多了加上也有点紧张。。没想出什么好办法。 后来他给了HINT说要开一个数组存smallest so far 然后我大概想了一会. 围观我们@1point 3 acres

. visit 1point3acres for more.开一个n长度的array, 从左往右每个位置存到目前位置的smallest number. 存完后从数组最右往左遍历 记录结果max, 如果a[right] > small[right - max - 1] 更新max = max + 1
如果发现a[right] <= smallest[right - max - 1] 说明,a[right] 比这之前的都小,就right--继续遍历。。。 直到right <= max。。。。

然后在结束前大概写出来了。。也不知道他怎么想的,有几个小BUG但是改过来了。 剩几分钟 愉快的聊了会天 。。。 可能是因为周五吧 他感觉全程都很高兴。。

有点坎坷,但是希望能过。。。。- -。。
. 1point 3acres 论坛

评分

4

查看全部评分


上一篇:求Amazon群面面经
下一篇:Google 9/30 电面面经

本帖被以下淘专辑推荐:

我的人缘0
 楼主| ericlee27 发表于 2016-10-2 06:57:52 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
不好意思 下午出去了 回家找了找昨天的草纸  把代码贴出来分享一下

是根据我那个思路写的,如果不对还请大牛们指出!
. 1point 3acres 论坛
  1. public int findMaximumGap(int[] nums){
  2.         // Invalid
  3.         if (nums == null || nums.length == 0) return 0;
  4.         int[] smallestSoFar = new int[nums.length];
  5.         smallestSoFar[0] = nums[0];
  6.         for (int i = 1; i < nums.length; ++i) {
  7.             smallestSoFar[i] = (nums[i] < smallestSoFar[i - 1]) ? nums[i] : smallestSoFar[nums.length - 1];. 1point3acres
  8.         }
  9.         int max = 0;
  10.         for (int j = nums.length - 1; j > max; j--){
  11.             while ((j > max) && (nums[j] >= smallestSoFar[j - max - 1])) {
  12.                 ++max;
  13.             }. 1point3acres
  14.         }
  15.         return max;
  16.     }
复制代码

-google 1point3acres


补充内容 (2016-10-3 03:59):
SorrY 各位,有一处TYPO 第七行最右边的坐标应该是i 不是nums.length-1,打上来的时候打错了 抱歉
回复 支持 2 反对 0

使用道具 举报

我的人缘0
WhatsFLAG 发表于 2016-10-2 00:58:55 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
这个方法好精妙啊,楼主大牛!
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| ericlee27 发表于 2016-10-2 01:26:20 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
WhatsFLAG 发表于 2016-10-2 00:58
这个方法好精妙啊,楼主大牛!

估计是因为周五了 面试官很开心 给了个大Hint 哈哈~
回复 支持 反对

使用道具 举报

我的人缘0
木易wen 发表于 2016-10-2 02:08:24 | 显示全部楼层
这题O(n), O(1)就行吧,双指针
  1. -google 1point3acres
  2. private static int findMaxDistance(int[] A) {. 围观我们@1point 3 acres
  3.                 if(A.length < 2) {
  4.                         return 0;.留学论坛-一亩-三分地
  5.                 }.留学论坛-一亩-三分地
  6.                 int begin = 0, end = 1, dist = 0;
  7.                 do {
  8.                         if(A[end] >= A[end - 1]) {
  9.                                 dist = Math.max(end - begin, dist);
  10.                         }else {
  11.                                 if(A[end] >= A[begin]) {
  12.                                         dist = Math.max(end - begin, dist);
  13.                                 }else {
  14.                                         begin = end;
  15.                                 }
  16.                         }
  17.                 } while(++ end < A.length);
  18.                 return dist;
  19.         }
复制代码
回复 支持 反对

使用道具 举报

我的人缘0
Hualiang 发表于 2016-10-2 02:27:02 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第二题不是buy and sell stock吗?
回复 支持 反对

使用道具 举报

我的人缘0
WhatsFLAG 发表于 2016-10-2 02:33:10 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
木易wen 发表于 2016-10-2 02:08. 留学申请论坛-一亩三分地
这题O(n), O(1)就行吧,双指针

看了你的代码,没有运行,但是不敢苟同啊
回复 支持 反对

使用道具 举报

我的人缘0
seuzbw 发表于 2016-10-2 02:34:23 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
木易wen 发表于 2016-10-2 02:08
这题O(n), O(1)就行吧,双指针

每次end<begin的时候,你把begin移动到end,这一步错了. more info on 1point3acres
你可以想象此时后面的数字都特别大,比一开始begin还大,你却把begin移动到end了
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
rcholic 发表于 2016-10-2 02:45:15 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
上代码试试,看看对吗?

  1. public int maxDistance(int[] nums) {


  2.         int[] minIndices = new int[nums.length]; // indices of the smallest number so far 来源一亩.三分地论坛.
  3.         int min = nums[0];
  4.         int minIndex = 0;
  5.         for (int i = 0; i < nums.length; i++) {. 围观我们@1point 3 acres
  6.             if (nums[i] < min) {
  7.                 min = nums[i];.1point3acres网
  8.                 minIndex = i;
  9.             }
  10.             minIndices[i] = minIndex;.留学论坛-一亩-三分地
  11.         }.1point3acres网

  12.         int j = nums.length - 1;
  13.         int result = Integer.MIN_VALUE;. 围观我们@1point 3 acres
  14.         while (j >= 0) {
  15.             if (nums[j] >= nums[minIndices[j]]) {
  16.                 result = Math.max(result, j - minIndices[j]);. 留学申请论坛-一亩三分地
  17.             }
    . Waral 博客有更多文章,
  18.             j--;
  19.         }

  20.         return result;
  21.     }
复制代码

补充内容 (2016-10-2 03:21):
好像错了!test case: [6, 2, 3, 4, 3, 5, 6], 这个情况应该是返回 6!
回复 支持 反对

使用道具 举报

我的人缘0
木易wen 发表于 2016-10-2 02:55:13 | 显示全部楼层

哦, 想错了,sorry
回复 支持 反对

使用道具 举报

我的人缘0
rcholic 发表于 2016-10-2 03:23:27 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
楼上@木易wen 的代码和我给出的代码貌似都错了,对于这个test case: . visit 1point3acres for more.
[6, 2, 3, 4, 3, 5, 6], 这个情况应该是返回 6!

上面代码返回的结果却是4!错了吧?
回复 支持 反对

使用道具 举报

我的人缘0
yhl 发表于 2016-10-2 03:50:21 | 显示全部楼层
试试看对吗?..
.本文原创自1point3acres论坛
int maxGap(vector<int> nums)
{
   vector<int> min(nums.size(), INT_MAX);
   int minIndex = 0, maxGap = 0; 来源一亩.三分地论坛.

   for (int i = 0; i < nums.size(); i++)
   {
      if (nums[i] <= nums[minIndex])
      {. From 1point 3acres bbs
         minIndex = i;
      }
      min[i] = minIndex;-google 1point3acres
   }
.本文原创自1point3acres论坛
   int r = nums.size() - 1;

   while (r >= 0)
   {
      int tmp = r;
.1point3acres网
      while (tmp > 0 && nums[r] > nums[min[tmp]]). From 1point 3acres bbs
      {
         maxGap = max(maxGap, r - min[tmp] + 1);
         tmp = min[tmp] - 1;
      }

      if (r == tmp)
         break;

      r = tmp;
   }
-google 1point3acres
   return maxGap;
}
回复 支持 反对

使用道具 举报

我的人缘0
rcholic 发表于 2016-10-2 03:52:44 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
用dynamic programming的思路写了一个,测试结果正确,但是空间O(n), 时间复杂度貌似是O(n^2)了:(. From 1point 3acres bbs

  1. public int maxDistance2(int[] A) {
  2.         if(A.length < 2) {
  3.             return 0;
  4.         }

  5.         int n = A.length;
    .1point3acres网
  6.         int[] dp = new int[n];. 一亩-三分-地,独家发布
  7.         dp[0] = 0;
  8.         for (int i = 1; i < n; i++) {
  9.             int curMinIndex = minIndex(A, i);// < i ? 1 : 0; // TODO: this is not working yet
  10.             dp[i] = Math.max(dp[i-1], curMinIndex);
  11.         }
  12. . 一亩-三分-地,独家发布
  13.         System.out.println(Arrays.toString(dp));

  14.         return dp[n-1];
  15.     }

  16.     // find the minimum index where nums[i] <= nums[curPos]
  17.     private int minIndex(int[] nums, int curPos) {-google 1point3acres
  18.         int result = curPos;
  19.         int k = curPos-1;
  20.         while (k >= 0) {
  21.             if (nums[k] <= nums[curPos]) {
  22.                 result = k;
  23.             }
    . From 1point 3acres bbs
  24.             k--;
  25.         }
  26. . 留学申请论坛-一亩三分地
  27.         return curPos - result;
  28.     }
复制代码
.留学论坛-一亩-三分地
补充内容 (2016-10-2 03:55):
// find the minimum index where nums <= nums[curPos]
应该改为
// find the max distance between the current position and the element that satisfies A <= A[curPos]
回复 支持 反对

使用道具 举报

我的人缘0
木易wen 发表于 2016-10-2 04:06:48 | 显示全部楼层
lz能上一下代码么?只想到了O(nlgn)解法, 想看一下你怎么做的,谢谢
回复 支持 反对

使用道具 举报

我的人缘0
rcholic 发表于 2016-10-2 04:06:51 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
不好意思,刷屏了,刚又试了一下双指针的做法,貌似也是正确的,时间O(n),不用空间 来源一亩.三分地论坛.

  1. public int maxDistance3(int[] A) {
  2.         if(A.length < 2) {. visit 1point3acres for more.
  3.             return 0;
  4.         }
  5.         int max = 0;

  6.         int left = 0, right = A.length - 1;
  7.         while (left < right) {
  8.             if (A[left] <= A[right]) {
  9.                 max = Math.max(max, right-left);
  10.                 right--;
  11.             } else {
  12.                 left++;
  13.             }
  14.         }. 留学申请论坛-一亩三分地

  15.         return max;
  16.     }
复制代码


test cases:

  1. []
  2. [1, 10, 6]
  3. [1, 10, 6, 3, 2, 3, 4, 5, 6].本文原创自1point3acres论坛
  4. [6, 1, 10, 6, 3, 2, 3, 4, 5, 6]
  5. [100, 6, 1, 10, 6, 3, 2, 3, 4, 5, 6]
复制代码


跑步去鸟。。。。
回复 支持 反对

使用道具 举报

我的人缘0
木易wen 发表于 2016-10-2 04:10:14 | 显示全部楼层
rcholic 发表于 2016-10-2 03:52
用dynamic programming的思路写了一个,测试结果正确,但是空间O(n), 时间复杂度貌似是O(n^2)了:( ...

n2就不用dp了。。直接全扫一遍找最大
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| ericlee27 发表于 2016-10-2 04:12:03 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
木易wen 发表于 2016-10-2 04:10
n2就不用dp了。。直接全扫一遍找最大
. Waral 博客有更多文章,
我晚上回家贴哈
回复 支持 反对

使用道具 举报

我的人缘0
rcholic 发表于 2016-10-2 04:19:54 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
其实这个题可以转化成一个这样的题目:. 1point3acres
假设你的数组是: A =[10, 2, 6, 1, 4, 5, 6

将这个数组做成prefix diff: D = A - A[i-1] (for i > 0), 转化成这个 D = [0, -8, 4, -5, 3, 1, 1]

题目相当于问在D数组中找出sum为0的区间长度,上面加粗体的部分即为答案!和best time to buy and sell stocks那个题差不多,只不过是问法变了

补充内容 (2016-10-2 04:20):
更正:D = A - A[i-1] (for i > 0)
回复 支持 反对

使用道具 举报

我的人缘0
WhatsFLAG 发表于 2016-10-2 04:21:30 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
rcholic 发表于 2016-10-2 04:06. visit 1point3acres for more.
不好意思,刷屏了,刚又试了一下双指针的做法,貌似也是正确的,时间O(n),不用空间
.留学论坛-一亩-三分地
看了代码还是不敢苟同啊,比如2,3,1?
回复 支持 反对

使用道具 举报

我的人缘0
木易wen 发表于 2016-10-2 04:23:00 | 显示全部楼层
yhl 发表于 2016-10-2 03:50
试试看对吗?..

int maxGap(vector nums)

[2, 1, 4, 5, 3, 0, 6, 7, 1, 1]这个不对,应该是8
回复 支持 反对

使用道具 举报

我的人缘0
rcholic 发表于 2016-10-2 04:23:05 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
WhatsFLAG 发表于 2016-10-2 04:21
看了代码还是不敢苟同啊,比如2,3,1?
-google 1point3acres
[2,3,1], yeah you got me
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-27 16:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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