楼主: superbeet
跳转到指定楼层
上一主题 下一主题
收起左侧

新鲜谷歌Onsite面经

🔗
火火火bit 2016-9-9 13:51:32 | 只看该作者
全局:
Josh 发表于 2016-9-9 12:59
记得之前面经见过一道题跟楼主第二题很像:给n堆硬币,每次只能从堆顶拿一枚,问拿k个硬币最大数额是多少。 ...

求解。。能想到用记忆化搜索来剪枝,但复杂度不会分析
回复

使用道具 举报

🔗
 楼主| superbeet 2016-9-9 13:59:55 | 只看该作者
全局:
Josh 发表于 2016-9-9 12:59
记得之前面经见过一道题跟楼主第二题很像:给n堆硬币,每次只能从堆顶拿一枚,问拿k个硬币最大数额是多少。 ...

在哪里看到的?
回复

使用道具 举报

🔗
daniel_hl 2016-9-9 14:47:40 | 只看该作者
全局:
diff那个是类似于edit distance吗
回复

使用道具 举报

🔗
william_gong 2016-9-9 21:17:42 | 只看该作者
回复

使用道具 举报

🔗
william_gong 2016-9-9 21:23:06 | 只看该作者
全局:
火火火bit 发表于 2016-9-9 13:51
求解。。能想到用记忆化搜索来剪枝,但复杂度不会分析

你的记忆化搜索打算纪录哪些状态呢?
回复

使用道具 举报

🔗
 楼主| superbeet 2016-9-10 00:29:26 | 只看该作者
全局:
有坛友了解碰到"面试官迟到很久面试很仓促"这种情况,应该怎么处理呢?
回复

使用道具 举报

🔗
zzgzzm 2016-9-10 05:42:15 | 只看该作者
全局:
mingzhou1987 发表于 2016-9-9 13:44
贪心应该不行吧,假设某个stack底有一个超大的数,顶端是一个超小的数,不是永远选不到这个。

你说的没错。关键是这个“使取出的值总和最大”怎么理解。因为STL API对于stack只提供查询top的值,在没有pop之前永远不知道地下的元素值。所以我对这道题的假设是提前不能知道除stack top之外的元素值。那么在没有额外信息的条件下就只有贪心算法了。
事实上,可以很容易举反例说明无论怎么pop都不可能保证取出的值总和最大。例如N=2,每个stack只有2个元素,所有top元素都是1, 但只有一个stack底的元素很大。理论上pop的最优方式是就pop光这个stack的2个元素,但初始状态下无法确定这个stack在array中的哪一个。
回复

使用道具 举报

🔗
zzgzzm 2016-9-10 05:45:00 | 只看该作者
全局:
楼主可以再具体澄清一下“N次操作后能拿到的数字和最大是多少” 是怎么定义的吗?在初始状态下我们是否可以知道每个stack中所有元素的值?还是只能通过stack::peek只知道顶端的值?
回复

使用道具 举报

🔗
南慕伦 2016-9-10 07:26:26 | 只看该作者
全局:
dp啦
dp[i][j]表示前i个栈取j个数字的最大值
显然dp[i][j] = max{dp[i-1][k] + sum[i][0..(j-k-1)]}
边界条件就是dp[0][j] = 0
回复

使用道具 举报

🔗
zzgzzm 2016-9-10 09:53:15 | 只看该作者
全局:
OK. I see. 用DP就相当于可以不断地用前i个stack用不同的pop方式来查看stack top下面的若干值,而且可以将pop出来的元素再push回去复原,之前计算dp[i][j]用的pop不计入最终的N次操着(这样的确是可以保证策划出最大总和的)。我以为是面对M个stack就一共只给N次pop的机会,一旦用过不可以后悔(这样是不可能0风险的)。如果的这样的话可以用array重新叙述题目更清楚:给一个vector<vector<int>> arr, 其中M = arr.size(), 但arr[i].size()对不同的i可以不同。要求取一个arr的二维总size为N的子集,限制每个arr[i]只能取连续的前几个(也允许根本不取)。 这样就明确说明所有arr中的元素是都可以预知的,个人感觉这样就比较明确。当然也许真正面试中可以真正澄清这些问题,呵呵,只是个人看法而已。
回复

使用道具 举报

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

本版积分规则

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