一、簡(jiǎn)答(30分)
1、extern “C”{}是什么含義?用來(lái)解決什么問(wèn)題。(10分)
2、至少說(shuō)出兩種經(jīng)典設(shè)計(jì)模式，并舉例說(shuō)明使用場(chǎng)景，有偽代碼更加.(10分)
3、TCP連接的time_wait是什么狀態(tài)，描述其發(fā)生的場(chǎng)景，說(shuō)明它存在的好處壞處。(10分)
二、算法與程序設(shè)計(jì)(40分)
1.有一個(gè)任務(wù)執(zhí)行器，每天需要定時(shí)執(zhí)行很多任務(wù)(任務(wù)數(shù)N<1000),任務(wù)執(zhí)行器每次只能執(zhí)行一個(gè)任務(wù)而任務(wù)之間存在依賴關(guān)系，如A任務(wù)需要依賴于B任務(wù)完成后才能進(jìn)行，雖然各個(gè)任務(wù)之間依賴關(guān)系復(fù)雜但是各個(gè)任務(wù)之間卻沒(méi)有循環(huán)依賴的問(wèn)題。給出一個(gè)合適的任務(wù)執(zhí)行順序。請(qǐng)?jiān)敿?xì)描述你的算法思路(如需要，可給出偽代碼來(lái)輔助描述)，并分析其時(shí)間和空間復(fù)雜度。(20分)
2.編寫(xiě)函數(shù)：
統(tǒng)計(jì)在某段英文文本完整句子的數(shù)目，文本只包括大小寫(xiě)英文字母、空格、點(diǎn)(.)、逗號(hào)(,)。
完整句子必須包含至少一個(gè)字母并以點(diǎn)結(jié)束。要求：請(qǐng)給出完整代碼，在達(dá)到目標(biāo)的情況下盡量高效，簡(jiǎn)介。(20分)
三、系統(tǒng)設(shè)計(jì)題(30分)
某流量監(jiān)控系統(tǒng)每天生成大量的數(shù)據(jù)記錄，每條記錄 包括url,訪問(wèn)IP,時(shí)間，這些數(shù)據(jù)記錄需要進(jìn)行存儲(chǔ)和維護(hù)，并提供查詢。請(qǐng)?jiān)O(shè)計(jì)一個(gè)系統(tǒng)能夠存儲(chǔ)和維護(hù)1000億條數(shù)據(jù)，實(shí)現(xiàn)實(shí)時(shí)監(jiān)控，并能支持一下兩種查詢：
1.指定任意一個(gè)時(shí)間段(精確到分鐘)和某個(gè)ip,查出該時(shí)段內(nèi)該ip的總訪問(wèn)量。
2.指定任意一個(gè)時(shí)間段(精確到分鐘)和某個(gè)url,查出該時(shí)段內(nèi)對(duì)該url的總訪問(wèn)量。下面是當(dāng)時(shí)筆試的一些思路，具體細(xì)節(jié)不太記得了。
1.很多地方都見(jiàn)到這道題，extern “c”是指將該段代碼以C語(yǔ)言形式進(jìn)行編譯、鏈接。由于C不支持函數(shù)重載，C與C++對(duì)于同一函數(shù)進(jìn)行編譯后在符號(hào)表中保存的函數(shù)名存在差異，故當(dāng)進(jìn)行C、C++混編時(shí)會(huì)出現(xiàn)一些問(wèn)題。
2.記得上學(xué)期還特意去借了一本《設(shè)計(jì)模式》書(shū)來(lái)看，翻是翻了幾下，結(jié)果啥也沒(méi)記住，這題直接空了。對(duì)于設(shè)計(jì)模式記得最深的一句就是“過(guò)分在意設(shè)計(jì)模式會(huì)阻礙你的創(chuàng)新思維”。
3.前段時(shí)間騰訊筆試時(shí)有道選擇題也是考TCP的幾個(gè)狀態(tài)，當(dāng)時(shí)做錯(cuò)了。回來(lái)后看了下TCP的連接和釋放，這次還真用上了。time_wait是TCP釋放四次握手中的一個(gè)狀態(tài)，當(dāng)?shù)谌挝帐滞瓿蓵r(shí)，即客戶端收到來(lái)自服務(wù)器的FIN后，再發(fā)送一個(gè)ACK,客戶便開(kāi)始了time_wait狀態(tài)。
同時(shí)一個(gè)記時(shí)器開(kāi)始記時(shí)，當(dāng)達(dá)到2倍一個(gè)報(bào)文段在因特網(wǎng)中最大的生存期時(shí)代表超時(shí)。如果在超時(shí)前客戶端再次收到FIN，則表示是服務(wù)器重發(fā)的FIN,客戶端需重發(fā)送ACK。
4.依題目得知是求有向圖的一個(gè)拓?fù)湫蛄小?/p>
5.直接掃描一遍。
int count_Pfect_sentence(string str) { int i = 0, cnt = 0, hasOneLetter = 0; while(str[i]) { if(str[i] == '.') { if(hasOneLetter) cnt++; hasOneLetter = 0; } else if(isalpha(str[i])) hasOneLetter = 1; i++; } return cnt; }
6.海量數(shù)據(jù)處理題，當(dāng)時(shí)花了很長(zhǎng)時(shí)間在想這兩題，感覺(jué)沒(méi)有想到什么好的思路。這樣的系統(tǒng)應(yīng)當(dāng)是實(shí)時(shí)性優(yōu)先吧，在時(shí)間空間上首先考慮時(shí)間。
a、建個(gè)二維映射Map[time].bitset\, time代表某一時(shí)間點(diǎn)，將時(shí)間點(diǎn)表示為
時(shí)間秒差數(shù)字作為映射索引。第二維考慮bitset的方式, 建立一個(gè)2^32(整型的最大位數(shù))的數(shù)組(bitset),每一個(gè)bit位0或1代表該位上代表的IP整數(shù)是否訪問(wèn)過(guò). 統(tǒng)計(jì)時(shí)枚舉每個(gè)時(shí)間點(diǎn)，再按位和indexIP進(jìn)行與運(yùn)算進(jìn)行統(tǒng)計(jì)，時(shí)間效率應(yīng)該不差。以保存30天為例，空間為(30243600)(2^32)bit = 2^50B = 1000TB = 1PB
b、時(shí)間以分鐘為單位，第二維直接為IP, 映射值為該分鐘訪問(wèn)量。(302460)(2^32)B= 2^50B = 1000TB = 1PB
7、映射Map[url][time],將url進(jìn)行字符串hash，再進(jìn)行枚舉統(tǒng)計(jì)。
這兩題如果做成兩維映射，內(nèi)存吃不消，既然兩題中的一維是已經(jīng)指定的，變化的只是時(shí)間段，因此可以用一維表示，先預(yù)處理，再進(jìn)行統(tǒng)計(jì)。
閱讀了本文，本站思而學(xué)教育網(wǎng)（cnrencai）筆試頻道，還為你提供以下可能你會(huì)感興趣的筆試題相關(guān)文章：
愛(ài)立信技術(shù)類筆試真題
華邦軟件工程師筆試真題
測(cè)試反應(yīng)能力的筆試題
