2/12/2016 Google电面面经

下午两点准时从加州来的电话，听声音是白人小哥，感觉蛮和蔼的。先问了简历，问了最interesting project，然后又问了the most challenging technical part of the project.. 然后开始coding

楼主不知道是电话通话质量不好还是耳机有问题，总是听不很清楚，结果第一题小哥说了题目，语速好快，我愣是一个字都没听懂。然后问小哥能不能paste题目

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

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

明，他说good， 然后就草草写了代码。最后随便问了个题目就完了~~

求Onsite，求bless 求过亚麻group！



补充内容 (2016-2-12 05:18):
写错了，是2月11号。。

第二题,

1. public class LocalMinimum {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[] arr = {3, 2, 5, 4, 3, 5};
   
5.                 System.out.println(findLocalMinimum(arr));
   
6.         }
   
7.         public static int findLocalMinimum(int[] arr) {
   
8.                 if (arr == null || arr.length == 0) {
   
9.                         return -1;
   
10.                 }
    
11.                
    
12.                 int start = 0;
    
13.                 int end = arr.length - 1;
    
14.                 while (start + 1 < end) {
    
15.                         int mid = (end - start) / 2 + start;
    
16.                         if (mid > 0 && arr[mid] > arr[mid - 1]) {
    
17.                                 end = mid;
    
18.                         } else {
    
19.                                 start = mid;
    
20.                         }
    
21.                 }
    
22.                
    
23.                 return arr[start] < arr[end]? start : end;
    
24.         }
    
25. }
    

复制代码

tianlu1 发表于 2016-2-24 11:06
第二题local minimum是这么定义的呢？如果要找数组最小值的话不scan整个数组要怎么弄呢？

local min就是这个数比它的左右neighbor都小。方法可用binary search, 具体可以参见leetcode find peek

mingzhou1987 发表于 2016-2-24 13:41
那如果只有最后两个元素是duplicate怎么办，不是至少要扫一个数组？不知道我的理解有没有错

不好意思忘记说了啊，数组里的数字都是unique的

明天的面经

加油加油啊， 应该会有不错的结果！！

第二题local minimum是这么定义的呢？如果要找数组最小值的话不scan整个数组要怎么弄呢？

第一题复杂度是o(n)吗？

Lg n 如果数组值是都是unique的。

kinggarden2001 发表于 2016-2-24 13:36
Lg n 如果数组值是都是unique的。

那如果只有最后两个元素是duplicate怎么办，不是至少要扫一个数组？不知道我的理解有没有错

mingzhou1987 发表于 2016-2-24 13:23
第一题复杂度是o(n)吗？

恩恩 是的