百度招聘筆試題

百度筆試題（30分）輸入：N（整數(shù)）A.txt615個字節(jié)文件格式如下：字符串\\t數(shù)字\\n說明：1條記錄；字符串中不含有\(zhòng)\t。100的整數(shù)。100A.txt不滿足該條件，程序則退出；如果文件格式錯誤，程序也退出。要求：（正整數(shù)A.ttN條記錄例如：abc\\t20a\\t30de\\t5010即abc20%的概率輸出，a30%的概率輸出，de50%10條記錄以下為一次輸出的結(jié)果,多次輸出的結(jié)果可能不相同。abcadedeabcdeadeade（35分）題目描述：n個正整數(shù)，將它們聯(lián)接成一排，組成一個最小的多位整數(shù)。程序輸入：n個數(shù)程序輸出：聯(lián)接成的多位數(shù)例如：n=2時，232，321連接成的最小整數(shù)為：32132，n=4時，455，31，31233聯(lián)接成的最小整數(shù)為：312313355[題目要求]法。（非常重要）三、系統(tǒng)設(shè)計題（35分）1000萬用戶的系統(tǒng)中，設(shè)計一個推送(feed)系統(tǒng)。以下是一些預定義概念:1unsignedintuserid(uid)uid11000萬的正整數(shù)。2uid3uid4的兩個用戶可以500個；用戶之間的好友關(guān)系可以被解除blogid表示。的文章更新列表。5feed1blogid增加量每天在百萬量級。feed訪問系統(tǒng)。要求：1feed1000feed；feed的展現(xiàn)按照時間倒排序，最新的在最前面除的3、盡可能高效2010百度校園招聘筆試題一、簡答題bug：#include<stdio.h>#include<stdlib.h>structRecord{inta;intb;};intcreate(structRecord*p,intnum){p=newstructRecord[num];if(!p)return-1;elsereturn0;}{structRecord*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=0;}return0;}intmain(void){Test();getchar();return0;}#include<stdio.h>#include<stdlib.h>structRecord{inta;intb;};intcreate(structRecord*&p,intnum){p=NULL;p=newstructRecord[num];if(!p)return-1;}

return0;{structRecord*p=NULL;inti;intnum;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=0;p[i].b=0;}delete[]p;return0;}intmain(void){Test();getchar();return0;}在這臺計算機上可運行并且確定可以終止的程序的最長運行時間是多少？給出思路及推理過程（可以做任何假設(shè)。二、算法設(shè)計nN1N2……Nn構(gòu)成，每個組件都可以獨立編譯，但是某些組件的編譯依賴于其它組件（即某些組件只能在其它組件編譯完成后才能編譯#include<iostream>#defineMAXN505#defineMAXMMAXN*MAXNstructedge{intv;edge*mNext;};intin[MAXN];intn,m;edgeE[MAXM];inten;edge*first[MAXN];intcnt[MAXN][MAXN];voidinsert(intu,intv){E[en].v=v;E[en].mNext=first[u];first[u]=&E[en++];}voidtopo(){for(inti=1;i<=n;i++)for(intu=1;u<=n;u++){if(in[u]==0){in[u]=-1;printf("%d",u);*e=first[u];e;e=e->mNext)in[e->v]--;break;}}}intmain(){freopen("c:/a.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){memset(cnt,0,sizeof(cnt));memset(in,0,sizeof(in));intu,v;en=0;for(inti=0;i<m;i++){scanf("%d%d",&u,&v);if(cnt[u][v]==0){cnt[u][v]=1;insert(u,v);in[v]++;}}topo();printf("\n");}return0;}intmaxnumstr(char*inputstr,char*outputstr)函數(shù)功能：找出inputstr中的最長連續(xù)數(shù)字串存儲到outputstr里并返回長度，如調(diào)用maxnumstr("123abc1234a"outputstr)4outputstr中為"1234"。#include<iostream>#defineMAXN1000intmaxnumstr(char*inputstr,char*outputstr){||outputstr==NULL)throw"ErrorNULLparams";if(*inputstr=='\0'){*outputstr='\0';return0;}char*begin=inputstr;intres=1;intcur=1;charpre=*inputstr++;while(*inputstr){cur++;elsecur=1;if(res<cur){res=cur;}pre=*inputstr++;}for(inti=0;i<res;i++)outputstr[i]=begin[i];returnres;}intmain(){freopen("c:/a.txt","r",stdin);charsrc[MAXN],tar[MAXN];while(scanf("%s",src)!=EOF){",maxnumstr(src,NULL));printf("%s\n",tar);}return0;}三、系統(tǒng)設(shè)計URL(統(tǒng)一資源定位符)site、path組成，并且有其它屬性信息如訪問時間等。site://.baidu，path為/img/abc。100URL信息；URL信息的添加、刪除及修改；URL的屬性信息；校園招聘筆試題一、簡答A（0AB（我用方法比較笨，應(yīng)該是做錯了，唉）A,Bunsignedint4個字節(jié)(A&1)^(B&1)剩下兩位分別與242.閱讀一段代碼，然后有四個小問題，代碼和題都很簡單基礎(chǔ)。a）C程序中的存儲區(qū)分哪幾個部分？（如常量、全局存儲區(qū)（靜態(tài)變量、全局變量、代碼區(qū)、堆、棧分配失敗以后將會返回一個空指針new/deletemalloc/free的區(qū)別。free類似.判斷一個括號字符串是否匹配正確，如果括號有多種，怎么做？如（）正確，首先需要確定的一點是這個括號字符串中不能包含除括號以外的其它字符。chchmap中，則將其壓mapch（匹配錯誤二、算法案。請詳細描述你的算法思路（可以用偽代碼，并分析時間復雜度和空間復雜度。完整代碼，盡量高效，簡潔）partitionO(n)O(1)。三、系統(tǒng)設(shè)計題AfollowBB的消息，A都能看見。下，快速的實現(xiàn)以下兩種查詢：a）給定一個用戶，查詢他發(fā)送的消息，按消息發(fā)送時間排序，新的消息在前。follow的所有人的消息，按消息發(fā)送時間排序，新的消息在前.年百度校園招聘技術(shù)類筆試真題新鮮出爐第一大題定義棧的數(shù)據(jù)結(jié)構(gòu)，添加一個min函數(shù)，找到棧的最小元素。要求函數(shù)min、push、pop的時間（，請簡要描述思路。是一個讀程序?qū)懡Y(jié)果，并判斷函數(shù)功能。同時要指出程序的隱患 太長了，記不住了。分析線性表、二叉平衡樹和哈希表存儲數(shù)據(jù)時各自的優(yōu)劣。第二大題種中截取一段，要求包含所有不同的顏色，長度越短越好，如何截取。詳述算法思路，并分析時間和空間復雜度。設(shè)計strnumcmp函數(shù)，比較字符串的大小。功能為a.當字符串中有數(shù)字時，以數(shù)字大小為準b.strcmp方式。第三大題處理一個詞搭配的詞典，條件為1)“今天”和“晚上”“今天晚上”和“晚上今天”10萬量級1萬個詞搭配對字典的使用讀操作很多，通常為上千次請求，幾乎沒有寫入操作。請設(shè)計一個字典服務(wù)系統(tǒng)，當請求為兩個詞的搭配時，能快速返回搭配的相關(guān)信息，使用盡可能少的資源，并計算出需要使用的機器資源。2011.10.16校園招聘會筆試題一、算法設(shè)計n個點，并給出時間復雜度分析。思路：這個使用數(shù)學中的極坐標來解決，先調(diào)用[s1，t1]r，歸一化后乘以半徑，得/（t2-s2）queryquery非常多，故系統(tǒng)不能全存，設(shè)系mrymquery被抽中的概率相等，并分析之，注意：不到最后一刻，并不知用戶的總請求量。m+i，那么在im/m+，im/m+）m/（m+i）(m-1)/(m+i)query被抽中的概率是相等的。3、C+STLvector的相關(guān)問題：push_back時，其內(nèi)部的內(nèi)存分配是如何進行的？clear時，內(nèi)部是如何具體實現(xiàn)的？若想將其內(nèi)存釋放，該如何操作？vector的工作原理是系統(tǒng)預先分配一塊CAPACITY這塊空間會讓某種方式擴展，但是你刪除數(shù)據(jù)的時候，它卻不會縮小。vector為了防止大量分配連續(xù)內(nèi)存的開銷，保持一塊默認的尺寸的內(nèi)存，clear只是清數(shù)據(jù)了，未vectorcapacity容量未變化，系統(tǒng)維護一個的默認值。vector中占用的全部內(nèi)存呢?標準的解決方法如下template<classT>voidClearVector(vector<T>&vt){vector<T>vtTemp;veTemp.swap(vt);}事實上，vectoracquire/release內(nèi)存，內(nèi)存管理框freestl的底層：stl假定如果你需要更多的資源就代表你以后也可能需要這么多資源(listhashmap也是用這些內(nèi)存)malloc/free。如果是這trade-off二是提高了內(nèi)存申請和釋放的效率——不用每次都在系統(tǒng)內(nèi)存里尋找一番。二、系統(tǒng)設(shè)計正常用戶端每分鐘最多發(fā)一個請求至服務(wù)端，服務(wù)端需做一個異常客戶端行為的過濾系統(tǒng)，設(shè)服務(wù)A1分鐘內(nèi)的客戶端任何其它請求都需要被過濾，現(xiàn)知每一IPv6ID，客戶端個數(shù)太多，以至于無法全部放到單臺服務(wù)器的內(nèi)存少越好，請將關(guān)鍵的設(shè)計和思想用圖表和代碼表現(xiàn)出來。p([1,2,3])輸出：[123]、[132]、[213]、[231]、[321]、[312]求一個組合函數(shù)。全排列，最終結(jié)果為取出的字符和剩余子串全排列的組合。[cpp]viewplaincopy #include<iostream>#include<string> usingnamespacestd;4. 5.voidpermute1(stringprefix,stringstr)6.{ if(str.length()==0)cout<<prefix<<endl; else10. { for(inti=0;i<str.length();i++)13. }14.} 15.16.voidpermute1(strings) 17.{18. permute1("",s); 19.}20. 21.intmain(void)22.{ //method1,unabletoremoveduplicatepermutations.permute1("abc"); return0;26.} 優(yōu)點：該方法易于理解，但無法移除重復的排列，如：s="ABA"，會生成兩個“AAB”。21容易理解。abca，求后面兩bcbca和后面的bbac，bacc放到第一位置的時候了。記住abc仍然是和原先處在第一acbaba之后，cacbacb、a的排列。典型的遞歸思路了?；谇懊娴姆治?，我們可以得到如下的參考代碼：1.1.voidPermutation(char*pStr,char*pBegin)3.assert(pStr&&pBegin);5.//return;7.printf("%s\n",pStr);if(*pBegin=='\0')6.//if(!pStr||!pBegin)4.2.{8. else9. {10. chartemp;11. for(char*pCh=pBegin;*pCh!='\0';pCh++)12. {13. if(pChpBegin&&*pCh*pBegin)//為避免生成重復排列，當不同位置的字符相同時不再交換14. continue;15. temp=*pCh;16. *pCh=*pBegin;17. *pBegin=temp;18.19. Permutation(pStr,pBegin+1);20.21. temp=*pCh;22. *pCh=*pBegin;23. *pBegin=temp;24. }25. }26.}27.28.intmain(void)29.{30. charstr[]="aba";31. Permutation(str,str);32. return0;33.}p([1,2,3])輸出：[1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3]這兩問可以用偽代碼。2012校園招聘筆試題一.編程題typedefstructintid；//IDbooldoschedule（task*pask，inttask_num）;以下函數(shù)可以直接調(diào)用：dk（inti；執(zhí)行一個進程intwaittaskinttimeout；//ti，如果沒有任-1boolkilltas（inti.闡述棧和堆在生命周期、速度、內(nèi)存性能等方面的不同點。假如現(xiàn)在有一個緩沖區(qū)域絕大多1KB100MB，怎么樣合理分配內(nèi)存？const修飾符的語句的意義a).double*ptr=&value；b).constdouble*ptr=&value;c).double*constptr=&value;d).constdouble*constptr=&value;cconstconstdoublevalue=0.2f；double*ptr；ptrvaluePtr=(int*)&value;三.算法設(shè)計題A（1,、B2,、（3,B和C5個節(jié)點的有向圖，標有權(quán)值，求始點到終-_四.系統(tǒng)設(shè)計題（erSS運0weywqeey5KBB。做出一個方案，說明系統(tǒng)結(jié)構(gòu)、存儲結(jié)構(gòu)、性能優(yōu)化等方面的設(shè)計。2013校園招聘筆試題（30）1：數(shù)據(jù)庫以及線程發(fā)生死鎖的原理及必要條件，如何避免死鎖答：產(chǎn)生死鎖的原因主要是：因為系統(tǒng)資源不足。進程運行推進的順序不合適。資源分配不當?shù)?。產(chǎn)生死鎖的四個必要條件：互斥條件：一個資源每次只能被一個進程使用。請求與保持條件：一個進程因請求資源而阻塞時，對已獲得的資源保持不放。不剝奪條件:進程已獲得的資源，在末使用完之前，不能強行剝奪。循環(huán)等待條件:若干進程之間形成一種頭尾相接的循環(huán)等待資源關(guān)系。避免死鎖：死鎖的預防是通過破壞產(chǎn)生條件來阻止死鎖的產(chǎn)生，但這種方法破壞了系統(tǒng)的并行性和并發(fā)性。死鎖產(chǎn)生的前三個條件是死鎖產(chǎn)生的必要條件，也就是說要產(chǎn)生死鎖必須具備的條件，而不是存在3個條件就一定產(chǎn)生死鎖，那么只要在邏輯上回避了第四個條件就可以避免死鎖。避免死鎖采用的是允許前三個條件存在，但通過合理的資源分配算法來確保永遠不會形成環(huán)形等待的封閉進程鏈，從而避免死鎖。該方法支持多個進程的并行執(zhí)行，為了避免死鎖，系統(tǒng)動態(tài)的確定是否分配一個資源給請求的進程。預防死鎖：具體的做法是破壞產(chǎn)生死鎖的四個必要條件之一2：面向?qū)ο蟮娜齻€基本元素，五個基本原則答：三個基本元素：封裝繼承多態(tài)五個基本原則：以提高內(nèi)聚性來減少引起變化的原因。（Open-Closedprinciple）:軟件實體應(yīng)該是可擴展的，而不可修改的。也就是，對擴展開放，對修改封閉的。機制的約束規(guī)范，只有子類能夠替換基類時，才能保證系統(tǒng)在運行期內(nèi)識別子類，這是保證繼承復用的基礎(chǔ)。Principle）:依賴于抽象。具體而言就是高層模塊不依賴于底層模塊，二者都同依賴于抽象；抽象不依賴于具體，具體依賴于抽象。Principle）:使用多個小的專門的接口，而不要使用一個大的總接口。3：windows內(nèi)存管理的機制以及優(yōu)缺點答：分頁存儲管理基本思想：頁頁和塊的大小相等。可將用戶程序的任一頁放在內(nèi)存的任一塊中，實現(xiàn)了離散分配。分段存儲管理基本思想：將用戶程序地址空間分成若干個大小不等的段，每段可以定義一組相對完整的邏輯信息。存儲分配時，以段為單位，段與段在內(nèi)存中可以不相鄰接，也實現(xiàn)了離散分配。段頁式存儲管理基本思想：分頁系統(tǒng)能有效地提高內(nèi)存的利用率，而分段系統(tǒng)能反映程序的邏輯結(jié)構(gòu)，便于段的共享與保護，將分頁與分段兩種存儲方式結(jié)合起來，就形成了段頁式存儲管理方式。在段頁式存儲管理系統(tǒng)中，作業(yè)的地址空間首先被分成若干個邏輯分段，每段都有自己的段號，然段頁式系統(tǒng)中，作業(yè)的地址結(jié)構(gòu)包含三部分的內(nèi)容：段號 頁號 頁內(nèi)位移量程序員按照分段系統(tǒng)的地址結(jié)構(gòu)將地址分為段號與段內(nèi)位移量，地址變換機構(gòu)將段內(nèi)位移量分解為頁號和頁內(nèi)位移量。為實現(xiàn)段頁式存儲管理，系統(tǒng)應(yīng)為每個進程設(shè)置一個段表，包括每段的段號，該段的頁表始址和頁表長度。每個段有自己的頁表，記錄段中的每一頁的頁號和存放在主存中的物理塊號。（40）1001個員工，現(xiàn)在要在公司里面找到最好的羽毛球選手，也就是第一名，每個人都必須參賽，問至少要比賽多少次才能夠找到最好的羽毛球員工。500組剩下一人，類似于歸并排序的方式，比出冠軍后，讓冠軍之間再比，主要是要想想多余的那一個選手如何處理，必然要在第一次決出冠軍后加入比賽組。2100個燈泡，每個燈泡都是關(guān)著的，第一趟把所有的燈泡燈泡打開，第二趟把偶數(shù)位的燈泡制反（也就是開了的關(guān)掉，關(guān)了的打開），第三趟讓第3,6,9....的燈泡制反 第100趟讓第100個燈泡制反，問經(jīng)過一百趟以后有多少燈泡亮著答：對于每盞燈，拉動的次數(shù)是奇數(shù)時，燈就是亮著的，拉動的次數(shù)是偶數(shù)時，燈就是關(guān)著的。3．1——100100個數(shù)中有哪幾個數(shù)，約數(shù)的個數(shù)是奇數(shù)。我們知道一個數(shù)的約數(shù)都是成對出現(xiàn)的，只有完全平方數(shù)約數(shù)的個數(shù)才是奇數(shù)個。10010盞燈是亮著的。它們的編號分別是：1、4、9、16、25、36、49、64、81、100。32050020*500個數(shù)中找出排500的數(shù)答：TOP-KK的最小堆來解決*pszStringintnCharsRotate),ABCDEFG3DEFGABCO（1），O（n）（30）現(xiàn)在有一個手機，手機上的鍵盤上有這樣的對應(yīng)關(guān)系，2對應(yīng)"abc",3對應(yīng)"def". 里面有一個“樣楊往userlist中查找出對應(yīng)的用戶名和電話號碼并返回結(jié)果。C++語言:電話號碼對應(yīng)的英語單詞(注意此題的非遞歸做法)#include<iostream>#include<cstdlib>#defineN4電話號碼個數(shù)4.5.usingnamespacestd;6.7.charc[][10"","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};//存儲各個數(shù)字所能代表的字符8.intnumber[N]{2,4,7,9//存儲電話號碼9.inttotal[10{0033333434}//各個數(shù)組所能代表的字符總數(shù)10.intanswer[N];//數(shù)字目前所代表的字符在其所能代表的字符集中的位置,011.voidSearch(int*numberintn);//非遞歸的辦法voidRecursiveSearch(int*numberintcur,char*ps,intn);//遞歸的辦法1.intmain()2.{3. //Search(number,N);charps[N+1]={0};RecursiveSearch(number,0,ps,N);return0;}voidSearch(int*number,intn){inti;while(