新鲜谷歌Onsite面经

年初时候面过一次Google，一共五轮有一轮代码没写完挂了。不过可能平均成绩差的不远，这次的Recruite

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

到的数字和最大是多少。

大家好运~ 攒人品，求offer~

第二轮题目不是很清楚楼主的意思，现在假设是说给定一个vector<stack<int>>类型的arr, 并且M=arr.size(), 求N次pop操作可以取出的最大值。因为在没有pop之前是不可能知道stack除了顶端之外的值，所以这道题我觉得应该问得更具体一些，就是问用贪心算法每次pop arr 中最大栈顶，然后N次这样后的操作所取的值总和。否则任何方式都无法保证一定取值总和最大。
如果是贪心算法，建一个max heap, 元素为pair<int,int>, 其中first是栈顶值，second 是该栈在arr 中的指标，按first 丛小到大定义heap 的排序。每次pop heap取当前最大值，并用pair second 判断该栈是否在arr 中已空，若未空，pop该栈顶并push 到heap 中。重复该操作N次或heap为空，whichever comes first. 该题和Leetcode 中tweeter design 的设计get most recent 10 tweets from self and followees 是一样的算法。

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中的元素是都可以预知的，个人感觉这样就比较明确。当然也许真正面试中可以真正澄清这些问题，呵呵，只是个人看法而已。

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中的哪一个。

请问啥叫代码比较器？谢谢

bless LZ. 请问一组array有M个stack，意思是array 的element都是stack吗？还是啥意思？多谢

william_gong 发表于 2016-9-9 10:48
请问啥叫代码比较器？谢谢

可能是指git diff之类的功能

请问N次操作是pop n次吗

houqingniao 发表于 2016-9-9 10:55
bless LZ. 请问一组array有M个stack，意思是array 的element都是stack吗？还是啥意思？多谢

类似git diff

火火火bit 发表于 2016-9-9 11:37
请问N次操作是pop n次吗

对，进行N次pop操作后。

记得之前面经见过一道题跟楼主第二题很像：给n堆硬币，每次只能从堆顶拿一枚，问拿k个硬币最大数额是多少。应该是dp解。

贪心应该不行吧，假设某个stack底有一个超大的数，顶端是一个超小的数，不是永远选不到这个。