Google电话面试题目

谷歌的电话面试都是用Google Doc敲代码，题目本身不是很难，不过想敲出bug-free还是很难的。

直接上题目

A. 链表重组

有一个链表，里面用int 存放key，现在给定一个值 val，我们重组链表，小于val的节点放在前面。并且相对顺序不能变化

1. struct TreeNode{ 
2.     int value; 
3.     TreeNode *pNext; 
4. }; 
5.  
6. int ReconstructLinkedListByValue(TreeNode *head, int val){ 
7.     TreeNode *leftPart = NULL, *leftHead = NULL; 
8.     TreeNode *rightPart = NULL, *rightHead = NULL; 
9.      
10.     while(head){ 
11.         if(head->value > val){ 
12.             if(leftPart == NULL) leftHead = leftPart = head; 
13.             else{ 
14.                 leftPart->pNext = head; 
15.                 leftPart = head; 
16.             } 
17. } 
18.         else{ 
19.             if(rightPart == NULL) rightHead = rightPart= head; 
20.             else{ 
21.                 rightPart->pNext = head; 
22.                 rightPart= head; 
23.             } 
24.         } 
25.         head = head->pNext; 
26.     } 
27.     if(leftHead  == NULL){ 
28.         return rightHead; 
29.     } 
30.     else{ 
31.         leftPart.pNext = rightHead; 
32.         return leftHead; 
33.     } 
34. } 

B. 小朋友拿数据
有两个小朋友，玩一个游戏，游戏的内容是:

有一个数组，只有头和尾可以取数据，一次只能取得一个，谁拿到的数据和最大谁就赢了。

现在假设两个小孩都足够聪明。你能否求出第一个小孩，取得的和是多少

分析：

首先让我想到的是动态规划，然后试图给出公式。

不管哪个小孩，我们用dp[i][j]表示第一次拿可以拿到的最优解。

因为他只有两种选择 a[i] 或者 a[j]

如果他拿了a[i] 那么剩余数组是 a[i+1, j] 因为第二个小孩也足够聪明，他从这个数组先拿，也可以拿到他的最优解 dp[i+1][j]

那么当前这个小孩，只能拿到 a[i+1, j] 的数据和减去最优解。

所以dp公式如下

1. dp[i][j] = max(a[i] + sum(i+1, j) – dp[i+1][j],   
2.                       a[j] + sum(i, j-1) – dp[i][j-1]); 
3.  
4. 代码如下 
5. #define MAX_NUM 100  
6. int dp[MAX_NUM][MAX_NUM]; 
7.  
8. int GetSumArray(int nums[], int sum[], int n){ 
9.     sum[0] = nums[0]; 
10.     for(int i = 1; i < n; i++){ 
11.         sum[i] = nums[i] + sum[i-1]; 
12.     } 
13. } 
14.  
15.  
16. int GetMaxSelect(int nums[], int n){ 
17. int *sum = new int[n]; 
18.     GetSumArray(nums, sum, n); 
19.     int i,j, k; 
20.     for( i = 0; i < n; i++){ 
21.         dp[i][i] = nums[i]; 
22.     } 
23.     for( k = 1; k < n; k++){ 
24.         for( i = 0; i + k < n; i++){ 
25.             j = k + i; 
26.             dp[i][j] = max(nums[i] + (sum[j] –  sum[i+1]) – dp[i+1][j],   
27.                                           nums[j] + (sum[j-1] – sum[i]) – dp[i][j-1]); 
28. } 
29.     } 
30.  
31. delete[] sum; 
32. return dp[0][n-1]; 
33. }