Google on campus

两轮连续45分钟。

第一轮：
1. 一串数，例如 10， 20，30，40，20，50，25. 两个玩家，只能选最左或最右，轮流选，怎样max你的和。举出贪心反例。用max-m

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

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

补充内容 (2014-11-1 03:02):
第一题DP解法：

第一题比较容易：

1. public class MaxGame {
   
2.         public static int maxGame(int[] arr) {
   
3.                 if(arr == null || arr.length == 0)        return 0;
   
4.                 int len = arr.length;
   
5.                
   
6.                 //calculate the sum from index i to index j
   
7.                 //dynamic programming method
   
8.                 int[][] segSum = new int[len][len];
   
9.                 for(int i = 0; i < len; ++i)        segSum[i][i] = arr[i];
   
10.                 for(int i = 0; i < len; ++i) {                       
    
11.                         for(int j = i + 1; j < len; ++j) {                               
    
12.                                 segSum[i][j] = (segSum[i][j - 1] + arr[j]);
    
13.                         }
    
14.                 }
    
15.                
    
16.                 //dynamic programming method to find the max picks
    
17.                 int[][] maxPick = new int[len][len];
    
18.                 for(int i = 0; i < len; ++i)                maxPick[i][i] = arr[i];
    
19.                 for(int i = len - 2; i >= 0; --i) {
    
20.                         for(int j = i + 1; j < len; ++j) {
    
21.                                 maxPick[i][j] = Math.max(arr[i] + segSum[i + 1][j] - maxPick[i + 1][j],
    
22.                                                                              arr[j] + segSum[i][j - 1] - maxPick[i][j - 1]);
    
23.                         }
    
24.                 }               
    
25.                 return maxPick[0][len - 1];
    
26.         }
    
27.        
    
28.         public static void main(String[] args) {
    
29.                 int[] arr = new int[] {1, 2, 2, 3, 2,1};
    
30.                 System.out.println(maxGame(arr));
    
31.         }
    
32. }

复制代码

王可雪 发表于 2014-11-4 14:47
没考虑太多cases，不一定对。不过倒是提醒我了，对付游戏minimax是比较常用的思路。为了感谢lz分享面经， ...

上面的代码有点错误。

1. #include <iostream>
   
2. #include <assert.h>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. int coinGame(int array[], int n) {
   
7.         assert(n > 0);
   
8.         if (n == 1)
   
9.                 return array[0];
   
10.         int start = 0;
    
11.         int end = n - 1;
    
12.         int sum = 0;
    
13.         for (; start < end;) {
    
14.                 if (end - start == 1) {
    
15.                         sum += max(array[start], array[end]);
    
16.                         break;
    
17.                 }
    
18.                 else if (end - start == 2) {
    
19.                         sum += max(array[start], array[end]) + array[start+1];
    
20.                         break;
    
21.                 }
    
22.                 else {
    
23.                         //cout << array[end] - array[end-1] << endl;
    
24.                         sum += (min(array[start] - array[start+1], array[start]-array[end]) >
    
25.                                 min(array[end] - array[end-1], array[end]-array[start]))
    
26.                                 ? array[start++] : array[end--];
    
27.                         //cout << end << endl;
    
28.                         min(array[start] - array[start+1], array[start]-array[end]) >
    
29.                         min(array[end] - array[end-1], array[end]-array[start]) ? start++ : end--;
    
30.                         //cout << end << endl;               
    
31.                 }
    
32.         }
    
33.         return sum;
    
34. }
    
35. 
    
36. int main() {
    
37.         int test1[] = {50, 100, 1000, 49};
    
38.         int test2[] = {50, 100, 1, 49};
    
39.         cout << coinGame(test1, 4) << endl;
    
40.         cout << coinGame(test2, 4) << endl;
    
41. 
    
42. }

复制代码

22691482 发表于 2014-11-4 11:20
思路是这样。。问题是怎么写出可以跑的代码。。

没考虑太多cases，不一定对。不过倒是提醒我了，对付游戏minimax是比较常用的思路。为了感谢lz分享面经，我贴一下我的代码，要是有没考虑到的，欢迎大家指正。

1. #include <iostream>
   
2. #include <assert.h>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. int coinGame(int array[], int n) {
   
7.         assert(n > 0);
   
8.         if (n == 1)
   
9.                 return array[0];
   
10.         int start = 0;
    
11.         int end = n - 1;
    
12.         int sum = 0;
    
13.         for (; start < end; start++, end--) {
    
14.                 if (end - start == 1)
    
15.                         sum += max(array[start], array[end]);
    
16.                 else if (end - start == 2) {
    
17.                         sum += max(array[start], array[end]) + array[start+1];
    
18.                         break;
    
19.                 }
    
20.                 else {
    
21.                         sum += (min(array[start] - array[start+1], array[start]-array[end]),
    
22.                                 min(array[end] - array[end-1], array[end]-array[start]))
    
23.                                 ? array[start] : array[end];
    
24.                 }
    
25.         }
    
26.         return sum;
    
27. }
    
28. 
    
29. int main() {
    
30.         int test1[] = {50, 100, 1, 49};
    
31.         cout << coinGame(test1, 4) << endl;
    
32. }

复制代码

补充内容 (2014-11-4 14:48):
我这里assume的永远玩家先手

reverse linked list里的一次 K 个是啥意思？

pf22099 发表于 2014-10-31 02:43
reverse linked list里的一次 K 个是啥意思？

Leetcode那个。。

22691482 发表于 2014-10-30 11:04
Leetcode那个。。

噢···了然了然，多谢！

pf22099 发表于 2014-10-31 03:05
噢···了然了然，多谢！

校友你好 ！！　哈哈

22691482 发表于 2014-10-30 12:05
校友你好 ！！　哈哈

哈哈，Trojans遍天下啊

请问楼主能否说一下randomNumber那个题的做法？

忽而今夏 发表于 2014-10-31 12:25
请问楼主能否说一下randomNumber那个题的做法？

说来话长啊。。。主要是跟面试官聊，一步步的改进时间和空间。。更注重过程吧。

averillzheng 发表于 2014-11-4 03:15
第一题比较容易：

你好，，请问代码里面的segsum是干嘛的？