新鲜 Google 电面，SDE Full Time，已通知跪了..

惨。。本来这学期没打算投任何简历，三周前突然被Google的一个校园recruiter联系，好不容易拖到昨天才电面，之前一直在好好刷题...可惜今早就通知跪了。

先是自我介绍，然后介绍一个项目，接着对方(估计是白人大叔，感觉并不友善) 介绍自己是什么network的一个senior manager没听清楚，然后开始做题。
整个面试音质都很差，我还能听到从他电话那头传来的我自己的声音+他同事的说笑声+各种杂音，我说话他也没怎么搭理，额...

题目是这样的，输入是一个int amount 和 vector<int> coins，分别表示总货币量、各个coin的价值量，要求以最少的coin个数凑齐总货币量。 （大家应该都熟悉吧？入门级的DP题目。。）
然后输出的是每种货币的数目，vector<int> nums。
举例：  amount  = 40, coins = [1,

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

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

了几句，他突然问我，噢等一下，我们要求的不是总数。。。我就突然紧张了，想了一会后，在每个dp[i]的循环里加了个stack用来记录插入过的coin index，如果dp[i]更新的话就把前面
的那个pop出来回滚回去，再把新的弄进来，感觉好像可以。。。

然后随便聊了一分钟就结束了。
然后今早recruiter打电话来说unfortunately blabla...一年冷冻期blabla。。
谢谢观赏。。。我刷题去了。。

private void solution(int[] coins,int amount, int[] result){  
        int[] dp = new int[amount+1];
        int[] sol = new int[result.size()];
        dp[0]=0;  
        for(int i=1;i<=amount;i++) dp[i]=Integer.MAX_VALUE;  
        for(int i=1;i<=amount;i++){  
            for(int j=0;j<coins.length;j++){  
                if(coins[j]<=i&&dp[i]>dp[i-coins[j]]+1){  
                    dp[i]=dp[i-coins[j]]+1;  
                    sol[i-1]=j;  
                }  
            }  
        }
          for(int i=1;i<=amount;i++){  
             result[solu[i-1]]++;
        }
    }  


AMOUNT很大的时候，可以优化DP空间，如果coins的面额最小m，最大n， 开一个长度为 L = n-m+1 的int[] dp,然后每次调用的时候相应的变成dp[i%L]跟dp[(i-coins[j])%L]

为什麽还打电话，不直接发邮件说呢，

能问下lz一年冷冻期是怎么说的？明确告诉你一年内绝对不能投？

一年冷冻期。。。我擦

354886 发表于 2015-11-21 01:30
能问下lz一年冷冻期是怎么说的？明确告诉你一年内绝对不能投？

recruiter倒是没有细说额，原话大概是“很不幸我们不能继续下去，但是这并不代表你不够好，我们鼓励你一年后再次尝试谷歌，一年的工作经验会让你进步很多，要知道我们谷歌40%的员工并不是第一次面试就能进来的” 额。。。

jmnjmnjmn 发表于 2015-11-22 06:05
private void solution(int[] coins,int amount, int[] result){  
        int[] dp = new int[amount+1] ...

你这个code有bug啊，result的length应该是和coins的length是一样的，code中sol的size和result一样，那就不是sol[i-1]了，另外，最后的for循环，一个一个的加不行吧，因为有些amount是不需去拿coin去组成的吧？

写了下coin的代码，感觉空间复杂度可以降低。欢迎指教

1. public class CoinChange {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[] coins = {1, 5, 15, 25};
   
5.                 int[] res = changeCoin(40, coins);
   
6.                 for (int i : res) {
   
7.                         System.out.println(i);
   
8.                 }
   
9.         }
   
10.        
    
11.         public static int[] changeCoin(int amount, int[] coins) {
    
12.                 if (coins == null || coins.length == 0) {
    
13.                         return null;
    
14.                 }
    
15.                 HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
    
16.                 int[] dp = new int[amount + 1];
    
17.                 Arrays.fill(dp, Integer.MAX_VALUE);
    
18.                 dp[0] = 0;
    
19.                 map.put(0, new ArrayList<Integer>());
    
20.                 for (int i = 1; i <= amount; i++) {
    
21.                         for (int j = 0; j < coins.length; j++) {
    
22.                                 if (coins[j] <= i && dp[i - coins[j]] != Integer.MAX_VALUE && dp[i - coins[j]] + 1 < dp[i]) {
    
23.                                         dp[i] = dp[i - coins[j]] + 1;
    
24.                                         map.put(i, new ArrayList<Integer>(map.get(i - coins[j])));
    
25.                                         map.get(i).add(coins[j]);
    
26.                                 }
    
27.                         }
    
28.                 }
    
29.                 int[] res = new int[coins.length];
    
30.                 HashMap<Integer, Integer> coinsMap = new HashMap<Integer, Integer>();
    
31.                 for (int i = 0; i < coins.length; i++) {
    
32.                         coinsMap.put(coins[i], i);
    
33.                 }
    
34.                 for (int i : map.get(amount)) {
    
35.                         res[coinsMap.get(i)]++;
    
36.                 }
    
37.                 return res;
    
38.         }
    
39. }
    

复制代码