一亩三分地论坛

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

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

谷歌店面面经

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

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

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

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

x

发面经,攒人品。

开始就聊了快20分钟。之后给了道题:
给一堆硬币list,里面是面值。AB俩人轮流投掷,正面A拿走,反面B拿走。然后算下A, B分别拿走多少钱。最后算下A, B拿走的钱Tie的概率。. 1point3acres.com/bbs
是LC 39 组合和的变体

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

接着刷题刷题刷题~~~

评分

1

查看全部评分

domofeng 发表于 2016-9-14 04:32:34 | 显示全部楼层
感觉象个01背包问题, 写了一下, 不知道对不对, 请指正:
. more info on 1point3acres.com
  1. public static double divideMoney(List<Integer> list){
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  2.             if(list==null || list.size()==0) return 0.0;

  3.             int sum=0;
  4.             for(int n : list) sum+=n;
  5.             
  6.             return helperBack(list, sum/2)*1.0/Math.pow(2, list.size());. 鍥磋鎴戜滑@1point 3 acres
  7.         }
  8.         public static int helperBack(List<Integer> list, int target){
  9.                 int[] dp=new int[target+1];
  10.                 dp[0]=1;
  11.                
  12.                 for(int i=0; i<list.size(); i++){
  13.                         for(int j=target; j>=1; j--){
  14.                                 if(j>=list.get(i)) dp[j]+=dp[j-list.get(i)];
  15.                         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  16.                 }
  17.                 System.out.println("Tie: "+dp[target]);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  18.                 return dp[target];
  19.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

Josh 发表于 2016-9-9 00:26:59 | 显示全部楼层
想了下可以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

回复 支持 反对

使用道具 举报

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++){. from: 1point3acres.com/bbs
             dp[j*2]=dp[j];
             dp[j*2+1]=dp[j*2]+list[I];
        }
} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
if(total%2==1)
    return 0;
int count=0;
for(int I=0;i<(1<<list.length);i++){
     if(dp[I]==total/2)-google 1point3acres
         count++;
}
return count/(1<<list.length);

回复 支持 反对

使用道具 举报

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

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

使用道具 举报

xiayewang 发表于 2016-9-9 01:46:12 | 显示全部楼层
phantom 发表于 2016-9-9 01:36
你这个不是指数复杂度么?DFS就是指数复杂度啊。。. more info on 1point3acres.com
并没有提升时间复杂度。。用DP的意义就没有了

恩 是的 谢谢大神指正!
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-9 02:08:10 | 显示全部楼层
phantom 发表于 2016-9-9 01:36
你这个不是指数复杂度么?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
. 鍥磋鎴戜滑@1point 3 acres
其实有点像背包的。
S : 面值数组
sum = sum(S)
DP [sum / 2][ S.size() ]. from: 1point3acres.com/bbs
递推公式:
DP[k] : 表示用前i个数字,构造出sum = k的数量
DP[k] = DP[k][i-1]          不放入第 i 个数
               DP[k-S][i-1]    放入第 i 个数

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

. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

Josh 发表于 2016-9-9 02:32:35 | 显示全部楼层
phantom 发表于 2016-9-9 02:12
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解法来解?
sort 数组以后
dp[i] 表示 i块钱可以有dp[i]种组合
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

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

那用 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)

不是吧, 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.1point3acres缃
https://en.wikipedia.org/wiki/Partition_problem#The_pseudo-polynomial_algorithm

其实有点像背包 ...
.1point3acres缃
赞!谢谢指点哇
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 18:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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