Google Intern 电面 10/3

今下午刚刚面完Google Winter Intern 的电面， 两轮phone， 面试官是两个印度人求点人品，顺便希望能进host match！


直接说题吧！

第一轮：
1. 给一个array， 找出这个array 的local minimum。 Local minimum的定义是小于左边并且小于右边。
2. 给

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

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

ins many integers.所有integer都是(0-10k). Get the smallest k integers. 要求O(n)

问下楼主第二轮第二题怎么答的，谢谢。

kin332026 发表于 2016-10-31 13:55
请问楼主第一轮第三题是怎么做的呢

假设一定有解的情况下，可以看成一个贪心问题，"aaaabbbccd" 每次从string的第1位开始check s.charAt(i) != s.charAt(i - 1), 如果找到相等的就从后面抓一个和s.charAt(i - 1)不等的swap一下，prev = i - 1, 此时s.substring(0, prev +1)就满足条件，后面的递归处理就好，所以时间复杂度是O(N)

1. public static String nextNonRepeatPermutation(String s){
   
2.       if(s == null || s.length() < 2) return s;
   
3.       int i = 1;
   
4.       while(i < s.length() && s.charAt(i) != s.charAt(i - 1)){
   
5.         i++;
   
6.       }
   
7.       if(i == s.length()) {
   
8.         return s;
   
9.       }else{
   
10.         char prev = s.charAt(i);
    
11.         int from = i;
    
12.         while(i < s.length() && s.charAt(i) == prev){
    
13.           i++;
    
14.         }
    
15.         s = swap(s, from, i);
    
16.         return s.substring(0, from) + nextNonRepeatPermutation(s.substring(from));
    
17.       }
    
18.     }
    
19.     public static String swap(String s, int from ,int to){
    
20.       if(s == null || from < 0 || to >= s.length()) return s;
    
21.       char[] arr = s.toCharArray();
    
22.       char tmp = arr[from];
    
23.       arr[from]= arr[to];
    
24.       arr[to]= tmp;
    
25. 
    
26.       return new String(arr);
    
27.     }

复制代码

补充内容 (2016-11-1 00:52):
感觉还是用堆实现起来最简单确保正确：
把字符出现频率统计出来，扔在一个堆里。每次取出前两个频率高的字母，配成一对，次数减一，扔回堆。

jy_121 发表于 2016-10-4 09:51
问下楼主第二轮第二题怎么答的，谢谢。

我开始想把large file分割成一个一个subfile 后来面试官hint下想到可以用Bucketsort的方法, 建立一个10k size的bucket 然后面试官说好 给你一个hasNext() 和 next()的函数来traverse这个file

中间有些小bug没有想到。。毕竟好久没练bucket sort了 也不知道这样做是不是对的

做个参考吧

一滴水那个没看懂啊啊啊啊

mdzzxswl 发表于 2016-10-4 09:05
一滴水那个没看懂啊啊啊啊

其实就是想成一个weighted tree, 然后求weight最大的root->leaf 的path~

r39xu 发表于 2016-10-4 09:29
其实就是想成一个weighted tree, 然后求weight最大的root->leaf 的path~

这样！还有 为什么lz是winter的呀是自己选的吗～

r39xu 发表于 2016-10-4 10:10
我开始想把large file分割成一个一个subfile 后来面试官hint下想到可以用Bucketsort的方法, 建立一个10k  ...

多谢回复，没有注意取值范围，这样应该是可以的

请问楼主投了多久来的interview啊

第二轮 第二题 可以用 size 为 k 的min heap 吗？

Romeobaby 发表于 2016-10-4 10:47
第二轮 第二题 可以用 size 为 k 的min heap 吗？

当时也有提到min heap， 不过好像不符合O(n)的要求