一亩三分地论坛

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

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

Google Phone 9/30

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

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

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

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

x
面试官迟到了10分钟。。。。
据口音应该是个帅气白人哥,上来先自我介绍一番,在Google map做卫星*&……*&#!@#^^#什么什么的,太高大上,没怎么听懂。。。
然后接着就问了我两个beha问题:
1. What specific product in Google are you interested in and why.
2. Why you wanna work at Google.
胡扯了一堆然后大概时间过去了快20MIN..
coding.. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
一开始他问我知不知道circular buffer我说知道,然后让我简单写了一个,后来他说的东西把他自己都绕进去了。。。花了5分钟都没讲明白 然后他说never mid,let's move on.. - -####. 1point3acres.com/bbs
第二题问的是最大间隔

给一个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。。。。. visit 1point3acres.com for more.

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

有点坎坷,但是希望能过。。。。- -。。. 1point 3acres 璁哄潧

评分

4

查看全部评分

本帖被以下淘专辑推荐:

 楼主| ericlee27 发表于 2016-10-2 06:57:52 | 显示全部楼层
不好意思 下午出去了 回家找了找昨天的草纸  把代码贴出来分享一下. Waral 鍗氬鏈夋洿澶氭枃绔,

是根据我那个思路写的,如果不对还请大牛们指出!
. visit 1point3acres.com for more.
  1. public int findMaximumGap(int[] nums){
  2.         // Invalid. 鍥磋鎴戜滑@1point 3 acres
  3.         if (nums == null || nums.length == 0) return 0;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.         int[] smallestSoFar = new int[nums.length];. Waral 鍗氬鏈夋洿澶氭枃绔,
  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;. visit 1point3acres.com for more.
  10.         for (int j = nums.length - 1; j > max; j--){. 1point3acres.com/bbs
  11.             while ((j > max) && (nums[j] >= smallestSoFar[j - max - 1])) {
  12.                 ++max;
  13.             }
  14.         }
  15.         return max;
  16.     }
复制代码

. 1point3acres.com/bbs
.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2016-10-3 03:59):. Waral 鍗氬鏈夋洿澶氭枃绔,
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]) {. 1point 3acres 璁哄潧
  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;. from: 1point3acres.com/bbs
  14.                                 }
  15.                         }
  16.                 } while(++ end < A.length);
  17.                 return dist;. 鍥磋鎴戜滑@1point 3 acres
  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)就行吧,双指针
.鏈枃鍘熷垱鑷1point3acres璁哄潧
每次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];
  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;. Waral 鍗氬鏈夋洿澶氭枃绔,
  11.         }

  12.         int j = nums.length - 1;
  13.         int result = Integer.MIN_VALUE;
  14.         while (j >= 0) {
  15.             if (nums[j] >= nums[minIndices[j]]) {
  16.                 result = Math.max(result, j - minIndices[j]);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  17.             }
  18.             j--;
  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 | 显示全部楼层

-google 1point3acres哦, 想错了,sorry
回复 支持 反对

使用道具 举报

rcholic 发表于 2016-10-2 03:23:27 | 显示全部楼层
楼上@木易wen 的代码和我给出的代码貌似都错了,对于这个test case:
[6, 2, 3, 4, 3, 5, 6], 这个情况应该是返回 6!.鐣欏璁哄潧-涓浜-涓夊垎鍦

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

使用道具 举报

yhl 发表于 2016-10-2 03:50:21 | 显示全部楼层
试试看对吗?... 1point 3acres 璁哄潧

. more info on 1point3acres.comint 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])
      {. 1point3acres.com/bbs
         minIndex = i;. visit 1point3acres.com for more.
      }
      min[i] = minIndex;
   }

   int r = nums.size() - 1;
. from: 1point3acres.com/bbs
   while (r >= 0)
   {
      int tmp = r; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 鍥磋鎴戜滑@1point 3 acres
      while (tmp > 0 && nums[r] > nums[min[tmp]]). From 1point 3acres bbs
      {
         maxGap = max(maxGap, r - min[tmp] + 1);
         tmp = min[tmp] - 1;
      }. 1point3acres.com/bbs
. 1point3acres.com/bbs
      if (r == tmp)
         break;

      r = tmp;
   }

   return maxGap;
}
回复 支持 反对

使用道具 举报

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

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

  5.         int n = A.length;
  6.         int[] dp = new int[n];
  7.         dp[0] = 0;. 鍥磋鎴戜滑@1point 3 acres
  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.         System.out.println(Arrays.toString(dp));

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

  15.     // find the minimum index where nums[i] <= nums[curPos]
  16.     private int minIndex(int[] nums, int curPos) {
  17.         int result = curPos;
  18.         int k = curPos-1;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  19.         while (k >= 0) {
  20.             if (nums[k] <= nums[curPos]) {
    . 1point3acres.com/bbs
  21.                 result = k;
  22.             }
  23.             k--;
  24.         }
  25. . more info on 1point3acres.com
  26.         return curPos - result;
  27.     }
复制代码

补充内容 (2016-10-2 03:55):. 鍥磋鎴戜滑@1point 3 acres
// 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.         }
  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--;.1point3acres缃
  11.             } else {
  12.                 left++;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13.             }
  14.         }
  15. . visit 1point3acres.com for more.
  16.         return max;
  17.     }
复制代码


test cases:

  1. []
  2. [1, 10, 6]
  3. [1, 10, 6, 3, 2, 3, 4, 5, 6]
  4. [6, 1, 10, 6, 3, 2, 3, 4, 5, 6]
  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: 1point3acres.com/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那个题差不多,只不过是问法变了

补充内容 (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
不好意思,刷屏了,刚又试了一下双指针的做法,貌似也是正确的,时间O(n),不用空间

看了代码还是不敢苟同啊,比如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
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 08:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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