1、單項(xiàng)選擇題 1.1 如果把傳輸速率定義為單位時(shí)間內(nèi)傳送的信息量(以字節(jié)計(jì)算)多少。關(guān)于一下幾種典型的數(shù)據(jù)傳輸速率: 1.使用USB2.0閃存盤(pán),往USB閃存盤(pán)上拷貝文件的數(shù)據(jù)傳輸速率 2.使用100M以太網(wǎng),在局域網(wǎng)內(nèi)拷貝大文件時(shí)網(wǎng)絡(luò)上的數(shù)據(jù)傳輸速率 3.使用一輛卡車(chē)?yán)?000塊單塊1TB裝滿數(shù)據(jù)的硬盤(pán),以100km/h的速度從上海到天津(100km)一趟所等價(jià)的數(shù)據(jù)傳輸帶寬 4.使用電腦播放MP3,電腦的PCI總線到聲卡的數(shù)據(jù)傳輸速率 在通常情況下,關(guān)于這幾個(gè)傳輸速率的排序正確的是: A.4<1<2<3 B.1<4<2<3 C.4<1<3<2 D.1<4<3<2 1.2 對(duì)以下程序,正確的輸出結(jié)果是 #define SUB(x,y) x-y #define ACCESS_BEFORE(element,offset,value) *SUB(&element, offset) =value int main() { int array[10]= {1,2,3,4,5,6,7,8,9,10}; int i; ACCESS_BEFORE(array[5], 4, 6); printf("array: "); for (i=0; i<10; ++i){ printf("%d", array[i]); } printf("\n"); return (0); }A.array: 1 6 3 4 5 6 7 8 9 10 B.array: 6 2 3 4 5 6 7 8 9 10 C.程序可以正確編譯連接,但是運(yùn)行時(shí)會(huì)崩潰 D.程序語(yǔ)法錯(cuò)誤,編譯不成功 1.3 在區(qū)間[-2, 2]里任取兩個(gè)實(shí)數(shù),它們的和>1的概率是: A.3/8 B.3/16 C.9/32 D.9/64 1.4 小組賽,每個(gè)小組有5支隊(duì)伍,互相之間打單循環(huán)賽,勝一場(chǎng)3分,平一場(chǎng)1分,輸一場(chǎng)不得分,小組前三名出線。平分抽簽。問(wèn)一個(gè)隊(duì)少拿幾分就有理論上的出線希望: A.1 B.2 C.3 D.4 1.5 用二進(jìn)制來(lái)編碼字符串“abcdabaa”,需要能夠根據(jù)編碼,解碼回原來(lái)的字符串,少需要多長(zhǎng)的二進(jìn)制字符串? A.12 B.14 C.18 D.24 1.6 10個(gè)相同的糖果,分給三個(gè)人,每個(gè)人至少要得一個(gè)。有多少種不同分法 A.33 B.34 C.35 D.36 1.7 下列程序段,循環(huán)體執(zhí)行次數(shù)是: y=2 while(y<=8) y=y+y; A.2 B.16 C.4 D.3 1.8 下面哪種機(jī)制可以用來(lái)進(jìn)行進(jìn)程間通信? A.Socket B.PIPE C.SHARED MEMORY D.以上皆可 1.9 下列關(guān)于編程優(yōu)化的說(shuō)法正確的是: A.使用編譯器的優(yōu)化選項(xiàng)(如-O3)后程序性能一定會(huì)獲得提高 B.循環(huán)展開(kāi)得越多越徹底,程序的性能越好 C.寄存器分配能夠解決程序中的數(shù)據(jù)依賴(lài)問(wèn)題 D.現(xiàn)代主流C/C++編譯器可以對(duì)簡(jiǎn)單的小函數(shù)進(jìn)行自動(dòng)Iinline 1.10 一下程序是用來(lái)計(jì)算兩個(gè)非負(fù)數(shù)之間的大公約數(shù): long long gcd(long long x, long long y) { if( y==0) return 0; else return gcd (y, x%y); }我們假設(shè)x,y中大的那個(gè)數(shù)的長(zhǎng)度為n,基本運(yùn)算時(shí)間復(fù)雜度為O(1),那么該程序的時(shí)間復(fù)雜度為: A.O(1) B.O(logn) C.O(n) D.O(n^2) 2、程序設(shè)計(jì)與算法(2.1,2.2為編程題,2.3為算法設(shè)計(jì)題,只需設(shè)計(jì)思路和關(guān)鍵步驟偽代碼) 2.1 寫(xiě)函數(shù),輸出前N個(gè)素?cái)?shù)。不需要考慮整數(shù)溢出問(wèn)題,也不需要使用大數(shù)處理算法。 2.2 長(zhǎng)度為n的數(shù)組亂序存放著0至n-1. 現(xiàn)在只能進(jìn)行0與其他數(shù)的swap,請(qǐng)?jiān)O(shè)計(jì)并實(shí)現(xiàn)排序。 2.3 給定一個(gè)原串和目標(biāo)串,能對(duì)源串進(jìn)行如下操作: 1.在給定位置插入一個(gè)字符 2.替換任意字符 3.刪除任意字符 要求寫(xiě)一個(gè)程序,返回少的操作數(shù),使得源串進(jìn)行這些操作后等于目標(biāo)串。源串和目標(biāo)串長(zhǎng)度都小于2000。 —— 以下是我根據(jù)各種來(lái)源總結(jié)的參考答案: 1.1 A USB 2.0的理論傳輸極限是480Mbps[2],但是按照這個(gè)速率就沒(méi)有選項(xiàng)可選了-.-,所以猜測(cè)應(yīng)該認(rèn)為是普通U盤(pán)寫(xiě)數(shù)據(jù)的6MB/s,即48Mbps; 100M以太網(wǎng)的速率就是100Mbps; 卡車(chē)?yán)脖P(pán),1000x1000x8/3600=2222Mbps,這個(gè)應(yīng)該是快的; MP3在256kbps碼率下也平均只有1分鐘2MB,所以不會(huì)超過(guò)0.3Mbps,所以一定是慢的。 1.2 D 這道題大家走出考場(chǎng)后爭(zhēng)議非常大。咱啥也不說(shuō),直接進(jìn)mingw跑一下gcc:
gcc提示的錯(cuò)誤是“賦值號(hào)的左邊操作數(shù)需要一個(gè)左值”。其原因是調(diào)用宏的那句被預(yù)處理器替換成了: *&array[5]-4 =6; 由于減號(hào)比賦值優(yōu)先級(jí)高,因此先處理減號(hào);由于減號(hào)返回一個(gè)數(shù)而不是合法的左值,所以編譯報(bào)錯(cuò)。 1.3 C 這道題我是蒙對(duì)的-.- 標(biāo)準(zhǔn)做法是先畫(huà)出y=1-x的線,上側(cè)陰影部分就是y>1-x,其所占比例為9/32:
1.4 B 這道題我從A開(kāi)始湊勝負(fù)表,直到B湊出結(jié)果就OK了。 1.5 B 這道題需要對(duì)abcd進(jìn)行Huffman編碼。首先根據(jù)權(quán)值建立Huffman樹(shù),得到優(yōu)編碼: a=0, b=10, c=110, d=111 然后數(shù)一下就行了。 1.6 D 這道題我是窮舉的orz……一共這么幾種情況: 118,127,136,145; 226,235,244; 334; 然后有數(shù)字重復(fù)的算3種排列,不重復(fù)的算6種排列,共計(jì)4×3+4×6=36種。 1.7 D 這題很基本了。 1.8 D 一般學(xué)過(guò)操作系統(tǒng)這門(mén)課的都會(huì)吧,而且個(gè)人覺(jué)得D這個(gè)選項(xiàng)的出現(xiàn)不符合Google風(fēng)格。 1.9 D 這題其實(shí)很好做,因?yàn)镈肯定是對(duì)的,而且ABC的言論太絕對(duì)。但如果一定要給出解釋的話…… A選項(xiàng)的優(yōu)化只能針對(duì)代碼本身,純系統(tǒng)調(diào)用什么的是不會(huì)性能提升的(當(dāng)然也不會(huì)下降), B選項(xiàng)我覺(jué)得是在并行優(yōu)化方面,好的編譯器可以從循環(huán)中發(fā)掘并行性,展開(kāi)之后就不行了, C選項(xiàng)有點(diǎn)說(shuō)不清。消除數(shù)據(jù)依賴(lài)主要有兩個(gè)方法,一種是SSA,即靜態(tài)單賦值[3],這是通過(guò)對(duì)變量進(jìn)行重命名實(shí)現(xiàn)的,嚴(yán)格的說(shuō)應(yīng)該叫“寄存器重命名”[4]而不是“寄存器分配”;另外一種是調(diào)換指令順序,這種只要不是真相關(guān)(寫(xiě)后讀,RAW)的話都可以消除掉,也不屬于寄存器分配。所以感覺(jué)不應(yīng)該選這個(gè)。 1.10 B 求大公約數(shù)用的是輾轉(zhuǎn)相除法(歐幾里得算法),所以是O(logn)[5]。 2.1 這題比較基本,而且很多企業(yè)的筆試都愛(ài)考類(lèi)似的。主要就是對(duì)嘗試對(duì)數(shù)a進(jìn)行質(zhì)因數(shù)分解,容易寫(xiě)的就是從2開(kāi)始一直除到sqrt(a),性能提升一點(diǎn)就從2,3然后除奇數(shù)一直到sqrt(a)。當(dāng)然還可以?xún)?yōu)化一下,建立一個(gè)動(dòng)態(tài)質(zhì)數(shù)鏈表,將之前取到的所有質(zhì)數(shù)加入表進(jìn)行加速。 2.2 這題我覺(jué)得除了重載一下swap函數(shù)然后用傳統(tǒng)排序法之外也想不出什么高效的做法了。而且要代碼實(shí)現(xiàn),時(shí)間緊迫也不由得你多想。 2.3 這題個(gè)人覺(jué)得是這場(chǎng)筆試?yán)瓍^(qū)分度的題了(所以非科班出身的本人妥妥的死在這道題上),基于動(dòng)態(tài)規(guī)劃算法。事實(shí)上就是寫(xiě)出LD算法的偽代碼,[6]中有詳細(xì)的描述。 考場(chǎng)里完全對(duì)這東東沒(méi)概念,就隨便寫(xiě)了點(diǎn)啥交掉了。好吧,目送各位進(jìn)面試的大牛順利(你們的考驗(yàn)才剛剛開(kāi)始什么的我會(huì)隨便亂說(shuō)嗎) [1] 2013 google校園招聘筆試題. braveheart89的專(zhuān)欄. http://blog.csdn.net/braveheart89/article/details/8074657 [2] USB 2.0. 百度百科. http://baike.baidu.com/view/460899.htm [3] 編譯器后端寄存器分配算法SSA(靜態(tài)單一賦值法). 專(zhuān)欄. http://blog.csdn.net/lm2302293/article/details/6791752 [4] 寄存器重命名. 維基百科. http://zh.wikipedia.org/zh/%E5%AF%84%E5%AD%98%E5%99%A8%E9%87%8D%E5%91%BD%E5%90%8D [5] 歐幾里得算法的時(shí)間復(fù)雜度. 依然的博客. http://leaphan.blog.163.com/blog/static/16229419320105211170298/ [6] 文本比較算法Ⅰ——LD算法. 萬(wàn)倉(cāng)一黍. http://www.cnblogs.com/grenet/archive/2010/06/01/1748448.html