我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
查看: 2486|回复: 7
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
dong882205 发表于 2015-11-21 00:29:20 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

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

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

题目是这样的,输入是一个int amount 和 vector<int> coins,分别表示总货币量、各个coin的价值量,要求以最少的coin个数凑齐总货币量。 (大家应该都熟悉吧?入门级的DP题目。。). visit 1point3acres for more.
然后输出的是每种货币的数目,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]

关键是刚开始没怎么听清楚,问了好几遍才确认,自己也是太紧张了。然后先确认了几个细节要求:
都是整数?是的
最后是要凑齐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;
. from: 1point3acres
然后写着写着就迷糊了,忘记目标不是coin的总数而是每个coin的个数。。。事实上,我写完之后(当时是只记录dp,即总数),他说yes I think this works. 然后follow up问如果amount很大怎么办。.本文原创自1point3acres论坛
我想着想着发现只要keep tracking dp 里后面 coins.size() 数量的dp即可,only store the dp, dp[i-coins[1]]....., dp[i-coins[coins.size()-1]]
他说好的,很好,又问了总体的时间空间复杂度。(好了到目前为止我们两个估计都忘记了刚开始要的是各个coin的个数。。。)
.1point3acres网
然后闲聊了几句,他突然问我,噢等一下,我们要求的不是总数。。。我就突然紧张了,想了一会后,在每个dp的循环里加了个stack用来记录插入过的coin index,如果dp更新的话就把前面
的那个pop出来回滚回去,再把新的弄进来,感觉好像可以。。。

然后随便聊了一分钟就结束了。. 1point 3acres 论坛
然后今早recruiter打电话来说unfortunately blabla...一年冷冻期blabla。。. 围观我们@1point 3 acres
谢谢观赏。。。我刷题去了。。

评分

1

查看全部评分


上一篇:TripAdvisor on-campus + onsite面经
下一篇:A家OA1面经 (11.20 Due)
我的人缘0
jmnjmnjmn 发表于 2015-11-22 06:05:33 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
private void solution(int[] coins,int amount, int[] result){  
. 1point3acres        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++){  -google 1point3acres
                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]

回复 支持 1 反对 0

使用道具 举报

我的人缘0
haifengc 发表于 2015-11-21 01:01:14 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
为什麽还打电话,不直接发邮件说呢,
回复 支持 反对

使用道具 举报

我的人缘0
354886 发表于 2015-11-21 01:30:31 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
能问下lz一年冷冻期是怎么说的?明确告诉你一年内绝对不能投?
回复 支持 反对

使用道具 举报

我的人缘0
Toby 发表于 2015-11-21 01:50:58 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
一年冷冻期。。。我擦
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| dong882205 发表于 2015-11-21 04:42:40 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
354886 发表于 2015-11-21 01:30
能问下lz一年冷冻期是怎么说的?明确告诉你一年内绝对不能投?

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

使用道具 举报

我的人缘0
bobzhang2004 发表于 2015-12-5 01:06:18 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
jmnjmnjmn 发表于 2015-11-22 06:05. 留学申请论坛-一亩三分地
private void solution(int[] coins,int amount, int[] result){  
        int[] dp = new int[amount+1] ...
-google 1point3acres
你这个code有bug啊,result的length应该是和coins的length是一样的,code中sol的size和result一样,那就不是sol[i-1]了,另外,最后的for循环,一个一个的加不行吧,因为有些amount是不需去拿coin去组成的吧?
回复 支持 反对

使用道具 举报

我的人缘0
bobzhang2004 发表于 2015-12-5 01:28:50 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
写了下coin的代码,感觉空间复杂度可以降低。欢迎指教
  1. public class CoinChange {

  2.         public static void main(String[] args) {
  3.                 int[] coins = {1, 5, 15, 25};
  4.                 int[] res = changeCoin(40, coins);
  5.                 for (int i : res) {
  6.                         System.out.println(i);. 一亩-三分-地,独家发布
  7.                 }
  8.         }
  9.         . 牛人云集,一亩三分地
  10.         public static int[] changeCoin(int amount, int[] coins) {
  11.                 if (coins == null || coins.length == 0) {
  12.                         return null;
  13.                 }. From 1point 3acres bbs
  14.                 HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
  15.                 int[] dp = new int[amount + 1];
  16.                 Arrays.fill(dp, Integer.MAX_VALUE);
  17.                 dp[0] = 0;
  18.                 map.put(0, new ArrayList<Integer>());
  19.                 for (int i = 1; i <= amount; i++) {
  20.                         for (int j = 0; j < coins.length; j++) {. 1point 3acres 论坛
  21.                                 if (coins[j] <= i && dp[i - coins[j]] != Integer.MAX_VALUE && dp[i - coins[j]] + 1 < dp[i]) {
  22.                                         dp[i] = dp[i - coins[j]] + 1;
  23.                                         map.put(i, new ArrayList<Integer>(map.get(i - coins[j])));
  24.                                         map.get(i).add(coins[j]);
  25.                                 }. visit 1point3acres for more.
  26.                         }
  27.                 }
  28.                 int[] res = new int[coins.length];
  29.                 HashMap<Integer, Integer> coinsMap = new HashMap<Integer, Integer>();. From 1point 3acres bbs
  30.                 for (int i = 0; i < coins.length; i++) {
  31.                         coinsMap.put(coins[i], i);
  32.                 }
  33.                 for (int i : map.get(amount)) {
  34.                         res[coinsMap.get(i)]++;.本文原创自1point3acres论坛
  35.                 }
  36.                 return res;. 一亩-三分-地,独家发布
  37.         }
  38. }.留学论坛-一亩-三分地
复制代码
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-28 09:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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