4.8 Google招聘筆試
google2013校園招聘筆試題
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.使用一輛卡車?yán)?000塊單塊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.#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);
}
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)行時會崩潰
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用二進(jìn)制來編碼字符串“abcdabaa”,需要能夠根據(jù)編碼，解碼回原來的字符串，最少需要多長的二進(jìn)制字符串?
A.12
B.14
C.18
D.24
1.6 10個相同的糖果，分給三個人，每個人至少要得一個。有多少種不同分法
A.33 B.34C.35D.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ī)制可以用來進(jìn)行進(jìn)程間通信?
A.Socket B.PIPEC.SHARED MEMORYD.以上皆可
1.9 下列關(guān)于編程優(yōu)化的說法正確的是：
A. 使用編譯器的優(yōu)化選項后程序性能一定會獲得提高
B. 循環(huán)展開得越多越徹底，程序的性能越好
C. 寄存器分配能夠解決程序中的數(shù)據(jù)依賴問題
D. 現(xiàn)代主流C/C++編譯器可以對簡單的小函數(shù)進(jìn)行自動Iinline
1.10 一下程序是用來計算兩個非負(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中最大的那個數(shù)的長度為n，基本運(yùn)算時間復(fù)雜度為O(1)，那么該程序的時間復(fù)雜度為：
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ù)原型：void print_prime(int N); 不需要考慮整數(shù)溢出問題，也不許使用大數(shù)處理算法。
2.2 長度為n的數(shù)組亂序存放著0至n-1. 現(xiàn)在只能進(jìn)行0與其他書的swap，請設(shè)計并實現(xiàn)排序( 必須采用交換實現(xiàn))。
2.3 給定一個原串和目標(biāo)串，能對原串進(jìn)行如下操作：
1 在給定位置插入一個字符
2 替換任意字符
3 刪除任意字符
要求寫一個程序，返回最少的操作數(shù)，使得原串進(jìn)行這些操作后等于目標(biāo)串。原串和目標(biāo)串長度都小于2000.
總結(jié)的參考答案：
1.1 A
USB 2.0的理論傳輸極限是480Mbps，但是按照這個速率就沒有選項可選了-.-，所以猜測應(yīng)該認(rèn)為是普通U盤寫數(shù)據(jù)的6MB/s，即48Mbps;
100M以太網(wǎng)的速率就是100Mbps;
卡車?yán)脖P，1000x1000x8/3600=2222Mbps，這個應(yīng)該是最快的;
MP3在256kbps碼率下也平均只有1分鐘2MB，所以不會超過0.3Mbps，所以一定是最慢的。
1.2 D
這道題大家走出考場后爭議非常大。咱啥也不說，直接進(jìn)mingw跑一下gcc：
gcc提示的錯誤是“賦值號的左邊操作數(shù)需要一個左值”。其原因是調(diào)用宏的那句被預(yù)處理器替換成了：
*&array-4 =6;
由于減號比賦值優(yōu)先級高，因此先處理減號;由于減號返回一個數(shù)而不是合法的左值，所以編譯報錯。
1.3 C
這道題我是蒙對的-.- 標(biāo)準(zhǔn)做法是先畫出y=1-x的線，上側(cè)陰影部分就是y>1-x，其所占比例為9/32：
1.4 B
這道題我從A開始湊勝負(fù)表，直到B湊出結(jié)果就OK了。
1.5 B
這道題需要對abcd進(jìn)行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ù)字重復(fù)的算3種排列，不重復(fù)的算6種排列，共計4×3+4×6=36種。
1.7 D
這題很基本了。
1.8 D
一般學(xué)過操作系統(tǒng)這門課的都會吧，而且個人覺得D這個選項的出現(xiàn)不符合Google風(fēng)格。
1.9 D
這題其實很好做，因為D肯定是對的，而且ABC的言論太絕對。但如果一定要給出解釋的話……
A選項的優(yōu)化只能針對代碼本身，純系統(tǒng)調(diào)用什么的是不會性能提升的(當(dāng)然也不會下降)，
B選項我覺得是在并行優(yōu)化方面，好的編譯器可以從循環(huán)中發(fā)掘并行性，展開之后就不行了，
C選項有點說不清。消除數(shù)據(jù)依賴主要有兩個方法，一種是SSA，即靜態(tài)單賦值，這是通過對變量進(jìn)行重命名實現(xiàn)的，嚴(yán)格的說應(yīng)該叫“寄存器重命名”而不是“寄存器分配”;另外一種是調(diào)換指令順序，這種只要不是真相關(guān)(寫后讀，RAW)的話都可以消除掉，也不屬于寄存器分配。所以感覺不應(yīng)該選這個。
1.10 B
求最大公約數(shù)用的是輾轉(zhuǎn)相除法(歐幾里得算法)，所以是O(logn)。
2.1
這題比較基本，而且很多企業(yè)的筆試都愛考類似的。主要就是對嘗試對數(shù)a進(jìn)行質(zhì)因數(shù)分解，最容易寫的就是從2開始一直除到sqrt(a)，性能提升一點就從2,3然后除奇數(shù)一直到sqrt(a)。當(dāng)然還可以優(yōu)化一下，建立一個動態(tài)質(zhì)數(shù)鏈表，將之前取到的所有質(zhì)數(shù)加入表進(jìn)行加速。
2.2
這題我覺得除了重載一下swap函數(shù)然后用傳統(tǒng)排序法之外也想不出什么高效的做法了。而且要代碼實現(xiàn)，時間緊迫也不由得你多想。
2.3
這題個人覺得是這場筆試唯一拉分的題了，基于動態(tài)規(guī)劃算法。事實上就是寫出LD算法的偽代碼。
寫出這樣一個函數(shù) ,輸入一個 n, 輸出從1到這個數(shù)字之間的出現(xiàn)的1的個數(shù),比如f(13)等于6; f(9)等于1; 網(wǎng)上有很多這道題的解法，大多采用窮舉法。這把這個算法題變成了程序設(shè)計，這道題，我認(rèn)為是總結(jié)一個遞推公式，然后用遞推法實現(xiàn)，比較好。后來在網(wǎng)上考證了一下，這道題本來也是讓總結(jié)一個數(shù)學(xué)函數(shù)即可，無需編程。既然寫了，就貼出來，發(fā)表一下自己的解法。這道題還有另一半,當(dāng)f(n)＝n是，最小的n是多少？本人還沒有好的方法，所以就不貼了。
下面的程序是上半部java實現(xiàn)的。
/* 可以推出下列遞推公式:
* f(n)=(a>1?s:n-s*a+1)+a*f(s-1)+f(n-s*a)當(dāng)n>9時;
* L是n的位數(shù)
* a是n的第一位數(shù)字
* s是10的L－1次方
* n-s*a求的是a后面的數(shù).
* 公式說明：
* 求 0-n 由多少個數(shù)字1，分三部分，一是所有數(shù)中第一位有多少個1，對應(yīng)(a>1?s:n-s*a+1)
* 當(dāng)a大于1是,應(yīng)該有a的L1次， a小于1是有n-s*a+1。
* 如n是223 所有數(shù)中第一位有1是100;n是123所有數(shù)中第一位是1的有24
* 二是 對應(yīng)a*f(s-1） 如n是223應(yīng)該有2*f(99)個1
* 三是 對應(yīng)f(n-s*a) 如n是223應(yīng)該有f(23)個1。
*/
long f(long n){
if (n<9) return n>0?1:0;
int L=(int)(Math.log10(n)+1);//求n的位數(shù)l
long s=(long)Math.pow(10, L-1);//求10的l－1次方，方便求后面n的第一位數(shù)字，及其后面的數(shù)。
long a=(long)(n/s);//求n的第一位數(shù)字
return (a>1?s:n-s*a+1)+a*f(s-1)+f(n-s*a);
}
google筆試題：A+B=C
在一個集合S中尋找最大的C使A+B=C且A,B,C均在集合當(dāng)中
解答(原創(chuàng))
1，將集合S中的數(shù)排序X1<=X2<=X3.............Xn;
2，for(i=n;i>0;i--)
{
for(j=0,k=i-1;k>j;)
{
if(Xj+Xk>Xi)
{
k--;
cotinue;
}
if(Xj+Xk<Xi)
{
j++;
contiue;
}
A=Xj;
B=Xk;
C=Xi;
break;
}
例子：
1，4，7，10，11，13，15，18，34
34:1-18,4-18........15-18
18:1-15,4-15,4-13,7-13,7-11
結(jié)果：
A=7;B=11,C=18;
第一個的題目（嗯，記的不是很完整）：
在一棵（排序？）二叉樹中搜索指定值，數(shù)據(jù)結(jié)構(gòu)定義為：
struct Node
{
Node * lnext;
Node * rnext;
int value;
};
函數(shù)定義為（）：
Node * search(Node * root, int value)
{
}
實現(xiàn)這個search函數(shù)。
用遞歸，經(jīng)典的樹的遍歷，pass先。
第二個的題目：
計算Tribonaci隊列（嗯，九成九記錯了那個單詞……），規(guī)則是T(n) = T(n - 1) T(n - 2) T(n -3)，其中T(0) = T(1) = 1，T(2) = 2。
函數(shù)定義：
int Tribonaci(int n) {
}
備注，不考慮證整數(shù)溢出，盡可能優(yōu)化算法。
這一題我一看就知道要考什么，很顯然的遞歸定義，但也是很顯然的，這里所謂的優(yōu)化是指不要重復(fù)計算。
簡單的說，在計算T(n)的時候要用到T(n - 1)、T(n - 2)和T(n - 3)的結(jié)果，在計算T(n - 1)的時候也要用到T(n - 2)和T(n - 3)的結(jié)果，所以在各項計算的時候必須把以前計算的結(jié)果記錄下來，去掉重復(fù)計算。這里用到的一點小技巧就是要新寫一個函數(shù)用來做這種事情，嗯，看看我寫的代碼吧！
/**
Get the value of T(n - 1), and retrieve the result of
T(n - 2) and T(n - 3).
@param[in] n The n in T(n).
@param[out] mid Value of T(n - 2).
@param[out] right Value of T(n - 3).
@return Value of T(n - 1).
*/
int find_trib(int n, int & mid, int & right)
{
if (3 == n)
{
mid = 1;
right = 1;
return 2;
}
else
{
int temp;
mid = find_trib(n - 1, right, temp);
return mid right temp;
}
}
/**
Find value of T(n).
@param[in] The n in T(n).
@return Value of T(n).
@note T(n) = T(n - 1) T(n - 2) T(n - 3) (n > 2)
T(0) = T(1) = 1, T(2) = 2.
*/
int tribonaci(int n)
{
if (n < 0)
{
// Undefined feature.
return 0;
}
if (0 == n || 1 == n)
{
return 1;
}
if (2 == n)
{
return 2;
}
int mid, right;
int left = find_trib(n, mid, right);
return left mid right;
}
啊啊，對了，答卷的時候我可沒心情寫注釋……剛才到VC.Net 2003上測試了一下，貌似沒有啥問題。唉，看來我多少還是懂一點算法的……
第三個的題目：
05年Google筆試題
要筆試考題如下，其他題目是基礎(chǔ)題，就不貼出了：
1、假設(shè)在n進(jìn)制下，下面的等式成立，n值是（）
567*456=150216
a、 9 b、 10 c、 12 d、 18
2、文法G:S->uvSvu|w所識別的語言是：（）
a、uvw*vu b、（uvwvu）* c、uv(uv)*wvu(vu)* d、(uv)*w(vu)*
3、如下程序段輸出是：（）
char str[][10]={"Hello","Google"};
char *p=str[0];
count<<strlen(p 10);
a、0 b、5 c、6 d、10
4、cnt=0
while(x!=1){
cnt=cnt 1;
if(x&1==0)
x=x/2;
else
x=3*x 1;
}
count<<cnt<<end1;
當(dāng)n=11時，輸出：（）
a、12 b、13 c、14 d、15
5、寫一段程序判定一個有向圖G中節(jié)點w是否從節(jié)點v可達(dá)。（假如G中存在一條從v至w的路徑就說節(jié)點w是從v可達(dá)的）。以下算法是用C 寫成的，在bool Reachable函數(shù)中，你可以寫出自己的算法。
class Graph{
public:
int NumberOfNodes();//返回節(jié)點的總數(shù)
bool HasEdge(int u,int v);//u,v是節(jié)點個數(shù)，從零開始依次遞增，當(dāng)有一條從u到v的邊時，返回true
}；
bool Reachable(Graph&G, int v, int w){
//請寫入你的算法
}
6、給定一棵所有邊的長度均為整數(shù)的樹，現(xiàn)要求延長其中某些邊，使得從根到任意節(jié)點的路徑長度相等。問滿足要求的樹的邊長度之和最小是多少?請寫出你的算法，并分析時間復(fù)雜度。
=====================================================================
Google筆試題
1、 兩個二進(jìn)制數(shù)的異或結(jié)果
2、 遞歸函數(shù)最終會結(jié)束，那么這個函數(shù)一定(不定項選擇)：
1. 使用了局部變量 2. 有一個分支不調(diào)用自身
3. 使用了全局變量或者使用了一個或多個參數(shù)
3、以下函數(shù)的結(jié)果?
int cal(int x)
{
if(x==0)
return 0;
else
return x+cal(x-1);
}
4、 以下程序的結(jié)果?
void foo(int*a, int* b)
{
*a = *a+*b;
*b = *a-*b;
*a = *a-*b;
}
void main()
{
int a=1, b=2, c=3;
foo(&a,&b);
foo(&b,&c);
foo(&c,&a);
printf("%d, %d, %d", a,b,c);
}
5、下面哪項不是鏈表優(yōu)于數(shù)組的特點?
1. 方便刪除 2. 方便插入 3. 長度可變 4. 存儲空間小
6、T(n) = 25T(n/5)+n^2的時間復(fù)雜度?
7、n個頂點，m條邊的全連通圖，至少去掉幾條邊才能構(gòu)成一棵樹?
8、正則表達(dá)式(01|10|1001|0110)*與下列哪個表達(dá)式一樣?
1.(0|1)* 2.(01|01)* 3.(01|10)* 4.(11|01)* 5.(01|1)*
9、如何減少換頁錯誤?
1. 進(jìn)程傾向于占用CPU 2. 訪問局部性(locality of reference)滿足進(jìn)程要求
3. 進(jìn)程傾向于占用I/O 4.使用基于最短剩余時間(shortest remaining time)的調(diào)度機(jī)制
5. 減少頁大小
10、實現(xiàn)兩個N*N矩陣的乘法，矩陣由一維數(shù)組表示
11、找到單向鏈表中間那個元素，如果有兩個則取前面一個
12、長度為n的整數(shù)數(shù)組，找出其中任意(n-1)個乘積最大的那一組，只能用乘法，不可以用除法。要求對算法的時間復(fù)雜度和空間復(fù)雜度作出分析，不要求寫程序。
google浙大招聘筆試題
一、單選
1、80x86中，十進(jìn)制數(shù)-3用16位二進(jìn)制數(shù)表示為?0010000
2、假定符號-、*、$分別代表減法、乘法和指數(shù)運(yùn)算，且
1)三個運(yùn)算符優(yōu)先級順序是：-最高，*其次，$最低;
2)運(yùn)算符運(yùn)算時為左結(jié)合。請計算3-2*4$1*2$3的值：
(A)4096，(B)-61，(C)64，(D)-80，(E)512
算符
3、下列偽代碼中，參數(shù)是引用傳遞，結(jié)果是?
calc(double p, double q, double r){q=q-1.0;r=r+p}
main(){
double a = 2.5, b = 9.0;
calc(b-a, a, a);
print(a);
}
(A)1.5 (B)2.5 (C)10.5 (D)8 (E)6.5
4、求輸出結(jié)果：
int foo(int x, int y){
if(x <=0 || y <= 0) return 1;
return 3 * foo(x - 1, y / 2);
}
printf("%d\n", foo(3, 5));
(A)81 (B)27 (C)9 (D)3 (E)1
5、下列哪個數(shù)據(jù)結(jié)構(gòu)在優(yōu)先隊列中被最廣泛使用?a
(A)堆 (B)數(shù)組 (C)雙向鏈表 (D)圖 (E)向量
6、以下算法描述了一個在n國元素的雙向鏈表中找到第k個元素的方法(k >= 1且k <= n)：
如果k <= n - k，從鏈表開始往前進(jìn)k-1個元素。
否則，從終點出發(fā)，往回走n - k個元素。
這個算法的時間代價是?
(A)θ(nlogn) (B)θ(max{k, n - k}) (C)θ(k + (n - k))
(D)θ(max{k, k - n}) (E)θ(min{k, n - k})
7、有一個由10個頂點組成的圖，每個頂點有6個度，那么這個圖有幾條邊?30
(A)60 (B)30 (C)20 (D)80 (E)90
8、正則表達(dá)式L = x*(x|yx+)。下列哪個字符串不符號
(A)x (B)xyxyx (C)xyx (D)yxx (E)yx
9、為讀取一塊數(shù)據(jù)而準(zhǔn)備磁盤驅(qū)動器的總時間包括
(A)等待時間 (B)尋道時間 (C)傳輸時間 (D)等待時間加尋道時間 (E)等待時間加尋道時間加傳輸時間
二、算法
1、打印出一個二叉樹的內(nèi)容。
2、在一個字符串中找到第一個只出現(xiàn)一次的字符。如abaccdeff，輸出b。
3、給定一個長度為N的整數(shù)數(shù)組（元素有正有負(fù)），求所有元素之和最大的一個子數(shù)組。分析算法時空復(fù)雜度。不必寫代碼。
附上算法題第3題的動態(tài)規(guī)劃做法的參考答案:
最大子序列
問題：
給定一整數(shù)序列A1， A2，... An （可能有負(fù)數(shù)），求A1~An的一個子序列Ai~Aj，使得Ai到Aj的和最大
例如： 整數(shù)序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和為20。 對于這個問題，最簡單也是最容易想到的那就是窮舉所有子序列的方法。利用三重循環(huán)，依次求出所有子序列的和然后取最大的那個。當(dāng)然算法復(fù)雜度會達(dá)到O(n^3)。顯然這種方法不是最優(yōu)的，下面給出一個算法復(fù)雜度為O(n)的線性算法實現(xiàn)，算法的來源于Programming Pearls一書。 在給出線性算法之前，先來看一個對窮舉算法進(jìn)行優(yōu)化的算法，它的算法復(fù)雜度為O(n^2)。其實這個算法只是對對窮舉算法稍微做了一些修改：其實子序列的和我們并不需要每次都重新計算一遍。假設(shè)Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用這一個遞推，我們就可以得到下面這個算法：
int max_sub(int a[],int size)
{
int i,j,v,max=a[0];
for(i=0;i<size;i++)
{
v=0;
for(j=i;j<size;j++)
{
v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1]
if(v>max)
max=v;
}
}
return max;
}那怎樣才能達(dá)到線性復(fù)雜度呢？這里運(yùn)用動態(tài)規(guī)劃的思想。先看一下源代碼實現(xiàn)：
int max_sub2(int a[], int size)
{
int i,max=0,temp_sum=0;
for(i=0;i<size;i++)
{
temp_sum+=a[i];
if(temp_sum>max)
max=temp_sum;
else if(temp_sum<0)
temp_sum=0;
}
return max;
}
在這一遍掃描數(shù)組當(dāng)中，從左到右記錄當(dāng)前子序列的和temp_sum，若這個和不斷增加，那么最大子序列的和max也不斷增加(不斷更新max)。如果往前掃描中遇到負(fù)數(shù)，那么當(dāng)前子序列的和將會減小。此時temp_sum 將會小于max，當(dāng)然max也就不更新。如果temp_sum降到0時，說明前面已經(jīng)掃描的那一段就可以拋棄了，這時將temp_sum置為0。然后，temp_sum將從后面開始將這個子段進(jìn)行分析，若有比當(dāng)前max大的子段，繼續(xù)更新max。這樣一趟掃描結(jié)果也就出來了。
google面試試題匯總
筆試題目：9道單選+3道問答
時間：100分鐘
我做的是B卷。
單選題：
1，求兩個二進(jìn)制數(shù)的異或值，基本上學(xué)過一點計算機(jī)的東西的人都能對的題目。。
2，不記得了。。也是不需要思考的題目。。
3，大概是如下的函數(shù)：
int someFunc(int x){
if (x == 0)
return 0;
else
return x + someFunc(x - 1);
}
問這個計算的是什么。。。
4，不記得了。。不需要思考吧。。
5，不記得了。。不需要思考吧。。
6，參見2，4，5。。
7，似乎需要思考一下。。
8，問鏈表結(jié)構(gòu)和數(shù)組相比的優(yōu)勢不包括哪項，
包括：
插入的時間
刪除的時間
存儲空間
剩下兩個不記得了。。
9，如下函數(shù)：
T(x) = 1 (x <= 1)
T(n) = 25 T(n/5) + n^2
問T(n)隨n的增長。
選項大概是這樣的：
O(n^2)，O(n^2logn)等等的。。
問答：
1，寫兩個N*N的矩陣的乘法，給出了C的格式，你可以選擇你喜歡的語言去寫。。
int* multi(int* a1, int* a2, int N){
}
2，尋找一個單向鏈表的中項，如果存在兩個則返回前一個。給出了C的格式，同樣你可以選擇。。。。
struct {
Node* next;
int value;
} Node;
Node* someFunc(Node* head){
}
3，給一個長度為n的整數(shù)數(shù)組，只允許用乘法不允許用除法，計算任意(n-1)個數(shù)的組合乘積中最大的一組。。。寫出算法的時空復(fù)雜度。
ps：懷疑這道題目出錯啦。。雖然我也做錯了。。。。。。
一些補(bǔ)充：
1，問答的第一題是google上學(xué)期 intern的大題原題;
2，google很喜歡考鏈表，無論intern的面試以及兩次的筆試都有這樣的題目;
3，google一般大題第三道都是寫算法的時空復(fù)雜度;
4，選擇題基本上偏簡單，但是要做得準(zhǔn)確率高似乎并不那么容易;
5，根據(jù)傳言，小道消息，人云亦云以及以訛傳訛，google的高速審卷政策來源于審卷時以選擇題為主，如果你全對啦，那么恭喜你pass啦;如果你錯了好幾道，那么下次努力吧，如果還有下次。。。大題基本是做參考的。。。
Google筆試題2006
選擇題
1. 把一個無符號16位整數(shù)a的最高為置為1
2. Fibonacci,求f(4)使用遞歸調(diào)用f(1)的次數(shù)f(n) = f(n-1)+f(n-2)
f(0)=0, f(1)=1
a.5 b.4 c. 3 d. 4以上
3. if (xAS{print “1″}
S->AB{print “2″}
A->a{print “3″}
B->bC{print “4″}
B->dB{print “5″}
C->c{print “6″}
6. 有關(guān)哈希表正確的說法(不定項)
a.哈希表的效率和哈希函數(shù)。。。。相關(guān)
b.哈希表的解決沖突方法慢，回影響哈希表效率
c.使用鏈表哈�？墒箖�(nèi)存緊湊
7. 一種無饑餓調(diào)度方法是：
a. 輪叫調(diào)度
b.
c. 最短使用時間
d. 最新隊列
8. 下列排序方法最差情況時間復(fù)雜度為O(n^2)的是：
a. 插入
b. 歸并
c. 冒泡
d. 快速
編程題：
1. 求一個二叉樹的高度，如果只有root結(jié)點，高度為0
2. 將稀疏疏組中的非零元素提取出來，用鏈表表示
3. 兩個n維數(shù)組，已排序，為升序。設(shè)計算法求2n的數(shù)中
第n大的數(shù)。要求分析時間和空間復(fù)雜度。不用給出代碼
==================================================================
這是部分google面試題目,希望后來者好運(yùn).
1.求直方圖的最大內(nèi)接矩形,假設(shè)每個細(xì)條的寬度為1.這個題很hot,兩個人來問.我沒想出什么好的算法.
2.NxN行列有序的矩陣查找一個數(shù).以前有人遇到過.O(N)的時間復(fù)雜度
3.給定一篇文章,求包含所有單詞的最短摘要.O(N)的時間復(fù)雜度
4.將MxN的矩陣轉(zhuǎn)秩,要求O(1)的空間復(fù)雜度.參考群論中cyclic group,group generator
5.開放式問題,怎么避免重復(fù)抓取網(wǎng)頁
6.開放式問題,有些網(wǎng)站每天只允許有限次訪問,怎么抓取網(wǎng)頁使得索引盡量全面和新鮮
7.寫一個singleton pattern的例子
8.vector vs. arraylist, growth strategy & complexity
9.在C++文件中只declare class A, 但不以任何方式define class A, 是做什么用
10.virtual function
11.討論html vs. xhtml vs. xml
12.描述在瀏覽器中敲入一個網(wǎng)址后所發(fā)生的事情.dns,cache等