《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 5880|回复: 39
收起左侧

Google Phone 9/30

[复制链接] |试试Instant~ |关注本帖
ericlee27 发表于 2016-10-1 09:12:48 | 显示全部楼层 |阅读模式

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

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

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

x
面试官迟到了10分钟。。。。
据口音应该是个帅气白人哥,上来先自我介绍一番,在Google map做卫星*&……*&#!@#^^#什么什么的,太高大上,没怎么听懂。。。
然后接着就问了我两个beha问题:
. Waral 鍗氬鏈夋洿澶氭枃绔,1. What specific product in Google are you interested in and why.
2. Why you wanna work at Google..鏈枃鍘熷垱鑷1point3acres璁哄潧
胡扯了一堆然后大概时间过去了快20MIN... 1point 3acres 璁哄潧
coding... From 1point 3acres bbs
一开始他问我知不知道circular buffer我说知道,然后让我简单写了一个,后来他说的东西把他自己都绕进去了。。。花了5分钟都没讲明白 然后他说never mid,let's move on.. - -####
第二题问的是最大间隔

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

开一个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但是改过来了。 剩几分钟 愉快的聊了会天 。。。 可能是因为周五吧 他感觉全程都很高兴。。
. 1point3acres.com/bbs
有点坎坷,但是希望能过。。。。- -。。

评分

4

查看全部评分

本帖被以下淘专辑推荐:

 楼主| ericlee27 发表于 2016-10-2 06:57:52 | 显示全部楼层
不好意思 下午出去了 回家找了找昨天的草纸  把代码贴出来分享一下. From 1point 3acres bbs

是根据我那个思路写的,如果不对还请大牛们指出!. 1point3acres.com/bbs

  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];
  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.             }
  14.         }
  15.         return max;
  16.     }
复制代码

. 鍥磋鎴戜滑@1point 3 acres
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

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

使用道具 举报

WhatsFLAG 发表于 2016-10-2 00:58:55 | 显示全部楼层
这个方法好精妙啊,楼主大牛!
回复 支持 反对

使用道具 举报

 楼主| ericlee27 发表于 2016-10-2 01:26:20 | 显示全部楼层
WhatsFLAG 发表于 2016-10-2 00:58
这个方法好精妙啊,楼主大牛!

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

使用道具 举报

木易wen 发表于 2016-10-2 02:08:24 | 显示全部楼层
这题O(n), O(1)就行吧,双指针

  1. private static int findMaxDistance(int[] A) {
  2.                 if(A.length < 2) {
  3.                         return 0;
  4.                 }
  5.                 int begin = 0, end = 1, dist = 0;
  6.                 do {
  7.                         if(A[end] >= A[end - 1]) {
  8.                                 dist = Math.max(end - begin, dist);
  9.                         }else {
  10.                                 if(A[end] >= A[begin]) {
  11.                                         dist = Math.max(end - begin, dist);
  12.                                 }else {
  13.                                         begin = end;
  14.                                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.                         }
  16.                 } while(++ end < A.length);
  17.                 return dist;
  18.         }
复制代码
回复 支持 反对

使用道具 举报

Hualiang 发表于 2016-10-2 02:27:02 | 显示全部楼层
第二题不是buy and sell stock吗?
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-10-2 02:33:10 | 显示全部楼层
木易wen 发表于 2016-10-2 02:08
这题O(n), O(1)就行吧,双指针

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

使用道具 举报

seuzbw 发表于 2016-10-2 02:34:23 | 显示全部楼层
木易wen 发表于 2016-10-2 02:08. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这题O(n), O(1)就行吧,双指针

每次end<begin的时候,你把begin移动到end,这一步错了
你可以想象此时后面的数字都特别大,比一开始begin还大,你却把begin移动到end了
回复 支持 反对

使用道具 举报

rcholic 发表于 2016-10-2 02:45:15 | 显示全部楼层
上代码试试,看看对吗?

  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];. from: 1point3acres.com/bbs
  4.         int minIndex = 0;
  5.         for (int i = 0; i < nums.length; i++) {
  6.             if (nums[i] < min) {
  7.                 min = nums[i];
  8.                 minIndex = i;
  9.             }
  10.             minIndices[i] = minIndex;
  11.         }

  12.         int j = nums.length - 1;. from: 1point3acres.com/bbs
  13.         int result = Integer.MIN_VALUE;. 1point 3acres 璁哄潧
  14.         while (j >= 0) {. visit 1point3acres.com for more.
  15.             if (nums[j] >= nums[minIndices[j]]) {. visit 1point3acres.com for more.
  16.                 result = Math.max(result, j - minIndices[j]);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  17.             } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  18.             j--;. Waral 鍗氬鏈夋洿澶氭枃绔,
  19.         }

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

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

使用道具 举报

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

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

使用道具 举报

rcholic 发表于 2016-10-2 03:23:27 | 显示全部楼层
楼上@木易wen 的代码和我给出的代码貌似都错了,对于这个test case:
[6, 2, 3, 4, 3, 5, 6], 这个情况应该是返回 6!. from: 1point3acres.com/bbs

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

使用道具 举报

yhl 发表于 2016-10-2 03:50:21 | 显示全部楼层
试试看对吗?..

int maxGap(vector<int> nums). 1point3acres.com/bbs
{
   vector<int> min(nums.size(), INT_MAX);
   int minIndex = 0, maxGap = 0;. from: 1point3acres.com/bbs

   for (int i = 0; i < nums.size(); i++)
   {
      if (nums[i] <= nums[minIndex])
      {
         minIndex = i;
      }
      min[i] = minIndex;
   }

   int r = nums.size() - 1;. more info on 1point3acres.com

   while (r >= 0)
   {
      int tmp = r;

      while (tmp > 0 && nums[r] > nums[min[tmp]])
      {
         maxGap = max(maxGap, r - min[tmp] + 1);
         tmp = min[tmp] - 1;
      }

      if (r == tmp). visit 1point3acres.com for more.
         break;
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
      r = tmp;-google 1point3acres
   }

   return maxGap;
}
回复 支持 反对

使用道具 举报

rcholic 发表于 2016-10-2 03:52:44 | 显示全部楼层
用dynamic programming的思路写了一个,测试结果正确,但是空间O(n), 时间复杂度貌似是O(n^2)了:(. Waral 鍗氬鏈夋洿澶氭枃绔,

  1. public int maxDistance2(int[] A) {
  2.         if(A.length < 2) {
  3.             return 0;
  4.         }
  5. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6.         int n = A.length;. 1point 3acres 璁哄潧
  7.         int[] dp = new int[n];. 鍥磋鎴戜滑@1point 3 acres
  8.         dp[0] = 0;
  9.         for (int i = 1; i < n; i++) {
  10.             int curMinIndex = minIndex(A, i);// < i ? 1 : 0; // TODO: this is not working yet
  11.             dp[i] = Math.max(dp[i-1], curMinIndex);. more info on 1point3acres.com
  12.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14.         System.out.println(Arrays.toString(dp));. 鍥磋鎴戜滑@1point 3 acres

  15.         return dp[n-1];. Waral 鍗氬鏈夋洿澶氭枃绔,
  16.     }

  17.     // find the minimum index where nums[i] <= nums[curPos]. From 1point 3acres bbs
  18.     private int minIndex(int[] nums, int curPos) {
  19.         int result = curPos;
  20.         int k = curPos-1;
  21.         while (k >= 0) {
  22.             if (nums[k] <= nums[curPos]) {
  23.                 result = k;
  24.             }
  25.             k--;-google 1point3acres
  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]
回复 支持 反对

使用道具 举报

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

使用道具 举报

rcholic 发表于 2016-10-2 04:06:51 | 显示全部楼层
不好意思,刷屏了,刚又试了一下双指针的做法,貌似也是正确的,时间O(n),不用空间

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

  6.         int left = 0, right = A.length - 1;
  7.         while (left < right) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.             if (A[left] <= A[right]) {
  9.                 max = Math.max(max, right-left);
  10.                 right--;
  11.             } else {
  12.                 left++;
  13.             }
  14.         }-google 1point3acres

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

-google 1point3acres
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]. 1point3acres.com/bbs
  5. [100, 6, 1, 10, 6, 3, 2, 3, 4, 5, 6]
复制代码


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

使用道具 举报

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

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

使用道具 举报

 楼主| ericlee27 发表于 2016-10-2 04:12:03 | 显示全部楼层
木易wen 发表于 2016-10-2 04:10
n2就不用dp了。。直接全扫一遍找最大

我晚上回家贴哈
回复 支持 反对

使用道具 举报

rcholic 发表于 2016-10-2 04:19:54 | 显示全部楼层
其实这个题可以转化成一个这样的题目:
假设你的数组是: 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那个题差不多,只不过是问法变了
. more info on 1point3acres.com
补充内容 (2016-10-2 04:20):
更正:D = A - A[i-1] (for i > 0)
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-10-2 04:21:30 | 显示全部楼层
rcholic 发表于 2016-10-2 04:06.1point3acres缃
不好意思,刷屏了,刚又试了一下双指针的做法,貌似也是正确的,时间O(n),不用空间
.1point3acres缃
看了代码还是不敢苟同啊,比如2,3,1?
回复 支持 反对

使用道具 举报

木易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
回复 支持 反对

使用道具 举报

rcholic 发表于 2016-10-2 04:23:05 | 显示全部楼层
WhatsFLAG 发表于 2016-10-2 04:21
看了代码还是不敢苟同啊,比如2,3,1?

[2,3,1], yeah you got me
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-23 04:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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