Google Phone 9/30

面试官迟到了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..
一开始他问

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

到right <= max。。。。

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

有点坎坷，但是希望能过。。。。- -。。

不好意思 下午出去了 回家找了找昨天的草纸  把代码贴出来分享一下

是根据我那个思路写的，如果不对还请大牛们指出!

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.     }

复制代码

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

ericlee27 发表于 2016-10-2 06:57
不好意思 下午出去了 回家找了找昨天的草纸  把代码贴出来分享一下

是根据我那个思路写的，如果不对还请 ...

1.         public static int maxDistance(int[] A) {
   
2.                 if(A.length<2)
   
3.                         return 0;
   
4.                 int[] smallest = new int[A.length];
   
5.                 int min = Integer.MAX_VALUE;
   
6.                 for (int i = 0; i < A.length; i++) {
   
7.                         min = A[i] > min ? min : A[i];
   
8.                         smallest[i] = min;
   
9.                 }
   
10.                 // left从right左边一位开始逐渐左移
    
11.                 int right = A.length - 1, left = right - 1;
    
12.                 int max = 0;
    
13.                 while (right >= max&&left>=0) {
    
14.                         if (A[right] > smallest[left]) {
    
15.                                 max = right - left;
    
16.                                 left--;
    
17.                         } else {
    
18.                                 right--;
    
19.                         }
    
20.                 }
    
21.                 return max;
    
22.         }

复制代码

一样解法

这题O(n), O(1)就行吧，双指针

1. 
   
2. private static int findMaxDistance(int[] A) {
   
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.         }

复制代码

这个方法好精妙啊，楼主大牛！

WhatsFLAG 发表于 2016-10-2 00:58
这个方法好精妙啊，楼主大牛！

估计是因为周五了 面试官很开心 给了个大Hint 哈哈~

第二题不是buy and sell stock吗？

木易wen 发表于 2016-10-2 02:08
这题O(n), O(1)就行吧，双指针

看了你的代码，没有运行，但是不敢苟同啊

木易wen 发表于 2016-10-2 02:08
这题O(n), O(1)就行吧，双指针

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

上代码试试，看看对吗？

1. public int maxDistance(int[] nums) {
   
2. 
   
3. 
   
4.         int[] minIndices = new int[nums.length]; // indices of the smallest number so far
   
5.         int min = nums[0];
   
6.         int minIndex = 0;
   
7.         for (int i = 0; i < nums.length; i++) {
   
8.             if (nums[i] < min) {
   
9.                 min = nums[i];
   
10.                 minIndex = i;
    
11.             }
    
12.             minIndices[i] = minIndex;
    
13.         }
    
14. 
    
15.         int j = nums.length - 1;
    
16.         int result = Integer.MIN_VALUE;
    
17.         while (j >= 0) {
    
18.             if (nums[j] >= nums[minIndices[j]]) {
    
19.                 result = Math.max(result, j - minIndices[j]);
    
20.             }
    
21.             j--;
    
22.         }
    
23. 
    
24.         return result;
    
25.     }

复制代码

补充内容 (2016-10-2 03:21):
好像错了！test case： ［6, 2, 3, 4, 3, 5, 6]， 这个情况应该是返回 6!

seuzbw 发表于 2016-10-2 02:34
每次end

哦， 想错了，sorry

楼上@木易wen 的代码和我给出的代码貌似都错了，对于这个test case：
［6, 2, 3, 4, 3, 5, 6]， 这个情况应该是返回 6!

上面代码返回的结果却是4！错了吧？