Google onsite 面经

Aprilyn 发表于 2016-2-11 02:18
囧，本来都在打字的，发现自己原来的想法不是那么对，面试官还说没更好的解了。。突然坦然了，估计面试官 ...

lz 可以用dfs(power set)来算，然后用set dedup吗？

guixi107 发表于 2016-2-11 02:44
lz 可以用dfs(power set)来算，然后用set dedup吗？

嗯呐，我一开始就说了dfs的解法，也说了关于硬币币值重复，需要剪枝的优化. 被继续追问了。

看花那个问题，先想成一维的。二维差不多就是4个一维的问题吧

第一题cut, 能不能用k-select做。就是大小比较定义按照楼主给的比例来定义。这样应该可以O(n)。不知道楼主的Greedy是怎么做的。

Aprilyn 发表于 2016-2-10 13:21
假设有四个点：
A B
C D 的值为：

如果B是statue,C和A是空地或者花的话，就不能这么算了。或者记录的值不考虑自己的状态，在考虑下一个值的时候再考虑这个值的状态？

楼主，这题能不能用四个matrix啊，分别存放从左到右，从右到左，从上倒下，从下到上的连续非2的sum， up to an index
这样是不是会被面试官k死。。。

感觉楼主面的很好啊，思路基本都是对的，为什么会挂呢

coin change,

1. public class CoinsChange {
   
2.         public static void main(String[] args) {
   
3.                 int[] arr = {5, 5, 10, 10, 20, 20};
   
4.                 System.out.println(getCoinsChangeWays(arr, 40));
   
5.         }
   
6.        
   
7.         public static int getCoinsChangeWays(int[] arr, int k) {
   
8.                 if (arr == null || arr.length == 0) {
   
9.                         return 0;
   
10.                 }
    
11.                 int[] dp = new int[k + 1];
    
12.                 dp[0] = 1;
    
13.                 for (int i = 0; i < arr.length; i++) {
    
14.                         for (int j = k; j > 0; j--) {
    
15.                                 if (j - arr[i] >= 0) {
    
16.                                         dp[j] += dp[j - arr[i]];
    
17.                                 }
    
18.                         }
    
19.                 }
    
20.                
    
21.                 return dp[k];
    
22.         }
    
23. }

复制代码

第一题的做法

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

复制代码

yanggao1119 发表于 2016-2-26 02:10
楼主，这题能不能用四个matrix啊，分别存放从左到右，从右到左，从上倒下，从下到上的连续非2的sum， up to ...

所以最好就是一个~