金山(Kingsoft)服務器端開發(fā)工程師筆試題和面試題答案

　　總體感覺金山的筆試題難度還可以，既考查了基礎知識，又測試了考生的編程及算法能力。試題大概分為三部分，第一部分是一些簡單的看程序填空，就是填寫程序的運行結果。這一部分只要仔細一點就沒什么問題。第二部分是簡答題，內容包括TCP，UDP協(xié)議，C++拷貝構造函數(shù)，快速排序算法，堆棧等基礎知識，這一部分問題也不大。最后一部分是兩道編程題，由于時間很充裕(兩個小時)如果能想出算法的話應該很快就做完了。這里與大家分享一道編程題，主要考查算法。

　　題目1：有一個int型數(shù)組Num，里面存放著若干的正數(shù)和負數(shù)，請你設計一個算法，在數(shù)組中截取一段Num[start]--Num[end]，使得這一段的整數(shù)之和最大，并返回最大值max。

　　算法思想：start和end記錄最大段的起始和終止位置，首先讓start指向數(shù)組的第一個正數(shù)的下標，end指向數(shù)組的倒數(shù)第一個正數(shù)的下標，即略去數(shù)組首尾的負數(shù)。然后用兩個循環(huán)求出所有組合的最大值并返回，start記錄最大段的起始下標，end記錄終止下標。

　　以下是我用C語言實現(xiàn)的程序代碼，已經在visual C++ 6.0上運行通過了，想加入金山的可以過來圍觀一下，呵呵。

　　#include /*在數(shù)組Num[]中截取一段Num[start]--Num[end]，使得這一段的元素之和最大，打印start和end并返回最大值max*/ int findMaxPart(int Num[],int n) { int len=n;//數(shù)組的長度 int start=0; int end=len-1; int sum=0; int max=0;//截取數(shù)組段的最大值 /*略去數(shù)組首尾的負數(shù)*/ 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 /*在數(shù)組Num[]中截取一段Num[start]--Num[end]，使得這一段的元素之和最大，打印start和end并返回最大值max*/ int findMaxPart(int Num[],int n) { int len=n;//數(shù)組的長度 int start=0; int end=len-1; int sum=0; int max=0;//截取數(shù)組段的最大值 /*略去數(shù)組首尾的負數(shù)*/ 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) ，效率太低了，在網友張立志同學的提示下，我用動態(tài)規(guī)劃算法對程序做了優(yōu)化。時間復雜度是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)服務器端開發(fā)工程師筆試題”，本站大風車網（cnrencai）筆試頻道，還為你提供更多“筆試題目”相關文章閱讀