Google Onsite面经

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 = 3, then the max sum should be 1+4+700

Second Round. Array Longe

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

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

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.                 }
    
17. 
    
18.                 return dp[nums.length - 1][k];
    
19.         }
    

复制代码

我觉得第一题可以先使用一个二维的数组存储起来的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中的最大值。

第一题：把所有stack里全pop到一个max heap里，再从max heap里pop出来n个数不就行了？

楼主大神能说一下第一题的思路吗～～

cc11328 发表于 2015-11-10 00:09
问下楼主第一题 当n = 4的时候是最大是1+4+700+3 = 708 还是 1+4+700+5 = 710

710，因为可以从第二个stack里面选嘛

guoqinlong 发表于 2015-11-10 00:11
楼主大神能说一下第一题的思路吗～～

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

楼主第二轮跟我店面问的一模一样哈！

ssross 发表于 2015-11-10 05:41
楼主第二轮跟我店面问的一模一样哈！

是个美国小哥问的？

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

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

请教楼主 第一题k stacks怎么做的

之前代码有点问题，重新写了下https://github.com/hejian2356/-Algorithms/blob/master/GetMaxSumFromTwoStack.java