Google intern 面经

LZ, 除了出题之外，有问背景或者一些计算机基础知识吗？

补充内容 (2015-10-8 10:29):
还有，第二题和第三题需要写出代码来吗？感觉没啥可写的。。。

写了第一 第三题 有错误或者优化请指正

1. vector<int>plusone(vector<int> nums){
   
2. int k=checkvalid(nums);
   
3. if(k==-1) return vector<int>();
   
4. if(k==nums.size()) nums[k-1]=1;
   
5. else  if(nums[k]>0){
   
6.        for(int i=nums.size()-1;i!=k;i--){
   
7.         if(nums[i]==9)
   
8.                   nums[i]=0;
   
9.           else{nums[i]++;return nums;}
   
10.                           }
    
11.         if(nums[k]==9){
    
12.                       nums[k]=0;
    
13.                             if(k==0) nums.insert(nums.begin(),1);
    
14.                                 else nums[k-1]=1;
    
15.                                 }
    
16.            else {nums[k]++;}
    
17.                 }
    
18. 
    
19. else if(nums[k]<0){
    
20.                for(int i=nums.size()-1;i!=k;i--){
    
21.         if(nums[i]==0)        nums[i]=9;
    
22.           else{nums[i]--;return nums;}
    
23.                      }
    
24.         if(nums[k]==-1){nums[k]=0;
    
25.                                    if(k+1<nums.size())   nums[k+1]*=-1;
    
26.                                   }
    
27.            else  nums[k]++;
    
28. }
    
29. return nums;
    
30. }
    
31. 
    
32. int  checkvalid(vector<int> nums){  //检查有效性并返回首个不为0的数字位置
    
33. int k=0,len=nums.size();
    
34. while(k<len &&nums[k]==0)
    
35. k++;
    
36. 
    
37. for(int i=k+1;i<len;i++){
    
38. if(nums[i]<0) return -1;
    
39. }
    
40. return k;
    
41. 
    
42. }
    
43. 
    
44. 
    
45. 
    
46. 
    
47. //第三题  感觉这个ischange好蠢 求一个更好一点的算法
    
48. vector<int> randarray(vector<int> nums){
    
49. bool ischange=false;
    
50. int k=nums.size();
    
51. if(k<=1) return nums;
    
52. while(!ischange){
    
53. while(k>1){
    
54. int rand_num=rand()%k;
    
55. if(rand_num!=k-1) ischange=true;
    
56. swap(nums[rand_num],nums[k-1]);
    
57. k--;
    
58.    }}
    
59. return nums;
    
60. 
    
61. 
    
62. }

复制代码

补充内容 (2015-10-8 17:42):
第三题代码忘了一句srand((unsigned)time(0));

goo 发表于 2015-10-8 17:31
写了第一 第三题 有错误或者优化请指正

补充内容 (2015-10-8 17:42):

第三题为啥要判断某个位置上的数字是否改变？我觉得也可以没有和其他元素调换啊。

zxy_snow 发表于 2015-10-8 09:50
第三个题是要用洗牌算法么？还是随机生成排列？

就是随机生成排列，别想太复杂

xnature 发表于 2015-10-8 09:59
第三题像是随机生成permutation？

第四题是外排序？

可以这么理解吧，第四题的关键应该是mapreduce

mooc 发表于 2015-10-8 10:23
LZ, 除了出题之外，有问背景或者一些计算机基础知识吗？

补充内容 (2015-10-8 10:29):

就是做题，啥也没问，都要写代码，除了最后那个

lz，第二题改怎么做?

我也想问问，第二题怎么做的啊？

xnature 发表于 2015-10-9 02:45
第三题为啥要判断某个位置上的数字是否改变？我觉得也可以没有和其他元素调换啊。

我又看了一下我的代码 while循环这里的有问题
修改后

1. vector<int> randarray(vector<int> nums){
   
2. bool ischange=false;
   
3. int k=nums.size();
   
4. if(k<=1) return nums;
   
5. srand((unsigned)time(0));
   
6. while(!ischange){
   
7. k=nums.size();
   
8. while(k>1){
   
9. int rand_num=rand()%k;
   
10. if(rand_num!=k-1) ischange=true;
    
11. swap(nums[rand_num],nums[k-1]);
    
12. k--;
    
13.    }}
    
14. return nums;
    
15. 
    
16. 
    
17. }

复制代码

这个ischange的作用是确保新生成的序列与输入序列不一样(至少有一位改变过),如果题意允许这种情况,就可以去掉ischange了,这题目没说清,可加可不加

mooc 发表于 2015-10-13 23:14
lz，第二题改怎么做?

哦对， 忘了说query是要计算从1个点到另一个点组成的方阵的和