百度軟件工程師面試筆試題目解析及經(jīng)驗(yàn)介紹

1、百度軟件工程師面試筆試題目解析及經(jīng)驗(yàn)介紹1 編程:用C語言實(shí)現(xiàn)一個(gè)revert函數(shù),它的功能是將輸入的字符串在原串上倒序后返回。2 編程:用C語言實(shí)現(xiàn)函數(shù)void * memmove(void *dest,const void *src,size_t n。memmove函數(shù)的功能是拷貝src所指的內(nèi)存內(nèi)容前n個(gè)字節(jié)到dest所指的地址上。3 英文拼寫糾錯(cuò):在用戶輸入英文單詞時(shí),經(jīng)常發(fā)生錯(cuò)誤,我們需要對(duì)其進(jìn)行糾錯(cuò)。假設(shè)已經(jīng)有一個(gè)包含了正確英文單詞的詞典,請(qǐng)你設(shè)計(jì)一個(gè)拼寫糾錯(cuò)的程序。(1請(qǐng)描述你解決這個(gè)問題的思路;(2請(qǐng)給出主要的處理流程,算法,以及算法的復(fù)雜度;(3請(qǐng)描述可能的改進(jìn)(改進(jìn)的方向如

2、效果,性能等等,這是一個(gè)開放問題。4 尋找熱門查詢:搜索引擎會(huì)通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來,每個(gè)查詢串的長度為1-255字節(jié)。假設(shè)目前有一千萬個(gè)記錄,這些查詢串的重復(fù)度比較高,雖然總數(shù)是1千萬,但如果除去重復(fù)后,不超過3百萬個(gè)。一個(gè)查詢串的重復(fù)度越高,說明查詢它的用戶越多,也就是越熱門。請(qǐng)你統(tǒng)計(jì)最熱門的10個(gè)查詢串,要求使用的內(nèi)存不能超過1G。(1請(qǐng)描述你解決這個(gè)問題的思路;(2請(qǐng)給出主要的處理流程,算法,以及算法的復(fù)雜度。5 集合合并:給定一個(gè)字符串的集合,格式如:aaa bbb ccc,bbb ddd,eee fff, ggg,ddd hhh 要求將其中交集不為空的

3、集合合并,要求合并完成后的集合之間無交集,例如上例應(yīng)輸出aaa bbb ccc ddd hhh,eee fff,ggg(1請(qǐng)描述你解決這個(gè)問題的思路;(2請(qǐng)給出主要的處理流程,算法,以及算法的復(fù)雜度(3請(qǐng)描述可能的改進(jìn)(改進(jìn)的方向如效果,性能等等,這是一個(gè)開放問題。/1 題char *revert(char * strint n=strlen(str;int i=0;char c;for(i=0;i c=str;str=strn-i;strn-i=c;return str;/2 題void * memmove(void *dest,const void *src,size_t nassert(

4、dest!=0&&(src!=0;char * temp=(char * dest;char * ss=(char * src;int i=0;for(;i *temp =*ss ;return temp;/3 題(1思路: 字典以字母鍵樹組織,在用戶輸入同時(shí)匹配(2 流程:每輸入一個(gè)字母:沿字典樹向下一層,a若可以順利下行,則繼續(xù)至結(jié)束,給出結(jié)果;b若該處不能匹配,糾錯(cuò)處理,給出拼寫建議,繼續(xù)至a;算法:字典采用27叉樹組織,每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)字母,查找就是一個(gè)字母一個(gè)字母匹配.算法時(shí)間就是單詞的長度k.情況:當(dāng)輸入的最后一個(gè)字母不能匹配時(shí)就提示出錯(cuò),簡化出錯(cuò)處理,動(dòng)態(tài)提示可能

5、處理方法:(a當(dāng)前字母前缺少了一個(gè)字母:搜索樹上兩層到當(dāng)前的匹配作為建議;(b當(dāng)前字母拼寫錯(cuò)誤:當(dāng)前字母的鍵盤相鄰作為提示;(只是簡單的描述,可以有更多的根據(jù)分析字典特征和用戶單詞已輸入部分選擇(a,(b處理復(fù)雜性分析:影響算法的效率主要是字典的實(shí)現(xiàn)與糾錯(cuò)處理(a字典的實(shí)現(xiàn)已有成熟的算法,改進(jìn)不大,也不會(huì)成為瓶頸;(b糾錯(cuò)策略要簡單有效,如前述情況,是線性復(fù)雜度;(3改進(jìn)策略選擇最是重要,可以采用統(tǒng)計(jì)學(xué)習(xí)的方法改進(jìn)。/4 題(1思路:用哈希做(2 首先逐次讀入查詢串,算哈希值,保存在內(nèi)存數(shù)組中,同時(shí)統(tǒng)計(jì)頻度(注意值與日志項(xiàng)對(duì)應(yīng)關(guān)系 選出前十的頻度,取出對(duì)應(yīng)的日志串,簡單不過了。哈希的設(shè)計(jì)是關(guān)鍵

6、。/5 題(1思路:先將集合按照大小排列后,優(yōu)先考慮小的集合是否與大的集合有交集。有就合并,如果小集合與所有其他集合都沒有交集,則獨(dú)立。獨(dú)立的集合在下一輪的比較中不用考慮。這樣就可以盡量減少字符串的比較次數(shù)。當(dāng)所有集合都獨(dú)立的時(shí)候,就終止。(2處理流程:1.將集合按照大小排序,組成集合合并待處理列表2.選擇最小的集合,找出與之有交集的集合,如果有,合并之;如果無,則與其它集合是獨(dú)立集合,從待處理列表中刪除。算法:1。將集合按照大小從小到大排序,組成待處理的集合列表。2。取出待處理集合列表中最小的集合,對(duì)于集合的每個(gè)元素,依次在其他集合中搜索是否有此元素存在:1>若存在,則將此小集合與大集

7、合合并,并根據(jù)大小插入對(duì)應(yīng)的位置。轉(zhuǎn)3。2>若不存在,則在該集合中取下一個(gè)元素。如果無下一個(gè)元素,即所有元素都不存在于其他集合。則表明此集合獨(dú)立,從待處理集合列表中刪除。并加入結(jié)果集合列表。轉(zhuǎn)3。3。如果待處理集合列表不為空,轉(zhuǎn)2。如果待處理集合列表為空,成功退出,則結(jié)果集合列表就是最終的輸出。算法復(fù)雜度分析:假設(shè)集合的個(gè)數(shù)為n,最大的集合元素為m 排序的時(shí)間復(fù)雜度可以達(dá)到n*log(n 然后對(duì)于元素在其他集合中查找,最壞情況下為(n-1*m 查找一個(gè)集合是否與其他集合有交集的最壞情況是m*m*(n-1 合并的時(shí)間復(fù)雜度不會(huì)超過查找集合有交集的最壞情況。所以最終最壞時(shí)間復(fù)雜度為O(m*m

8、*n*n需要說明的是:此算法的平均時(shí)間復(fù)雜度會(huì)很低,因?yàn)闊o論是查找還是合并,都是處于最壞情況的概率很小,而且排序后優(yōu)先用最小集合作為判斷是否獨(dú)立的對(duì)象,優(yōu)先與最大的集合進(jìn)行比較,這些都最大的回避了最壞情況。(3可能的改進(jìn):首先可以實(shí)現(xiàn)將每個(gè)集合里面的字符串按照字典序進(jìn)行排列,這樣就可以將查找以及合并的效率增高。另外,可能采取恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)也可以將查找以及合并等操作的效率得到提高。、1此題10分對(duì)任意輸入的正整數(shù)N,編寫C程序求N!的尾部連續(xù)0的個(gè)數(shù),并指出計(jì)算復(fù)雜度。如:18!=6402373705728000,尾部連續(xù)0的個(gè)數(shù)是3。(不用考慮數(shù)值超出計(jì)算機(jī)整數(shù)界限的問題2此題10分編寫一個(gè)C

9、語言函數(shù),要求輸入一個(gè)url,輸出該url是首頁、目錄頁或者其他url如下形式叫做首頁:如下形式叫做目錄頁:請(qǐng)注意:aurl有可能帶http頭也有可能不帶b動(dòng)態(tài)url(即含有"?"的url的一律不算目錄頁,如:另:如果你會(huì)linux,請(qǐng)用linux下的grep命令實(shí)現(xiàn)第2題的功能(附加5分。3此題40分如果必須從網(wǎng)頁中區(qū)分出一部分"重要網(wǎng)頁"(例如在10億中選8億,比其他網(wǎng)頁更值得展現(xiàn)給用戶,請(qǐng)?zhí)岢鲆环N方案。4此題40分假設(shè)有10億網(wǎng)頁已經(jīng)被我們存下來,并提供如下信息:網(wǎng)頁全文(即網(wǎng)頁的源碼、全文長度、網(wǎng)頁正文(即網(wǎng)頁中提取的主體文字、正文長度,以及其他

10、網(wǎng)頁提取物等,現(xiàn)在希望去掉其中的重復(fù)網(wǎng)頁,請(qǐng)?zhí)岢隹尚械姆桨?計(jì)算出每個(gè)網(wǎng)頁對(duì)應(yīng)的重復(fù)度,你可以自己對(duì)網(wǎng)頁重復(fù)下定義,也可以提出需要哪些更多的網(wǎng)頁提取物來實(shí)現(xiàn)更好的去重復(fù)方案。、好久沒來了。發(fā)生了一些事情,其間的心情已不是幾行文字所能表述的了。終于明白有些事情,并不是自己努力就一定能圓滿的;有些事情,是我控制不了的。唉,不提也罷!說說今天去百度筆試的經(jīng)歷吧部門:百度搜索應(yīng)用技術(shù)部。地點(diǎn):海淀南路銀科大廈(海淀圖書城西臨18層。時(shí)間:2005/6/15 10:00-11:20 am九點(diǎn)從實(shí)驗(yàn)室出發(fā),725到知春路,轉(zhuǎn)735,到海淀橋下車,9:50到達(dá)百度。在725的車上碰到一男士索要手機(jī)號(hào),說自己

11、認(rèn)識(shí)信息產(chǎn)業(yè)部的部長楊澤民先生,以居高臨下的姿態(tài)把手機(jī)號(hào)給了他-_-!在百度前臺(tái)見到了一直幫我安排筆試的楊韞敏jj,不是想象中的HR形象,而是一副干練的女IT的樣子跳躍的靈魂很快,給我找了一間小會(huì)議室,只有一張桌子,兩把椅子,還幫我開了燈,關(guān)門,走人,我開始看題。冷汗也開始流。翻了一下三頁紙的筆試題,只有很少的傳說中的Linux題目,其他的全是C、數(shù)據(jù)結(jié)構(gòu)、算法編程的題。第一反應(yīng):走人!但又覺得對(duì)不起陳jj,關(guān)鍵的是我已經(jīng)在筆試題上寫了姓名和學(xué)校了,sign,總的為自己的名字和學(xué)校負(fù)責(zé)吧,他們是無辜的。如此斗爭良久,決定堅(jiān)持下來。題目大致是這樣的:第一部分選擇題:有幾道網(wǎng)絡(luò)相關(guān)的題目,巨簡單,

12、比如第一題是TCP、RIP、IP、FTP中哪個(gè)協(xié)議是傳輸層的.。有一道linux的chown使用題目。其他的全是數(shù)據(jù)結(jié)構(gòu)的題目!什么鏈,表,碼的,不知所云跳躍的靈魂唉,我可以沒有學(xué)過數(shù)據(jù)結(jié)構(gòu)的人吶!真殘忍!這一部分迅速猜完!第二部分簡答題:1、在linux中如何編譯C程序,使之成為可執(zhí)行文件?如何調(diào)試?答案:1檢查程序中.h文件所在的目錄,將其加入系統(tǒng)PATH中;2執(zhí)行C編譯:#gcc 源文件名 -o 目標(biāo)文件名執(zhí)行C+編譯:#g+ 源文件名 -o 目標(biāo)文件名3改變目標(biāo)文件為可執(zhí)行文件:#chmod +x 目標(biāo)文件名4如需將多個(gè)可執(zhí)行文件連續(xù)執(zhí)行,可生成批處理文件:#vi 批處理文件名可執(zhí)行文

13、件1可執(zhí)行文件2.最后將該批處理文件屬性該位可執(zhí)行。調(diào)試:在編譯時(shí)使用-g參數(shù),就可以使用gdb進(jìn)行調(diào)試。2、寫出內(nèi)存分配和釋放的函數(shù),并指出區(qū)別。答案:C語言的標(biāo)準(zhǔn)內(nèi)存分配函數(shù):malloc,calloc,realloc,free等。malloc與calloc的區(qū)別為1塊與n塊的區(qū)別:malloc調(diào)用形式為(類型*malloc(size:在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一塊長度為“size”字節(jié)的連續(xù)區(qū)域,返回該區(qū)域的首地址。calloc調(diào)用形式為(類型*calloc(n,size:在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配n塊長度為“size”字節(jié)的連續(xù)區(qū)域,返回首地址。realloc調(diào)用形式為(類型*reallo

14、c(*ptr,size:將ptr內(nèi)存大小增大到size。free的調(diào)用形式為free(void*ptr:釋放ptr所指向的一塊內(nèi)存空間。C+中為new/delete函數(shù)。3、寫出socket函數(shù),并指出其功能。socket(:建立socket通信描述符;bind(:將套接字和機(jī)器上的一定的端口關(guān)聯(lián);connect(:連接到遠(yuǎn)程主機(jī);listen(:使套接字做好連接的準(zhǔn)備,規(guī)定等待服務(wù)請(qǐng)求隊(duì)列的長度;accept(:接受連接,一旦有客戶端發(fā)出連接,accept返回客戶地址信息和一個(gè)新的sock;有了這個(gè)新的sock,雙方就可以開始收發(fā)數(shù)據(jù):send(和recv(:用于流式套接字或者數(shù)據(jù)套接字的通

15、訊;sendto(和recvfrom(:用于無連接的數(shù)據(jù)報(bào)套接字;close(:關(guān)閉套接字;shutdown(:選擇性的關(guān)閉套接字,可以只允許某一方向的通訊關(guān)閉;getpeername(:返回流式套接字時(shí)對(duì)端peer信息;gethostname(:返回程序所運(yùn)行的機(jī)器的主機(jī)名字;gethostbyname(:返回本機(jī)IP;第三部分編程題:1、從文件中讀取字符串?dāng)?shù)據(jù),反序顯示并大小寫轉(zhuǎn)換。2、給定26字母表以及對(duì)應(yīng)的密碼表,編程實(shí)現(xiàn)加密及解密功能。第四部分思考題(正是傳說中的字典糾錯(cuò)題:用戶在輸入英文單詞時(shí)經(jīng)常出錯(cuò),現(xiàn)對(duì)其進(jìn)行就錯(cuò)。給定一個(gè)正確的英文詞典,考慮糾錯(cuò)實(shí)現(xiàn)。1指出思路。2流程、算法難

16、易程度及可能的改進(jìn)策略。不過陳jj沒有給我答題紙,只好拿試題的背面做了答題紙兼草稿紙-_-!說實(shí)話有些題目是很基礎(chǔ)的,就是沒背過。不知怎么搞得,巨潦草。實(shí)驗(yàn)室參加過筆試的通同學(xué)都是憋著勁做了兩個(gè)多小時(shí)才答完,而我只一個(gè)小時(shí)就完了,唉,正好說明肚子里只有別人一半的東西看著潦草而不著邊際的答題,決定在最后給陳jj寫段話,大意就是感謝她幫我挽回了一次筆試的機(jī)會(huì),但我的表現(xiàn)很遺憾等等.然后交卷走人沒想到交了試卷沒讓我走,等了大約30分鐘的樣子,有個(gè)很深沉的gg 來看我的卷子跳躍的靈魂-_-!我顫顫的跟他說我很長時(shí)間沒有接觸C了,當(dāng)時(shí)脖子都紅了,真覺得丟人。gg看了一下,沒有很鄙視的樣子,問我有沒有帶簡

17、歷。當(dāng)然木有啦答應(yīng)回來給他發(fā)個(gè)電子版的,然后趕緊跑人了!、題目大致是這樣的:第一部分選擇題:有幾道網(wǎng)絡(luò)相關(guān)的題目,巨簡單,比如第一題是TCP、RIP、IP、FTP 中哪個(gè)協(xié)議是傳輸層的.。有一道linux的chown使用題目。其他的全是數(shù)據(jù)結(jié)構(gòu)的題目!什么鏈,表,碼的,不知所云.唉,我可以沒有學(xué)過數(shù)據(jù)結(jié)構(gòu)的人吶!真殘忍!這一部分迅速猜完!第二部分簡答題:1、在linux中如何編譯C程序,使之成為可執(zhí)行文件?如何調(diào)試?答案:1檢查程序中.h文件所在的目錄,將其加入系統(tǒng)PATH中;2執(zhí)行C編譯:#gcc 源文件名 -o 目標(biāo)文件名執(zhí)行C+編譯:#g+ 源文件名 -o 目標(biāo)文件名3改變目標(biāo)文件為可執(zhí)

18、行文件:#chmod +x 目標(biāo)文件名4如需將多個(gè)可執(zhí)行文件連續(xù)執(zhí)行,可生成批處理文件:#vi 批處理文件名可執(zhí)行文件1可執(zhí)行文件2.最后將該批處理文件屬性該位可執(zhí)行。調(diào)試:在編譯時(shí)使用-g參數(shù),就可以使用gdb進(jìn)行調(diào)試。2、寫出內(nèi)存分配和釋放的函數(shù),并指出區(qū)別。答案:C語言的標(biāo)準(zhǔn)內(nèi)存分配函數(shù):malloc,calloc,realloc,free等。malloc與calloc的區(qū)別為1塊與n塊的區(qū)別:malloc調(diào)用形式為(類型*malloc(size:在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一塊長度為“size”字節(jié)的連續(xù)區(qū)域,返回該區(qū)域的首地址。calloc調(diào)用形式為(類型*calloc(n,size:在

19、內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配n塊長度為“size”字節(jié)的連續(xù)區(qū)域,返回首地址。realloc調(diào)用形式為(類型*realloc(*ptr,size:將ptr內(nèi)存大小增大到size。free的調(diào)用形式為free(void*ptr:釋放ptr所指向的一塊內(nèi)存空間。C+中為new/delete函數(shù)。3、寫出socket函數(shù),并指出其功能。socket(:建立socket通信描述符;bind(:將套接字和機(jī)器上的一定的端口關(guān)聯(lián);connect(:連接到遠(yuǎn)程主機(jī);listen(:使套接字做好連接的準(zhǔn)備,規(guī)定等待服務(wù)請(qǐng)求隊(duì)列的長度;accept(:接受連接,一旦有客戶端發(fā)出連接,accept返回客戶地址信息和一個(gè)

20、新的sock;有了這個(gè)新的sock,雙方就可以開始收發(fā)數(shù)據(jù):send(和recv(:用于流式套接字或者數(shù)據(jù)套接字的通訊;sendto(和recvfrom(:用于無連接的數(shù)據(jù)報(bào)套接字;close(:關(guān)閉套接字;shutdown(:選擇性的關(guān)閉套接字,可以只允許某一方向的通訊關(guān)閉;getpeername(:返回流式套接字時(shí)對(duì)端peer信息;gethostname(:返回程序所運(yùn)行的機(jī)器的主機(jī)名字;gethostbyname(:返回本機(jī)IP;第三部分編程題:1、從文件中讀取字符串?dāng)?shù)據(jù),反序顯示并大小寫轉(zhuǎn)換。2、給定26字母表以及對(duì)應(yīng)的密碼表,編程實(shí)現(xiàn)加密及解密功能。第四部分思考題(正是傳說中的字典糾

21、錯(cuò)題:用戶在輸入英文單詞時(shí)經(jīng)常出錯(cuò),現(xiàn)對(duì)其進(jìn)行就錯(cuò)。給定一個(gè)正確的英文詞典,考慮糾錯(cuò)實(shí)現(xiàn)。1指出思路。2流程、算法難易程度及可能的改進(jìn)策略。一道算法題目答案int Replace(Stringtype &S,Stringtype T,Stringtype V;/將串S中所有子串T 替換為V,并返回置換次數(shù)for(n=0,i=1;i=Strlen(S-Strlen(T+1;i+ /注意i的取值范圍if(!StrCompare(SubString(S,i,Strlen(T,T /找到了與T匹配的子串 /分別把T的前面和后面部分保存為head和tailStrAssign(head,SubSt

22、ring(S,1,i-1;StrAssign(tail,SubString(S,i+Strlen(T,Strlen(S-i-Strlen(T+1;StrAssign(S,Concat(head,V;StrAssign(S,Concat(S,tail; /把head,V,tail連接為新串i+=Strlen(V; /當(dāng)前指針跳到插入串以后n+;/ifreturn n;/Replace分析:i+=Strlen(V;這一句是必需的,也是容易忽略的.如省掉這一句,則在某些情況下,會(huì)引起不希望的后果,雖然在大多數(shù)情況下沒有影響.請(qǐng)思考:設(shè)S='place', T='ace'

23、;, V='face',則省掉i+=Strlen(V;運(yùn)行時(shí)會(huì)出現(xiàn)什么結(jié)果? (無限遞歸face百度2005年的筆試題1.實(shí)現(xiàn)void delete_char(char * str, char ch;把str中所有的ch刪掉2.把字符串S中所有A子串換成B,這個(gè)沒給函數(shù)原型3.搜索引擎的日志要記錄所有查詢串,有一千萬條查詢,不重復(fù)的不超過三百萬要統(tǒng)計(jì)最熱門的10條查詢串. 內(nèi)存<1G. 字符串長0-255(1 主要解決思路/具體用詞和原題不大一樣(2 算法及其復(fù)雜度分析4.有字典,設(shè)計(jì)一個(gè)英文拼寫糾正算法(1 思想(2 算法及復(fù)雜度(3 改進(jìn)5. aaa, bb, ccc

24、, dd , bbb, ff , gg 等一些字符串的集合要求把交集不為空的集合并起來,如上例會(huì)得到 aaa, bb, ccc, dd, ff , gg (1 思想(2 算法及復(fù)雜度(3 改進(jìn)、一、選擇題:15分共10題1.一個(gè)含有n個(gè)頂點(diǎn)和e條邊的簡單無向圖,在其鄰接矩陣存儲(chǔ)結(jié)構(gòu)中共有_個(gè)零元素。2._是面向?qū)ο蟪绦蛟O(shè)計(jì)語言中的一種機(jī)制。這種機(jī)制實(shí)現(xiàn)了方法的定義與具體的對(duì)象無關(guān),而對(duì)方法的調(diào)用則可以關(guān)聯(lián)于具體的對(duì)象。A.繼承(InhertanceB.模板(TemplateC.對(duì)象的自身引用(Self-ReferenceD.動(dòng)態(tài)綁定(Dynamic Binding3.應(yīng)用層DNS協(xié)議主要用于實(shí)

25、現(xiàn)網(wǎng)絡(luò)服務(wù)功能.A. IP地址到網(wǎng)絡(luò)設(shè)備名字的映射B. IP地址到網(wǎng)絡(luò)硬件地址的映射C. 網(wǎng)絡(luò)設(shè)備名字到IP地址的映射D. 網(wǎng)絡(luò)硬件地址到IP地址的映射4.linux默認(rèn)情況下,一個(gè)進(jìn)程最多能打開多少文件?B. 128C. 512D. 1024struct s1 char ch, *ptr;union short a, b;unsigned int c:2, d:1;struct s1 *next;的大小是_:A. 12字節(jié)D. 24字節(jié)6.任何一個(gè)基于"比較"的內(nèi)部排序的算法,若對(duì)6個(gè)元素進(jìn)行排序,則在最壞情況下所需的比較次數(shù)至少為_。A 共享內(nèi)存B 信號(hào)量C線程局部存儲(chǔ)

26、D 消息隊(duì)列8.下面程序,求count的值int func(xint count= 0;x=9999;while(xCount +;x = x&(x-1;return count;A 8;B 10;C 5;D 119.使用malloc系統(tǒng)調(diào)用分配的內(nèi)存是在_ 上分配的?A 棧;B bss;C 物理內(nèi)存;D 堆10.最壞情況下,合并兩個(gè)大小為n的已排序數(shù)組所需要的比較次數(shù)_C.2n+1二、簡答題:20分,共3題1.(5分下面這段代碼是把中英文混合字符串(漢字用兩個(gè)字節(jié)表示,特點(diǎn)是第一個(gè)字節(jié)的最高位為1中的大寫字母轉(zhuǎn)化為小寫字母,請(qǐng)找出其中的bug,注意各種異常情況。for (char *

27、piterator = szWord; *piterator != 0; piterator+if (*piterator & 0x80 != 0piterator+;else if (*piterator >= 'A' && *piterator <= 'Z'piterator += 32;2.(5分對(duì)給定的上億條無序的url,請(qǐng)按照domain、site以及path分別排序,并請(qǐng)指出排序過程中可能會(huì)遇到的哪些問題?如何提高效率?例如:3.(10分某型CPU的一級(jí)數(shù)據(jù)緩存大小為16K字節(jié),cache塊大小為64字節(jié);二級(jí)緩存

28、大小為256K字節(jié),cache塊大小為4K字節(jié),采用二路組相聯(lián)。經(jīng)測試,下面兩段代碼運(yùn)行時(shí)效率差別很大,請(qǐng)分析哪段代碼更好,以及可能的原因。為了進(jìn)一步提高效率,你還可以采取什么辦法?A段代碼int matrix102315;const char *str = "this is a str"int i, j, tmp, sum = 0;tmp = strlen(str;for(i = 0; i < 1023; i+ for(j = 0; j < 15; j+ sum += matrixij + tmp;B段代碼int matrix102517;const char

29、 *str = "this is a str"int i, j, sum = 0;for(i = 0; i < 17; i+ for(j = 0; j < 1025; j+ sum += matrixji + strlen(str;三、編程題:30分共1題注意:要求盡可能提供完整代碼,如果可以編譯運(yùn)行酌情加分。1.內(nèi)存中有一個(gè)長數(shù)組,條目數(shù)為10萬,數(shù)組單元為結(jié)構(gòu)體struct array, sizeof(struct array為512字節(jié)。結(jié)構(gòu)有一int型成員變量weight?，F(xiàn)需要取得按weight值從大到小排序的前500個(gè)數(shù)組單元,請(qǐng)實(shí)現(xiàn)算法,要求效率盡

30、可能高。四、設(shè)計(jì)題:35分共1題注意:請(qǐng)盡可能詳細(xì)描述你的數(shù)據(jù)結(jié)構(gòu)、系統(tǒng)架構(gòu)、設(shè)計(jì)思路等,建議多寫一些偽代碼或者流程說明。1.請(qǐng)?jiān)O(shè)計(jì)一個(gè)字典。以字符串為索引,存儲(chǔ)用戶定義的定長結(jié)構(gòu)。要求有增、刪、查、改的功能。已經(jīng)給定一個(gè)函數(shù),可以由字符串映射到一個(gè)簽名,每個(gè)簽名由兩個(gè)unsigned int類型組成。假設(shè)每一個(gè)字符串能夠?qū)?yīng)唯一的一個(gè)簽名,完全沒有重復(fù)(或者重復(fù)的概率可以忽略,并且簽名分布足夠均勻。請(qǐng)描述你的數(shù)據(jù)結(jié)構(gòu)?內(nèi)存如何申請(qǐng)?增、刪、查、改的功能如何實(shí)現(xiàn)?如果操作很頻繁,該如何優(yōu)化?、經(jīng)過在線筆試、兩輪電話面試,今天上午收到了百度的拒信,我的百度求職算是告一段落了從百度校園招聘開始,我

31、就投了一份簡歷。在別人都有在線筆試機(jī)會(huì)的時(shí)候,我卻沒有任何消息。聽說師兄可以給推薦,我就又通過內(nèi)部推薦的方式投遞了一次,這次很快就有消息了拒信。那時(shí)基本上就放棄了百度?？墒谴蟾?0多天以后,我投遞的第一份簡歷有消息了通知我在線筆試。經(jīng)過精心準(zhǔn)備,筆試題答得還湊合。過了幾天給我來了封郵件告知我筆試通過,會(huì)找時(shí)間安排電話面試。又過了好幾天,我正在剃頭的時(shí)候接到百度電話,約了第二天下午三點(diǎn)電話面試。心情異常興奮,回到寢室拼命復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)并收集百度面試題型臨陣磨槍呵呵。百度的面試氛圍很是輕松，讓你很快就覺得是在聊天而不是面試。第一 輪主要是在針對(duì)我的在線筆試的題目進(jìn)行提問和分析，主要講的是做題的思 路和改進(jìn)的方法。面試時(shí)間大概有半個(gè)小時(shí)，覺得應(yīng)該有下一輪。 果然上個(gè)星期五晚上接到了百度技術(shù)經(jīng)理的電話，自稱姓劉。在前一天 我同學(xué)也是這個(gè)時(shí)候接到百度第二面電話，看來是同一個(gè)人，后來的面試內(nèi) 容證實(shí)了是同一個(gè)人。面試過程大概如下： 1、介紹一下項(xiàng)目。 2、提了一個(gè)問題：上千萬條記錄，統(tǒng)計(jì)出重復(fù)記錄最多的前 N 條。 3、一個(gè)概率題：54 張撲克牌，除去兩張大小王剩