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