一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1619|回复: 7
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
dong882205 发表于 2015-11-21 00:29:20 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - Other - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
惨。。本来这学期没打算投任何简历,三周前突然被Google的一个校园recruiter联系,好不容易拖到昨天才电面,之前一直在好好刷题...可惜今早就通知跪了。. Waral 鍗氬鏈夋洿澶氭枃绔,

先是自我介绍,然后介绍一个项目,接着对方(估计是白人大叔,感觉并不友善) 介绍自己是什么network的一个senior manager没听清楚,然后开始做题。. more info on 1point3acres.com
整个面试音质都很差,我还能听到从他电话那头传来的我自己的声音+他同事的说笑声+各种杂音,我说话他也没怎么搭理,额...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
题目是这样的,输入是一个int amount 和 vector<int> coins,分别表示总货币量、各个coin的价值量,要求以最少的coin个数凑齐总货币量。 (大家应该都熟悉吧?入门级的DP题目。。)
然后输出的是每种货币的数目,vector<int> nums。
举例:  amount  = 40, coins = [1,5,15,25],输出[0,1,1,1]
再举例: amount  = 40, coins = [1,5,20,25],输出[0,0,2,0]

关键是刚开始没怎么听清楚,问了好几遍才确认,自己也是太紧张了。然后先确认了几个细节要求:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
都是整数?是的.鏈枃鍘熷垱鑷1point3acres璁哄潧
最后是要凑齐exact的目标数值amount?是的
会有无解的情况吗?默认总会有价值为“1”的coin

我刚开始想着用backtracking+贪心来做,先sort,再用最贵的coin开始凑,后来一想不对,应该bottom up用dp,转移方程就是dp = min(dp[i-1]+1, dp[i-coins[j]]+j) for all j from 1~coins.size()-1;

然后写着写着就迷糊了,忘记目标不是coin的总数而是每个coin的个数。。。事实上,我写完之后(当时是只记录dp,即总数),他说yes I think this works. 然后follow up问如果amount很大怎么办。
我想着想着发现只要keep tracking dp 里后面 coins.size() 数量的dp即可,only store the dp, dp[i-coins[1]]....., dp[i-coins[coins.size()-1]]
他说好的,很好,又问了总体的时间空间复杂度。(好了到目前为止我们两个估计都忘记了刚开始要的是各个coin的个数。。。)

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

然后随便聊了一分钟就结束了。
然后今早recruiter打电话来说unfortunately blabla...一年冷冻期blabla。。. Waral 鍗氬鏈夋洿澶氭枃绔,
谢谢观赏。。。我刷题去了。。

评分

1

查看全部评分

jmnjmnjmn 发表于 2015-11-22 06:05:33 | 显示全部楼层
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;  
                }  
            }  
        } . from: 1point3acres.com/bbs
          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]
. from: 1point3acres.com/bbs
回复 支持 1 反对 0

使用道具 举报

haifengc 发表于 2015-11-21 01:01:14 | 显示全部楼层
为什麽还打电话,不直接发邮件说呢,
回复 支持 反对

使用道具 举报

354886 发表于 2015-11-21 01:30:31 | 显示全部楼层
能问下lz一年冷冻期是怎么说的?明确告诉你一年内绝对不能投?
回复 支持 反对

使用道具 举报

Toby 发表于 2015-11-21 01:50:58 | 显示全部楼层
一年冷冻期。。。我擦
回复 支持 反对

使用道具 举报

 楼主| dong882205 发表于 2015-11-21 04:42:40 | 显示全部楼层
354886 发表于 2015-11-21 01:30
能问下lz一年冷冻期是怎么说的?明确告诉你一年内绝对不能投?

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

使用道具 举报

bobzhang2004 发表于 2015-12-5 01:06:18 | 显示全部楼层
jmnjmnjmn 发表于 2015-11-22 06:05.1point3acres缃
private void solution(int[] coins,int amount, int[] result){  
        int[] dp = new int[amount+1] ...
. From 1point 3acres bbs
你这个code有bug啊,result的length应该是和coins的length是一样的,code中sol的size和result一样,那就不是sol[i-1]了,另外,最后的for循环,一个一个的加不行吧,因为有些amount是不需去拿coin去组成的吧?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-5 01:28:50 | 显示全部楼层
写了下coin的代码,感觉空间复杂度可以降低。欢迎指教. from: 1point3acres.com/bbs
  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);
    .1point3acres缃
  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++) {. 1point3acres.com/bbs
  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. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 22:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表