Google Onsite面经

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

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

lianlu 发表于 2015-11-10 07:28
怎么由two array推广到k stacks? 是先全部读出来存在array里了？

stack只是设置一个环境，告诉你只能依次读吧，也可以先把stack读到array里呀

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中的最大值。

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

lianlu 发表于 2015-11-10 08:33
我觉得这才是楼主的解法（二维dp）。

你这个确实更好啦，学习了

补充内容 (2015-11-10 08:48):
请问怎么贴代码贴成你这样的？

楼主能把这个问题仔细讲讲吗？What if the two array are very large (10TB). A - MergeSort。是说把两个array分别external sort之后再一段一段load进内存比较？谢啦

zado 发表于 2015-11-10 05:45
是个美国小哥问的？

是的哈！听声音像个白人小哥！应该是同一个人！风格一模一样！

2Sum smaller的思路是什么？我现在想到的方法是sort。有O（n）的解法么？

maomaoxiong 发表于 2015-11-10 13:41
2Sum smaller的思路是什么？我现在想到的方法是sort。有O（n）的解法么？

就是leetcode 3sum smaller的变形，先sort array，然后左右两个指针往中间走。