Google onsite 面经

lz是两周前去onsite的，感觉还行，因为有deadline，所以催了hr，一周就被拒了。

第一轮：。大概是个东欧小哥，先是聊聊自己对各种语言的看法，然后做题。发音有点不太清楚，题目交流花了一点时间。
给一堆positive integer 如【10，15，20，25】之类，然后可以对integer用上cut的方法(如果大于10，则一次cut产生一个10)，看在有限的cut的次数下，做多能cut多少个10出来.
可能描述的有点绕，举个例子：10 不需要cut，20， cut 一次就产生2个10， 30 ，cut1一次，产生一个10和一个20， cut2次产生3个10； 15 最多能被cut1次，会产生一个10.
我说greedy就行。然后coding。然后一题之后就让问问题了

第二轮：一个俄罗斯大叔1. 平面上一堆点，判断是否关于某个垂直于x轴的线对称，面经里有， 所以很快做完
2. 一个含有interger 的matrix， 找出一个点使得到左上角的submatrix

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

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

-

我的hr一直强调feedback 的 confidential，这是让我最郁闷的地方，都说g家慢，我一周就被拒了，8点还没醒，一个电话过来。。有点难以接受，也只能move on了。 anyway，大家加油！

p.s 本想面完缓几天发面经的，结果成了挂经，下次早发攒rp
p.p.s 如果有缘，最后一轮的国人小哥不知能否分享feedback



补充内容 (2016-2-10 08:52):
lz是1/28 周四面的

Aprilyn 发表于 2016-2-10 14:35
应该就是https://leetcode.com/problems/range-sum-query-2d-immutable/这个的变形~

楼主 还有一个疑问 求硬币组合数那道题，DP是怎么解的？
我这边只想到用数学方法解，就是处理有 重复数 的情况。

javaprogrammer 发表于 2016-2-10 10:32
第三轮第二题，是不是每个不同种类的硬币都要选取，比如{1,1,2,2,3} 组成的面额是 1+2+3，1+1+2+3, 1+1+2+2 ...

一起回复啦，第三题不是都要选取，是只要值不同就算，可选可不选，1，2，3也算的

第一题是这样的，10不会消耗cut的次数，20，一次cut产生两个，1：2的比例，30是2：3，所以有限选10，然后20，然后30这样，之后再考虑不是10的倍数的情况

第一题的做法

1. public class WoodcutII {
   
2.        
   
3.         public static void main(String[] args) {
   
4.                 int[] arr = {10, 15, 20, 25, 45};
   
5.                 System.out.println(getMaxLength(arr, 1));
   
6.                 System.out.println(getMaxLength(arr, 2));
   
7.                 System.out.println(getMaxLength(arr, 3));
   
8.                 System.out.println(getMaxLength(arr, 4));
   
9.                 System.out.println(getMaxLength(arr, 5));
   
10.         }
    
11.         public static int getMaxLength(int[] arr, int k) {
    
12.                 List<Integer> tens = new ArrayList<Integer>();
    
13.                 int others = 0;
    
14.                 for (int i : arr) {
    
15.                         if (i % 10 == 0) {
    
16.                                 tens.add(i);
    
17.                         } else {
    
18.                                 others++;
    
19.                         }
    
20.                 }
    
21.                 Collections.sort(tens);
    
22.                 int i = 0;
    
23.                 int res = 0;
    
24.                 while (k > 0 && i < tens.size()) {
    
25.                         int num = tens.get(i) / 10;
    
26.                         if (k >= num - 1) {
    
27.                                 res += num;
    
28.                                 k -= (num - 1);
    
29.                         } else {
    
30.                                 res += k;
    
31.                                 k = 0;
    
32.                         }
    
33.                         i++;
    
34.                 }
    
35.                 res += Math.min(k, others);
    
36.                
    
37.                 return res;
    
38.         }
    
39. }
    

复制代码

lz很厉害啊，为什么这样还会挂？

第一题greedy是不是把数组排序，从最大的开始算起，大概是这样？

1. public static int maxCut(int[] nums, int cutLimit) {
   
2.         if (nums == null || nums.length == 0 || cutLimit <= 0) return 0;
   
3.         Arrays.sort(nums);
   
4.         int maxCut = 0;
   
5.         for (int i = nums.length - 1; i >= 0; i--) {
   
6.             if (nums[i] >= 10) {
   
7.                 if (maxCut + nums[i] / 10 <= cutLimit) maxCut += nums[i] / 10;
   
8.                 else {
   
9.                     return cutLimit;
   
10.                 }
    
11.             }            
    
12.         }
    
13.         return maxCut;
    
14.     }

复制代码

第三轮第二题，是不是每个不同种类的硬币都要选取，比如{1,1,2,2,3} 组成的面额是 1+2+3，1+1+2+3, 1+1+2+2+3, 1+2+2+3？

Aprilyn 发表于 2016-2-10 10:48
一起回复啦，第三题不是都要选取，是只要值不同就算，可选可不选，1，2，3也算的

第一题是这样的，10 ...

谢谢lz的回复，第三轮第二题，如果按照我那样从大到小算的话，把30cut了两次，拿到3个10，但是如果从小到大的话，只需要cut一次20，就能拿到3个10了，不知道我理解的对不对？

javaprogrammer 发表于 2016-2-10 11:02
谢谢lz的回复，第三轮第二题，如果按照我那样从大到小算的话，把30cut了两次，拿到3个10，但是如果从小到 ...

嗯，是需要从小到大，因为cut小的输入输出比高一些，但是得先考虑10的倍数，因为比如15，cut 1次得1个10， 但是20 cut1次，得两个10。

楼主，第二轮第一题 和 第三轮第一题方便讲下吗？麻烦了~

好奇怪啊，lz面的这么好，为什么还会悲剧。。。 背景怎么样

Aprilyn 发表于 2016-2-10 11:06
嗯，是需要从小到大，因为cut小的输入输出比高一些，但是得先考虑10的倍数，因为比如15，cut 1次得1个10 ...

太感谢lz了，前两天看到地里的一个帖子说刚开始被google拒了，然后又有team要了他，lz可以去看看

lz水平很牛， 一定会有好的offer的，加油