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