📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 31
跳转到指定楼层
上一主题 下一主题
收起左侧

Google Onsite面经

全局:

2015(10-12月) 码农类General 硕士 全职@google - 内推 - Onsite  | | Other | 应届毕业生

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
First Round. Given k stack of coins, take n conins, what is the max sum of the n coins.
eg. stack1: 1, 4, 700, 3
        stack2: 5, 10, 6
        if n = 2, then the max sum should be 5+10
        if n =
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
tegers nums and a target, find the number of pair i, j satisfy the condition nums[i] + nums[j] < target.

Follow up: kSum Smaller

评分

参与人数 1大米 +60 收起 理由
虾米酱 + 60 感谢分享!

查看全部评分


上一篇:Google 家面试面经有多少作用?
下一篇:Amazon电面

本帖被以下淘专辑推荐:

推荐
lianlu 2015-11-10 08:33:55 | 只看该作者
全局:
hj867955629 发表于 2015-11-10 08:25
stack只是设置一个环境,告诉你只能依次读吧,也可以先把stack读到array里呀

我觉得这才是楼主的解法(二维dp)。
  1. public static int getmaxsum(int[][] nums, int k) {
  2.                 int[][] dp = new int[nums.length][k + 1];// the max sum using first i
  3.                                                                                                         // array, and j numbers
  4.                 for (int j = 0; j <= k; j++) {
  5.                         for (int i = 0; i < dp.length; i++) {
  6.                                 // dp[i][j] = max(dp[i-1][l] + sum{});
  7.                                 dp[i][j] = Math.max(i - 1 >= 0 ? dp[i - 1][j] : 0, j - 1 >= 0 ? dp[i][j - 1] : 0);
  8.                                 int len = nums[i].length;
  9.                                 int sum = 0;
  10.                                 for (int l = 0; j - l - 1 >= 0 && l < len; l++) {
  11.                                         sum += nums[i][l];
  12.                                         dp[i][j] = Math.max(dp[i][j], (i - 1 >= 0 ? dp[i - 1][j - l - 1] : 0) + sum);
  13.                                 }

  14.                         }
  15.                 }

  16.                 return dp[nums.length - 1][k];
  17.         }
复制代码
回复

使用道具 举报

推荐
wyjzhi89 2015-11-10 08:38:31 | 只看该作者
全局:
我觉得第一题可以先使用一个二维的数组存储起来的stack 从第0位到第i位的sum。 然后用dp[m][k] 代表从第一个stack到第m个stack 选择了k个元素的最大值。因为每个stack选择的都是最前端的元素,所以dp[m][k]=max(sum[j]+dp[m-1][k-j])( j from 0 to k ) .这样就可以求出来k个stack中的最大值。
回复

使用道具 举报

推荐
complete_46 2015-11-19 07:48:49 | 只看该作者
全局:
第一题:把所有stack里全pop到一个max heap里,再从max heap里pop出来n个数不就行了?
回复

使用道具 举报

🔗
guoqinlong 2015-11-10 00:11:41 | 只看该作者
全局:
楼主大神能说一下第一题的思路吗~~
回复

使用道具 举报

🔗
 楼主| zado 2015-11-10 00:41:29 | 只看该作者
全局:
cc11328 发表于 2015-11-10 00:09
问下楼主第一题 当n = 4的时候是最大是1+4+700+3 = 708 还是 1+4+700+5 = 710

710,因为可以从第二个stack里面选嘛
回复

使用道具 举报

🔗
 楼主| zado 2015-11-10 00:42:14 | 只看该作者
全局:
guoqinlong 发表于 2015-11-10 00:11
楼主大神能说一下第一题的思路吗~~

动态规划,二维数组,三重循环。我当时写得不是很好。
回复

使用道具 举报

🔗
litJordan 2015-11-10 05:41:56 | 只看该作者
全局:
楼主第二轮跟我店面问的一模一样哈!
回复

使用道具 举报

🔗
 楼主| zado 2015-11-10 05:45:00 | 只看该作者
全局:
ssross 发表于 2015-11-10 05:41
楼主第二轮跟我店面问的一模一样哈!

是个美国小哥问的?
回复

使用道具 举报

🔗
hj867955629 2015-11-10 05:59:59 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
winterOfChicago 2015-11-10 06:28:01 | 只看该作者
全局:
请教楼主 第一题k stacks怎么做的
回复

使用道具 举报

🔗
hj867955629 2015-11-10 06:29:19 | 只看该作者
全局:
之前代码有点问题,重新写了下https://github.com/hejian2356/-Algorithms/blob/master/GetMaxSumFromTwoStack.java
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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