百度招聘筆試題

百度筆試題（30分）輸入：N（整數(shù)）A.txt615個(gè)字節(jié)文件格式如下：字符串\\t數(shù)字\\n說明：1條記錄；字符串中不含有\(zhòng)\t。100的整數(shù)。100A.txt不滿足該條件，程序則退出；如果文件格式錯(cuò)誤，程序也退出。要求：（正整數(shù)A.ttN條記錄例如：abc\\t20a\\t30de\\t5010即abc20%的概率輸出，a30%的概率輸出，de50%10條記錄以下為一次輸出的結(jié)果,多次輸出的結(jié)果可能不相同。abcadedeabcdeadeade（35分）題目描述：n個(gè)正整數(shù)，將它們聯(lián)接成一排，組成一個(gè)最小的多位整數(shù)。程序輸入：n個(gè)數(shù)程序輸出：聯(lián)接成的多位數(shù)例如：n=2時(shí)，232，321連接成的最小整數(shù)為：32132，n=4時(shí)，455，31，31233聯(lián)接成的最小整數(shù)為：312313355[題目要求]法。（非常重要）三、系統(tǒng)設(shè)計(jì)題（35分）1000萬用戶的系統(tǒng)中，設(shè)計(jì)一個(gè)推送(feed)系統(tǒng)。以下是一些預(yù)定義概念:1unsignedintuserid(uid)uid11000萬的正整數(shù)。2uid3uid4的兩個(gè)用戶可以500個(gè)；用戶之間的好友關(guān)系可以被解除blogid表示。的文章更新列表。5feed1blogid增加量每天在百萬量級(jí)。feed訪問系統(tǒng)。要求：1feed1000feed；feed的展現(xiàn)按照時(shí)間倒排序，最新的在最前面除的3、盡可能高效2010百度校園招聘筆試題一、簡(jiǎn)答題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;}在這臺(tái)計(jì)算機(jī)上可運(yùn)行并且確定可以終止的程序的最長(zhǎng)運(yùn)行時(shí)間是多少？給出思路及推理過程（可以做任何假設(shè)。二、算法設(shè)計(jì)nN1N2……Nn構(gòu)成，每個(gè)組件都可以獨(dú)立編譯，但是某些組件的編譯依賴于其它組件（即某些組件只能在其它組件編譯完成后才能編譯#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中的最長(zhǎng)連續(xù)數(shù)字串存儲(chǔ)到outputstr里并返回長(zhǎng)度，如調(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è)計(jì)URL(統(tǒng)一資源定位符)site、path組成，并且有其它屬性信息如訪問時(shí)間等。site://.baidu，path為/img/abc。100URL信息；URL信息的添加、刪除及修改；URL的屬性信息；校園招聘筆試題一、簡(jiǎn)答A（0AB（我用方法比較笨，應(yīng)該是做錯(cuò)了，唉）A,Bunsignedint4個(gè)字節(jié)(A&1)^(B&1)剩下兩位分別與242.閱讀一段代碼，然后有四個(gè)小問題，代碼和題都很簡(jiǎn)單基礎(chǔ)。a）C程序中的存儲(chǔ)區(qū)分哪幾個(gè)部分？（如常量、全局存儲(chǔ)區(qū)（靜態(tài)變量、全局變量、代碼區(qū)、堆、棧分配失敗以后將會(huì)返回一個(gè)空指針new/deletemalloc/free的區(qū)別。free類似.判斷一個(gè)括號(hào)字符串是否匹配正確，如果括號(hào)有多種，怎么做？如（）正確，首先需要確定的一點(diǎn)是這個(gè)括號(hào)字符串中不能包含除括號(hào)以外的其它字符。chchmap中，則將其壓mapch（匹配錯(cuò)誤二、算法案。請(qǐng)?jiān)敿?xì)描述你的算法思路（可以用偽代碼，并分析時(shí)間復(fù)雜度和空間復(fù)雜度。完整代碼，盡量高效，簡(jiǎn)潔）partitionO(n)O(1)。三、系統(tǒng)設(shè)計(jì)題AfollowBB的消息，A都能看見。下，快速的實(shí)現(xiàn)以下兩種查詢：a）給定一個(gè)用戶，查詢他發(fā)送的消息，按消息發(fā)送時(shí)間排序，新的消息在前。follow的所有人的消息，按消息發(fā)送時(shí)間排序，新的消息在前.年百度校園招聘技術(shù)類筆試真題新鮮出爐第一大題定義棧的數(shù)據(jù)結(jié)構(gòu)，添加一個(gè)min函數(shù)，找到棧的最小元素。要求函數(shù)min、push、pop的時(shí)間（，請(qǐng)簡(jiǎn)要描述思路。是一個(gè)讀程序?qū)懡Y(jié)果，并判斷函數(shù)功能。同時(shí)要指出程序的隱患 太長(zhǎng)了，記不住了。分析線性表、二叉平衡樹和哈希表存儲(chǔ)數(shù)據(jù)時(shí)各自的優(yōu)劣。第二大題種中截取一段，要求包含所有不同的顏色，長(zhǎng)度越短越好，如何截取。詳述算法思路，并分析時(shí)間和空間復(fù)雜度。設(shè)計(jì)strnumcmp函數(shù)，比較字符串的大小。功能為a.當(dāng)字符串中有數(shù)字時(shí)，以數(shù)字大小為準(zhǔn)b.strcmp方式。第三大題處理一個(gè)詞搭配的詞典，條件為1)“今天”和“晚上”“今天晚上”和“晚上今天”10萬量級(jí)1萬個(gè)詞搭配對(duì)字典的使用讀操作很多，通常為上千次請(qǐng)求，幾乎沒有寫入操作。請(qǐng)?jiān)O(shè)計(jì)一個(gè)字典服務(wù)系統(tǒng)，當(dāng)請(qǐng)求為兩個(gè)詞的搭配時(shí)，能快速返回搭配的相關(guān)信息，使用盡可能少的資源，并計(jì)算出需要使用的機(jī)器資源。2011.10.16校園招聘會(huì)筆試題一、算法設(shè)計(jì)n個(gè)點(diǎn)，并給出時(shí)間復(fù)雜度分析。思路：這個(gè)使用數(shù)學(xué)中的極坐標(biāo)來解決，先調(diào)用[s1，t1]r，歸一化后乘以半徑，得/（t2-s2）queryquery非常多，故系統(tǒng)不能全存，設(shè)系mrymquery被抽中的概率相等，并分析之，注意：不到最后一刻，并不知用戶的總請(qǐng)求量。m+i，那么在im/m+，im/m+）m/（m+i）(m-1)/(m+i)query被抽中的概率是相等的。3、C+STLvector的相關(guān)問題：push_back時(shí)，其內(nèi)部的內(nèi)存分配是如何進(jìn)行的？clear時(shí)，內(nèi)部是如何具體實(shí)現(xiàn)的？若想將其內(nèi)存釋放，該如何操作？vector的工作原理是系統(tǒng)預(yù)先分配一塊CAPACITY這塊空間會(huì)讓某種方式擴(kuò)展，但是你刪除數(shù)據(jù)的時(shí)候，它卻不會(huì)縮小。vector為了防止大量分配連續(xù)內(nèi)存的開銷，保持一塊默認(rèn)的尺寸的內(nèi)存，clear只是清數(shù)據(jù)了，未vectorcapacity容量未變化，系統(tǒng)維護(hù)一個(gè)的默認(rèn)值。vector中占用的全部?jī)?nèi)存呢?標(biāo)準(zhǔn)的解決方法如下template<classT>voidClearVector(vector<T>&vt){vector<T>vtTemp;veTemp.swap(vt);}事實(shí)上，vectoracquire/release內(nèi)存，內(nèi)存管理框freestl的底層：stl假定如果你需要更多的資源就代表你以后也可能需要這么多資源(listhashmap也是用這些內(nèi)存)malloc/free。如果是這trade-off二是提高了內(nèi)存申請(qǐng)和釋放的效率——不用每次都在系統(tǒng)內(nèi)存里尋找一番。二、系統(tǒng)設(shè)計(jì)正常用戶端每分鐘最多發(fā)一個(gè)請(qǐng)求至服務(wù)端，服務(wù)端需做一個(gè)異?？蛻舳诵袨榈倪^濾系統(tǒng)，設(shè)服務(wù)A1分鐘內(nèi)的客戶端任何其它請(qǐng)求都需要被過濾，現(xiàn)知每一IPv6ID，客戶端個(gè)數(shù)太多，以至于無法全部放到單臺(tái)服務(wù)器的內(nèi)存少越好，請(qǐng)將關(guān)鍵的設(shè)計(jì)和思想用圖表和代碼表現(xiàn)出來。p([1,2,3])輸出：[123]、[132]、[213]、[231]、[321]、[312]求一個(gè)組合函數(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)點(diǎn)：該方法易于理解，但無法移除重復(fù)的排列，如：s="ABA"，會(huì)生成兩個(gè)“AAB”。21容易理解。abca，求后面兩bcbca和后面的bbac，bacc放到第一位置的時(shí)候了。記住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)//為避免生成重復(fù)排列，當(dāng)不同位置的字符相同時(shí)不再交換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í)行一個(gè)進(jìn)程intwaittaskinttimeout；//ti，如果沒有任-1boolkilltas（inti.闡述棧和堆在生命周期、速度、內(nèi)存性能等方面的不同點(diǎn)。假如現(xiàn)在有一個(gè)緩沖區(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è)計(jì)題A（1,、B2,、（3,B和C5個(gè)節(jié)點(diǎn)的有向圖，標(biāo)有權(quán)值，求始點(diǎn)到終-_四.系統(tǒng)設(shè)計(jì)題（erSS運(yùn)0weywqeey5KBB。做出一個(gè)方案，說明系統(tǒng)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、性能優(yōu)化等方面的設(shè)計(jì)。2013校園招聘筆試題（30）1：數(shù)據(jù)庫以及線程發(fā)生死鎖的原理及必要條件，如何避免死鎖答：產(chǎn)生死鎖的原因主要是：因?yàn)橄到y(tǒng)資源不足。進(jìn)程運(yùn)行推進(jìn)的順序不合適。資源分配不當(dāng)?shù)取．a(chǎn)生死鎖的四個(gè)必要條件：互斥條件：一個(gè)資源每次只能被一個(gè)進(jìn)程使用。請(qǐng)求與保持條件：一個(gè)進(jìn)程因請(qǐng)求資源而阻塞時(shí)，對(duì)已獲得的資源保持不放。不剝奪條件:進(jìn)程已獲得的資源，在末使用完之前，不能強(qiáng)行剝奪。循環(huán)等待條件:若干進(jìn)程之間形成一種頭尾相接的循環(huán)等待資源關(guān)系。避免死鎖：死鎖的預(yù)防是通過破壞產(chǎn)生條件來阻止死鎖的產(chǎn)生，但這種方法破壞了系統(tǒng)的并行性和并發(fā)性。死鎖產(chǎn)生的前三個(gè)條件是死鎖產(chǎn)生的必要條件，也就是說要產(chǎn)生死鎖必須具備的條件，而不是存在3個(gè)條件就一定產(chǎn)生死鎖，那么只要在邏輯上回避了第四個(gè)條件就可以避免死鎖。避免死鎖采用的是允許前三個(gè)條件存在，但通過合理的資源分配算法來確保永遠(yuǎn)不會(huì)形成環(huán)形等待的封閉進(jìn)程鏈，從而避免死鎖。該方法支持多個(gè)進(jìn)程的并行執(zhí)行，為了避免死鎖，系統(tǒng)動(dòng)態(tài)的確定是否分配一個(gè)資源給請(qǐng)求的進(jìn)程。預(yù)防死鎖：具體的做法是破壞產(chǎn)生死鎖的四個(gè)必要條件之一2：面向?qū)ο蟮娜齻€(gè)基本元素，五個(gè)基本原則答：三個(gè)基本元素：封裝繼承多態(tài)五個(gè)基本原則：以提高內(nèi)聚性來減少引起變化的原因。（Open-Closedprinciple）:軟件實(shí)體應(yīng)該是可擴(kuò)展的，而不可修改的。也就是，對(duì)擴(kuò)展開放，對(duì)修改封閉的。機(jī)制的約束規(guī)范，只有子類能夠替換基類時(shí)，才能保證系統(tǒng)在運(yùn)行期內(nèi)識(shí)別子類，這是保證繼承復(fù)用的基礎(chǔ)。Principle）:依賴于抽象。具體而言就是高層模塊不依賴于底層模塊，二者都同依賴于抽象；抽象不依賴于具體，具體依賴于抽象。Principle）:使用多個(gè)小的專門的接口，而不要使用一個(gè)大的總接口。3：windows內(nèi)存管理的機(jī)制以及優(yōu)缺點(diǎn)答：分頁存儲(chǔ)管理基本思想：頁頁和塊的大小相等。可將用戶程序的任一頁放在內(nèi)存的任一塊中，實(shí)現(xiàn)了離散分配。分段存儲(chǔ)管理基本思想：將用戶程序地址空間分成若干個(gè)大小不等的段，每段可以定義一組相對(duì)完整的邏輯信息。存儲(chǔ)分配時(shí)，以段為單位，段與段在內(nèi)存中可以不相鄰接，也實(shí)現(xiàn)了離散分配。段頁式存儲(chǔ)管理基本思想：分頁系統(tǒng)能有效地提高內(nèi)存的利用率，而分段系統(tǒng)能反映程序的邏輯結(jié)構(gòu)，便于段的共享與保護(hù)，將分頁與分段兩種存儲(chǔ)方式結(jié)合起來，就形成了段頁式存儲(chǔ)管理方式。在段頁式存儲(chǔ)管理系統(tǒng)中，作業(yè)的地址空間首先被分成若干個(gè)邏輯分段，每段都有自己的段號(hào)，然段頁式系統(tǒng)中，作業(yè)的地址結(jié)構(gòu)包含三部分的內(nèi)容：段號(hào) 頁號(hào) 頁內(nèi)位移量程序員按照分段系統(tǒng)的地址結(jié)構(gòu)將地址分為段號(hào)與段內(nèi)位移量，地址變換機(jī)構(gòu)將段內(nèi)位移量分解為頁號(hào)和頁內(nèi)位移量。為實(shí)現(xiàn)段頁式存儲(chǔ)管理，系統(tǒng)應(yīng)為每個(gè)進(jìn)程設(shè)置一個(gè)段表，包括每段的段號(hào)，該段的頁表始址和頁表長(zhǎng)度。每個(gè)段有自己的頁表，記錄段中的每一頁的頁號(hào)和存放在主存中的物理塊號(hào)。（40）1001個(gè)員工，現(xiàn)在要在公司里面找到最好的羽毛球選手，也就是第一名，每個(gè)人都必須參賽，問至少要比賽多少次才能夠找到最好的羽毛球員工。500組剩下一人，類似于歸并排序的方式，比出冠軍后，讓冠軍之間再比，主要是要想想多余的那一個(gè)選手如何處理，必然要在第一次決出冠軍后加入比賽組。2100個(gè)燈泡，每個(gè)燈泡都是關(guān)著的，第一趟把所有的燈泡燈泡打開，第二趟把偶數(shù)位的燈泡制反（也就是開了的關(guān)掉，關(guān)了的打開），第三趟讓第3,6,9....的燈泡制反 第100趟讓第100個(gè)燈泡制反，問經(jīng)過一百趟以后有多少燈泡亮著答：對(duì)于每盞燈，拉動(dòng)的次數(shù)是奇數(shù)時(shí)，燈就是亮著的，拉動(dòng)的次數(shù)是偶數(shù)時(shí)，燈就是關(guān)著的。3．1——100100個(gè)數(shù)中有哪幾個(gè)數(shù)，約數(shù)的個(gè)數(shù)是奇數(shù)。我們知道一個(gè)數(shù)的約數(shù)都是成對(duì)出現(xiàn)的，只有完全平方數(shù)約數(shù)的個(gè)數(shù)才是奇數(shù)個(gè)。10010盞燈是亮著的。它們的編號(hào)分別是：1、4、9、16、25、36、49、64、81、100。32050020*500個(gè)數(shù)中找出排500的數(shù)答：TOP-KK的最小堆來解決*pszStringintnCharsRotate),ABCDEFG3DEFGABCO（1），O（n）（30）現(xiàn)在有一個(gè)手機(jī)，手機(jī)上的鍵盤上有這樣的對(duì)應(yīng)關(guān)系，2對(duì)應(yīng)"abc",3對(duì)應(yīng)"def". 里面有一個(gè)“樣楊往userlist中查找出對(duì)應(yīng)的用戶名和電話號(hào)碼并返回結(jié)果。C++語言:電話號(hào)碼對(duì)應(yīng)的英語單詞(注意此題的非遞歸做法)#include<iostream>#include<cstdlib>#defineN4電話號(hào)碼個(gè)數(shù)4.5.usingnamespacestd;6.7.charc[][10"","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};//存儲(chǔ)各個(gè)數(shù)字所能代表的字符8.intnumber[N]{2,4,7,9//存儲(chǔ)電話號(hào)碼9.inttotal[10{0033333434}//各個(gè)數(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(