一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 3714|回复: 26
收起左侧

谷歌店面面经

[复制链接] |试试Instant~ |关注本帖
ericshape123 发表于 2016-9-8 22:05:31 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x

发面经,攒人品。-google 1point3acres

开始就聊了快20分钟。之后给了道题:
.鐣欏璁哄潧-涓浜-涓夊垎鍦给一堆硬币list,里面是面值。AB俩人轮流投掷,正面A拿走,反面B拿走。然后算下A, B分别拿走多少钱。最后算下A, B拿走的钱Tie的概率。. visit 1point3acres.com for more.
是LC 39 组合和的变体. more info on 1point3acres.com

写出了DFS,但面试官最后说DP是优化解。

接着刷题刷题刷题~~~. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 402, 订阅: 28
domofeng 发表于 2016-9-14 04:32:34 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
感觉象个01背包问题, 写了一下, 不知道对不对, 请指正:

  1. public static double divideMoney(List<Integer> list){
  2.             if(list==null || list.size()==0) return 0.0;. more info on 1point3acres.com
  3. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4.             int sum=0;
  5.             for(int n : list) sum+=n;
  6.             .鐣欏璁哄潧-涓浜-涓夊垎鍦
  7.             return helperBack(list, sum/2)*1.0/Math.pow(2, list.size());
  8.         }
  9.         public static int helperBack(List<Integer> list, int target){
  10.                 int[] dp=new int[target+1];. From 1point 3acres bbs
  11.                 dp[0]=1;
  12.                 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  13.                 for(int i=0; i<list.size(); i++){
  14.                         for(int j=target; j>=1; j--){
  15.                                 if(j>=list.get(i)) dp[j]+=dp[j-list.get(i)];
  16.                         }
  17.                 }
  18.                 System.out.println("Tie: "+dp[target]);
  19.                 return dp[target];
  20.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

Josh 发表于 2016-9-9 00:26:59 | 显示全部楼层
关注一亩三分地微博:
Warald
想了下可以dp解,dp[i][j]就是前i个硬币A比B多j块钱的组合数。dp[I][j] = dp[i-1][j+coin[I]] + dp[i-1][j-coin[i]]
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-9 01:01:59 | 显示全部楼层
Josh 发表于 2016-9-9 00:26
想了下可以dp解,dp[j]就是前i个硬币A比B多j块钱的组合数。dp[j] = dp[j+coin] + dp[j-coin]

你这样的话 这个dp数组太大了吧。。 第二维的长度是所有币值的总和?
回复 支持 反对

使用道具 举报

phantom 发表于 2016-9-9 01:23:35 | 显示全部楼层
经典问题:subset sum
wikipedia

求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

xiayewang 发表于 2016-9-9 01:32:10 | 显示全部楼层
不知到这样可不可行。 硬币LIST的长度为N, 那么就设置dp数组的长度为1<<N.  下面是我的代码,方法比较笨,列举了每一种可能,没想到如何剪纸。

int total=0;
for(int I=0;i<list.length;I++){
   total+=list[I];
        for(int j=0;j<(1<<I);j++){
             dp[j*2]=dp[j];
             dp[j*2+1]=dp[j*2]+list[I];
        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
}
if(total%2==1). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    return 0;
int count=0;
for(int I=0;i<(1<<list.length);i++){
     if(dp[I]==total/2)
         count++; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}
return count/(1<<list.length);
. visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

phantom 发表于 2016-9-9 01:36:36 | 显示全部楼层
xiayewang 发表于 2016-9-9 01:32
不知到这样可不可行。 硬币LIST的长度为N, 那么就设置dp数组的长度为1

你这个不是指数复杂度么?DFS就是指数复杂度啊。。. 1point3acres.com/bbs
并没有提升时间复杂度。。用DP的意义就没有了
回复 支持 反对

使用道具 举报

xiayewang 发表于 2016-9-9 01:46:12 | 显示全部楼层
phantom 发表于 2016-9-9 01:36
你这个不是指数复杂度么?DFS就是指数复杂度啊。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
并没有提升时间复杂度。。用DP的意义就没有了
.1point3acres缃
恩 是的 谢谢大神指正!
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-9 02:08:10 | 显示全部楼层
phantom 发表于 2016-9-9 01:36. Waral 鍗氬鏈夋洿澶氭枃绔,
你这个不是指数复杂度么?DFS就是指数复杂度啊。。
并没有提升时间复杂度。。用DP的意义就没有了

这个题要是面值没特点的话,怎么着也得指数复杂度吧?
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-9 02:09:40 | 显示全部楼层
phantom 发表于 2016-9-9 01:36
你这个不是指数复杂度么?DFS就是指数复杂度啊。。
并没有提升时间复杂度。。用DP的意义就没有了

你能写个通用的dp解法大家参考参考吗?面值为任意正序列。
回复 支持 反对

使用道具 举报

phantom 发表于 2016-9-9 02:12:46 | 显示全部楼层
ytsr 发表于 2016-9-9 02:08
这个题要是面值没特点的话,怎么着也得指数复杂度吧?

https://en.wikipedia.org/wiki/Pa ... olynomial_algorithm

其实有点像背包的。
. more info on 1point3acres.comS : 面值数组
sum = sum(S)
DP [sum / 2][ S.size() ]
递推公式:. visit 1point3acres.com for more.
DP[k] : 表示用前i个数字,构造出sum = k的数量
DP[k] = DP[k][i-1]          不放入第 i 个数
               DP[k-S][i-1]    放入第 i 个数

复杂度 O(KN)
问题就是如果有某一个面值特别大。。时间复杂度很高

回复 支持 反对

使用道具 举报

Josh 发表于 2016-9-9 02:32:35 | 显示全部楼层
phantom 发表于 2016-9-9 02:12. from: 1point3acres.com/bbs
https://en.wikipedia.org/wiki/Partition_problem#The_pseudo-polynomial_algorithm

其实有点像背包 ...

这个跟我上面写的有点像,都是要sum长度的数组。求问这种解法最后的概率是dp[sum/2][n]/(2^n)?
回复 支持 反对

使用道具 举报

phantom 发表于 2016-9-9 02:34:00 | 显示全部楼层
Josh 发表于 2016-9-9 02:32
这个跟我上面写的有点像,都是要sum长度的数组。求问这种解法最后的概率是dp[sum/2][n]/(2^n)?

嗯。。是的啊。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
确实很像啊。。都需要sum长度的数组。。
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-9 02:37:39 | 显示全部楼层
能不能用类似coin change的dp解法来解?
.鏈枃鍘熷垱鑷1point3acres璁哄潧sort 数组以后
dp[i] 表示 i块钱可以有dp[i]种组合
回复 支持 反对

使用道具 举报

Josh 发表于 2016-9-9 02:42:34 | 显示全部楼层
william_gong 发表于 2016-9-9 02:37
能不能用类似coin change的dp解法来解?. From 1point 3acres bbs
sort 数组以后
dp 表示 i块钱可以有dp种组合
.鐣欏璁哄潧-涓浜-涓夊垎鍦
不一样,coin change里面硬币可以重复利用,这里硬币用完就没了。至少要二维数组吧,一个记录钱数,一个记录硬币数
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-9 02:43:14 | 显示全部楼层
Josh 发表于 2016-9-9 02:42
不一样,coin change里面硬币可以重复利用,这里硬币用完就没了。至少要二维数组吧,一个记录钱数,一个 ...

嗯对,确实是我欠考虑了
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-9 02:47:15 | 显示全部楼层
Josh 发表于 2016-9-9 02:42
不一样,coin change里面硬币可以重复利用,这里硬币用完就没了。至少要二维数组吧,一个记录钱数,一个 ...
-google 1point3acres
那用 Combination Sum IV 的思路呢?
回复 支持 反对

使用道具 举报

Josh 发表于 2016-9-9 02:57:48 | 显示全部楼层
william_gong 发表于 2016-9-9 02:47
那用 Combination Sum IV 的思路呢?

第一问是combination sum吧,第二问dp肯定更快,combination sum是O(2^n)
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-9 03:01:20 | 显示全部楼层
Josh 发表于 2016-9-9 02:57
第一问是combination sum吧,第二问dp肯定更快,combination sum是O(2^n)
.1point3acres缃
不是吧, Combination Sum IV是dp解的, 复杂度是n方, n为数组长度
回复 支持 反对

使用道具 举报

Josh 发表于 2016-9-9 03:08:42 | 显示全部楼层
william_gong 发表于 2016-9-9 03:01
不是吧, Combination Sum IV是dp解的, 复杂度是n方, n为数组长度

sorry理解错了,原来你指的是CombinationIV,那个题也是可以重复的,跟coin change是一样的
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-9 03:19:35 | 显示全部楼层
phantom 发表于 2016-9-9 02:12. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
https://en.wikipedia.org/wiki/Partition_problem#The_pseudo-polynomial_algorithm

其实有点像背包 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
赞!谢谢指点哇
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-30 16:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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