金山(Kingsoft)服务器端开发工程师笔试题和面试题答案

思而思学网

总体感觉金山的笔试题难度还可以,既考查了基础知识,又测试了考生的编程及算法能力。试题大概分为三部分,第一部分是一些简单的看程序填空,就是填写程序的运行结果。这一部分只要仔细一点就没什么问题。第二部分是简答题,内容包括TCP,UDP协议,C++拷贝构造函数,快速排序算法,堆栈等基础知识,这一部分问题也不大。最后一部分是两道编程题,由于时间很充裕(两个小时)如果能想出算法的话应该很快就做完了。这里与大家分享一道编程题,主要考查算法。

题目1:有一个int型数组Num,里面存放着若干的正数和负数,请你设计一个算法,在数组中截取一段Num[start]--Num[end],使得这一段的整数之和最大,并返回最大值max。

算法思想:start和end记录最大段的起始和终止位置,首先让start指向数组的第一个正数的下标,end指向数组的倒数第一个正数的下标,即略去数组首尾的负数。然后用两个循环求出所有组合的最大值并返回,start记录最大段的起始下标,end记录终止下标。

以下是我用C语言实现的程序代码,已经在visual C++ 6.0上运行通过了,想加入金山的可以过来围观一下,呵呵。

#include /在数组Num[]中截取一段Num[start]--Num[end],使得这一段的元素之和最大,打印start和end并返回最大值max/ int findMaxPart(int Num[],int n) { int len=n;//数组的长度 int start=0; int end=len-1; int sum=0; int max=0;//截取数组段的最大值 /略去数组首尾的负数/ while(Num[start]<0) start++; while(Num[end]<0) end--; max=Num[start]; for(int i=0;i { sum=0; for(int j=i;j { sum+=Num[j]; if(max { max=sum; start=i; end=j; } } } /打印start和end以及最大值max/ printf("start position is:%d/n",start); printf("end position is:%d/n",end); printf("The max value is:%d/n",max); return max;//返回max } void main() { int Num[]={2,-1,1,-20,4,9,-30,1,-1,2}; findMaxPart(Num,sizeof(Num)/sizeof(int)); } #include /在数组Num[]中截取一段Num[start]--Num[end],使得这一段的元素之和最大,打印start和end并返回最大值max/ int findMaxPart(int Num[],int n) { int len=n;//数组的长度 int start=0; int end=len-1; int sum=0; int max=0;//截取数组段的最大值 /略去数组首尾的负数/ while(Num[start]<0) start++; while(Num[end]<0) end--; max=Num[start]; for(int i=0;i { sum=0; for(int j=i;j { sum+=Num[j]; if(max { max=sum; start=i; end=j; } } } /打印start和end以及最大值max/ printf("start position is:%d/n",start); printf("end position is:%d/n",end); printf("The max value is:%d/n",max); return max;//返回max } void main() { int Num[]={2,-1,1,-20,4,9,-30,1,-1,2}; findMaxPart(Num,sizeof(Num)/sizeof(int)); }

问题补充:这种算法的时间复杂度是O(n^2) ,效率太低了,在网友张立志同学的提示下,我用动态规划算法对程序做了优化。时间复杂度是O(n)。代码如下。

#include int main() { int num[]={5,-1,1,-10,5,-1,5,-20,1,-1,3}; int n=sizeof(num)/sizeof(int); int sum=0; int max=num[0];// record the value of max part int start=0;// the start position of the max part int end=0;// the end position of the max part int temp_start; for(int i=0;i { sum+=num[i]; // update max part if(max { max=sum; end=i; start=temp_start; } // find new max part if(sum<0) { sum=0; temp_start=i+1; } } printf("max=%d/n",max); printf("start=%d/n",start); printf("end=%d/n",end); return 0; } #include int main() { int num[]={5,-1,1,-10,5,-1,5,-20,1,-1,3}; int n=sizeof(num)/sizeof(int); int sum=0; int max=num[0];// record the value of max part int start=0;// the start position of the max part int end=0;// the end position of the max part int temp_start; for(int i=0;i { sum+=num[i]; // update max part if(max { max=sum; end=i; start=temp_start; } // find new max part if(sum<0) { sum=0; temp_start=i+1; } } printf("max=%d/n",max); printf("start=%d/n",start); printf("end=%d/n",end); return 0; }

阅读了本文“金山(Kingsoft)服务器端开发工程师笔试题”,本站思而学教育网(cnrencai)笔试频道,还为你提供更多“笔试题目”相关文章阅读

热门推荐

最新文章