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

您好！
本帖隐藏的内容需要积分高于 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！错了吧？