百度校園招聘歷年筆試題

一、編程題（30分）A.txt615個(gè)字節(jié)字符串\\t數(shù)字1條記錄；字符串中不含有\(zhòng)\t100100A.txt不滿足該條件，程序則退出；N（正整數(shù)A.txt，按照字符串出現(xiàn)概率隨機(jī)地輸出字符串，輸出N條記錄A.txt即abc20%的概率輸出，a30%的概率輸出，de50%10以下為一次輸出的結(jié)果,二、算法題（35分）n程序輸入：nn=2時(shí)，232，321n=4時(shí)，455，31，31233[題目要求三、系統(tǒng)設(shè)計(jì)題（35分1000萬用戶的系統(tǒng)中，設(shè)計(jì)一個(gè)推送(feed)系統(tǒng)。以下是一些預(yù)定義概念1unsignedintuserid(uid)110002uid3uid4的兩個(gè)用戶可以互為好友。每個(gè)用戶好友的上限是500個(gè)；用戶之間的好友關(guān)系可以被解除章通過一個(gè)blogid表示。5feed1blogid增加量每天在百萬量級(jí)。題目：請(qǐng)?jiān)谝陨舷拗茥l件下，設(shè)計(jì)一個(gè)高效的feed訪問系統(tǒng)。1feed1000feed；feed的展現(xiàn)2010#include<stdio.h>#include<stdlib.h>structRecord{inta;intintcreate(structRecord*p,intp=newstructif(!p)return-1;return0;intstructRecord*p=NULL;inti;intnum;printf("0x%08x\n",p);scanf("Inputrecordnum:%d",&num);if(create(p,num)<0)return-1;printf("0x%08x\n",p);for(i=0;i<num;i++){p[i].a=0;p[i].b=returnintreturn0;#include<stdio.h>#include<stdlib.h>structRecordinta;intintcreate(structRecord*&p,intp=newstructRecord[num];if(!p)return-

returnintstructRecord*p=NULL;inti;intnum;printf("0x%08x\n",p);printf("Inputrecordnum:");scanf("%d",&num);if(create(p,num)<0)return-1;printf("0x%08x\n",p);for(i=0;i<num;i++){p[i].a=p[i].b=delete[]p;returnintreturn0;nN1N2……Nn構(gòu)成，每個(gè)組件都可以獨(dú)立編譯，但是某些組件的編譯依#include<iostream>#defineMAXN505#defineMAXMstructintedgeintin[MAXN];intn,m;edgeE[MAXM];inten;edgeintvoidinsert(intu,intvoidfor(intfor(intprintf("%d",u);for(edge*e=first[u];e;e=e->mNext)intintu,v;for(intreturnintmaxnumstr(char*inputstr,char函數(shù)功能：找出inputstr中的最長連續(xù)數(shù)字串存儲(chǔ)到outputstr里并返回長度，如調(diào)用,且#include<iostream>#defineMAXNintmaxnumstr(char*inputstr,charif(inputstr==NULL||outputstr==NULL)throw"ErrorNULLparams";return0;char*begin=inputstr;intres=1;intcharpre=*inputstr++;for(inti=0;i<res;i++)returnres;intcharsrc[MAXN],tar[MAXN];printf("%d",maxnumstr(src,NULL));returnURL(統(tǒng)一資源定位符)site、path中為100URLURLURL（0<A,B<100000A,Bunsignedint4個(gè)字節(jié),(A&1)^(B&1)剩下兩位分別與2a）C程序中的存儲(chǔ)區(qū)分哪幾個(gè)部分？new分配的內(nèi)存如果分配失敗會(huì)如何？new/deletemalloc/free與free類似（[]）chchmap中，則將其壓mapch（匹配錯(cuò)誤Spider如何在不超過抓取限額的情況下使得抓取的網(wǎng)頁價(jià)值之和最大，要求一個(gè)最佳抓取方partitionO(n)O(1)。AfollowBB的消息，Ab）follow的所有人的消息，按消息發(fā)送時(shí)間排序，新的消息在前.2011年百度校園招聘技術(shù)類筆試真題新鮮出爐minmin、push、pop的時(shí)間復(fù)雜度為O（1，請(qǐng)簡要描述思路。是一個(gè)讀程序?qū)懡Y(jié)果，并判斷函數(shù)功能。同時(shí)要指出程序的隱 mn(n10)，從設(shè)計(jì)strnumcmp函數(shù)，比較字符串的大小。功能為a.當(dāng)字符串中有數(shù)字時(shí)，以數(shù)字大小為準(zhǔn)strcmp方式。1)“今天”和“晚上”“今天晚上”和“晚上今天”101思路：這個(gè)使用數(shù)學(xué)中的極坐標(biāo)來解決，先調(diào)用[s1，t1]r，歸一化后乘以半徑，得到使得每個(gè)query被抽中的概率相等，并分析之，注意：不到最后一刻，并不知用戶的總請(qǐng)求量。那么在1-----m+im/m+i，im/==，所以每個(gè)3、C+STLvectorpush_backclearvector的工作原理是系統(tǒng)預(yù)先分配一塊CAPACITYvector為了防止大量分配連續(xù)內(nèi)存的開銷，保持一塊默認(rèn)的尺寸的內(nèi)存，clear只是清數(shù)據(jù)了，未清內(nèi)存，因?yàn)関ector的capacity容量未變化，系統(tǒng)維護(hù)一個(gè)的默認(rèn)值。vector中占用的全部內(nèi)存呢template<classTvoidClearVector(vector<T>&vtvector<T>vtTemp;veTemp.swap(vt);事實(shí)上，vectoracquire/release內(nèi)存，內(nèi)存管理框free以減少內(nèi)存，因?yàn)閮?nèi)存分配在stl的底層：stl假定如果你需要更多的資源就代表你以后也可能需要這么多資源(listhashmap也是用這些內(nèi)存)malloc/free。如果是這個(gè)邏輯的話這可能是個(gè)trade-offA1分鐘內(nèi)的客戶端任何其它請(qǐng)求都需要被過濾，現(xiàn)知每一客戶端都有一個(gè)IPv6地址可作為其ID，客戶端個(gè)數(shù)太多，以至于無法全部放到單臺(tái)服務(wù)器的內(nèi)存如p([1,2,3])輸出：1：依次從字符串中取出一個(gè)字符作為最終排列的第一個(gè)字符，對(duì)剩余字符組成的字符串生成[cpp]view #include#include usingnamespace voidpermute1(stringprefix,string if(str.length()==cout<<prefix<< for(inti=0;i<str.length(); 14.} voidpermute1(string 19. int //method1,unabletoremoveduplicate return26. 方法2：利用交換的思想，具體見實(shí)例，但該方法不如方法1容易理解。我們以三個(gè)字符abc為例來分析一下求字符串排列的過程。首先我們固定第一個(gè)字符a，求后面兩bcbca和后面的bbac，bacc放到第一位置的時(shí)候了。記住前面我們已經(jīng)把原先的第一個(gè)字符a和后面的b做了交換，為了保證這次c仍然是和原先處在第一acbaba之后，cacbacb、a的排列。1.1.voidPermutation(char*pStr,char*assert(pStr&&//returnif(*pBegin==//if(!pStr||2. char for(char*pCh=pBegin;*pCh!='\0'; if(pChpBegin&&*pCh*pBegin)// temp= *pCh= *pBegin= Permutation(pStr, temp= *pCh= *pBegin= 26.28.int29. charstr[]= return33.p([1,2,3])2012一.B任務(wù)數(shù)據(jù)結(jié)構(gòu)原型為：typedefstruct{intid；//該任務(wù)的IDbooldoschedule（task*pask，inttask_num）;以下函數(shù)可以直接調(diào)用：id；//timeout；//id；//改進(jìn)？二。簡答題數(shù)只需要1KB空間，極少數(shù)極端情況下需要100MB，怎么樣合理分配內(nèi)存？consta)double*ptr=&valueb)constdouble*ptr=&valuec)double*constptr=&valued).constdouble*constptr=&value;cconstconstdoublevalue=0.2f；doubleptrvaluePtr=(int*)&value;三.（1,5B（2,8C（3,95個(gè)節(jié)點(diǎn)的有向圖，標(biāo)有權(quán)值，求始點(diǎn)到終點(diǎn)的距離，圖就不畫了。這兩道題都需要詳細(xì)寫明算法與函數(shù)設(shè)計(jì)-_-四.系統(tǒng)設(shè)計(jì)題serverqueryquery5KB3GB2013一：簡答題不剝奪條件:循環(huán)等待條件:33：windows段頁式系統(tǒng)中，作業(yè)的地址結(jié)構(gòu)包含三部分的內(nèi)容：段 頁 頁內(nèi)位移二：程序設(shè)計(jì)題：公司里面有5002100 第100趟讓100這10010它們的編號(hào)分別是：1、4、9、16、25、36、49、64、81、10032050020*500500答：TOP-KK字符串左移，void*pszStringRotate(char*pszStringintnCharsRotate),ABCDEFGDEFGABCO（1），三：系統(tǒng)設(shè)計(jì)題現(xiàn)在有一個(gè)手機(jī)，手機(jī)上的鍵盤上有這樣的對(duì)應(yīng)關(guān)系，2對(duì)應(yīng)"abc",3對(duì)應(yīng) userlistC++語言:電話號(hào)碼對(duì)應(yīng)的英語單詞(注意此題的非遞歸做法#include#include#defineN4usingnamespacestd;]={intnumber[N]{2,4,7,9//inttotal[10{0033333434}//intanswer[N];//數(shù)字目前所代表的字符在其所能代表的字符集中的位置,voidSearch(int*numberintn);//voidRecursiveSearch(int*numberintcur,char*ps,intn);//intcharps[N+1]=RecursiveSearch(number,0,ps,returnvoidSearch(int*number,intintfor(i=0;i<n;printf("%c",intkn- //kwhile循環(huán)來解決擴(kuò)展性問題,while(k>=if(answer[k]<total[number[k]]-answer[k]=--if(k</*遞歸的解法number為存儲(chǔ)電話號(hào)碼的數(shù)組,posnumber中的下標(biāo),初始為0*ps為一外部數(shù)組,用于存放字母,n代表電話號(hào)碼的長度(個(gè)數(shù)*此遞歸的方法好理解,*voidRecursiveSea