4.8 Google招聘筆試
google2013校園招聘筆試題
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裝滿(mǎn)數(shù)據(jù)的硬盤(pán)，以100km/h的速度從上海到天津(100km)一趟所等價(jià)的數(shù)據(jù)傳輸寬帶
4.使用電腦播放MP3，電腦的pci總線(xiàn)到聲卡的數(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.#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)行時(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)不得分，小組前三名出線(xiàn)平分抽簽。問(wèn)一個(gè)隊(duì)最少拿幾分就有理論上的出線(xiàn)希望：
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.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ī)制可以用來(lái)進(jìn)行進(jìn)程間通信?
A.Socket B.PIPEC.SHARED MEMORYD.以上皆可
1.9 下列關(guān)于編程優(yōu)化的說(shuō)法正確的是：
A. 使用編譯器的優(yōu)化選項(xiàng)后程序性能一定會(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ù)原型：void print_prime(int N); 不需要考慮整數(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)排序( 必須采用交換實(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.
總結(jié)的參考答案：
1.1 A
USB 2.0的理論傳輸極限是480Mbps，但是按照這個(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-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的線(xiàn)，上側(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ì)。但如果一定要給出解釋的話(huà)……
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)單賦值，這是通過(guò)對(duì)變量進(jìn)行重命名實(shí)現(xiàn)的，嚴(yán)格的說(shuō)應(yīng)該叫“寄存器重命名”而不是“寄存器分配”;另外一種是調(diào)換指令順序，這種只要不是真相關(guān)(寫(xiě)后讀，RAW)的話(huà)都可以消除掉，也不屬于寄存器分配。所以感覺(jué)不應(yīng)該選這個(gè)。
1.10 B
求最大公約數(shù)用的是輾轉(zhuǎn)相除法(歐幾里得算法)，所以是O(logn)。
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)筆試唯一拉分的題了，基于動(dòng)態(tài)規(guī)劃算法。事實(shí)上就是寫(xiě)出LD算法的偽代碼。
寫(xiě)出這樣一個(gè)函數(shù) ,輸入一個(gè) n, 輸出從1到這個(gè)數(shù)字之間的出現(xiàn)的1的個(gè)數(shù),比如f(13)等于6; f(9)等于1; 網(wǎng)上有很多這道題的解法，大多采用窮舉法。這把這個(gè)算法題變成了程序設(shè)計(jì)，這道題，我認(rèn)為是總結(jié)一個(gè)遞推公式，然后用遞推法實(shí)現(xiàn)，比較好。后來(lái)在網(wǎng)上考證了一下，這道題本來(lái)也是讓總結(jié)一個(gè)數(shù)學(xué)函數(shù)即可，無(wú)需編程。既然寫(xiě)了，就貼出來(lái)，發(fā)表一下自己的解法。這道題還有另一半,當(dāng)f(n)＝n是，最小的n是多少？本人還沒(méi)有好的方法，所以就不貼了。
下面的程序是上半部java實(shí)現(xiàn)的。
/* 可以推出下列遞推公式:
* f(n)=(a>1?s:n-s*a+1)+a*f(s-1)+f(n-s*a)當(dāng)n>9時(shí);
* L是n的位數(shù)
* a是n的第一位數(shù)字
* s是10的L－1次方
* n-s*a求的是a后面的數(shù).
* 公式說(shuō)明：
* 求 0-n 由多少個(gè)數(shù)字1，分三部分，一是所有數(shù)中第一位有多少個(gè)1，對(duì)應(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
* 二是 對(duì)應(yīng)a*f(s-1） 如n是223應(yīng)該有2*f(99)個(gè)1
* 三是 對(duì)應(yīng)f(n-s*a) 如n是223應(yīng)該有f(23)個(gè)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
在一個(gè)集合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;
第一個(gè)的題目（嗯，記的不是很完整）：
在一棵（排序？）二叉樹(shù)中搜索指定值，數(shù)據(jù)結(jié)構(gòu)定義為：
struct Node
{
Node * lnext;
Node * rnext;
int value;
};
函數(shù)定義為（）：
Node * search(Node * root, int value)
{
}
實(shí)現(xiàn)這個(gè)search函數(shù)。
用遞歸，經(jīng)典的樹(shù)的遍歷，pass先。
第二個(gè)的題目：
計(jì)算Tribonaci隊(duì)列（嗯，九成九記錯(cuò)了那個(gè)單詞……），規(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ù)計(jì)算。
簡(jiǎn)單的說(shuō)，在計(jì)算T(n)的時(shí)候要用到T(n - 1)、T(n - 2)和T(n - 3)的結(jié)果，在計(jì)算T(n - 1)的時(shí)候也要用到T(n - 2)和T(n - 3)的結(jié)果，所以在各項(xiàng)計(jì)算的時(shí)候必須把以前計(jì)算的結(jié)果記錄下來(lái)，去掉重復(fù)計(jì)算。這里用到的一點(diǎn)小技巧就是要新寫(xiě)一個(gè)函數(shù)用來(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;
}
啊啊，對(duì)了，答卷的時(shí)候我可沒(méi)心情寫(xiě)注釋……剛才到VC.Net 2003上測(cè)試了一下，貌似沒(méi)有啥問(wèn)題。唉，看來(lái)我多少還是懂一點(diǎn)算法的……
第三個(gè)的題目：
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所識(shí)別的語(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;
當(dāng)n=11時(shí)，輸出：（）
a、12 b、13 c、14 d、15
5、寫(xiě)一段程序判定一個(gè)有向圖G中節(jié)點(diǎn)w是否從節(jié)點(diǎn)v可達(dá)。（假如G中存在一條從v至w的路徑就說(shuō)節(jié)點(diǎn)w是從v可達(dá)的）。以下算法是用C 寫(xiě)成的，在bool Reachable函數(shù)中，你可以寫(xiě)出自己的算法。
class Graph{
public:
int NumberOfNodes();//返回節(jié)點(diǎn)的總數(shù)
bool HasEdge(int u,int v);//u,v是節(jié)點(diǎn)個(gè)數(shù)，從零開(kāi)始依次遞增，當(dāng)有一條從u到v的邊時(shí)，返回true
}；
bool Reachable(Graph&G, int v, int w){
//請(qǐng)寫(xiě)入你的算法
}
6、給定一棵所有邊的長(zhǎng)度均為整數(shù)的樹(shù)，現(xiàn)要求延長(zhǎng)其中某些邊，使得從根到任意節(jié)點(diǎn)的路徑長(zhǎng)度相等。問(wèn)滿(mǎn)足要求的樹(shù)的邊長(zhǎng)度之和最小是多少?請(qǐng)寫(xiě)出你的算法，并分析時(shí)間復(fù)雜度。
=====================================================================
Google筆試題
1、 兩個(gè)二進(jìn)制數(shù)的異或結(jié)果
2、 遞歸函數(shù)最終會(huì)結(jié)束，那么這個(gè)函數(shù)一定(不定項(xiàng)選擇)：
1. 使用了局部變量 2. 有一個(gè)分支不調(diào)用自身
3. 使用了全局變量或者使用了一個(gè)或多個(gè)參數(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、下面哪項(xiàng)不是鏈表優(yōu)于數(shù)組的特點(diǎn)?
1. 方便刪除 2. 方便插入 3. 長(zhǎng)度可變 4. 存儲(chǔ)空間小
6、T(n) = 25T(n/5)+n^2的時(shí)間復(fù)雜度?
7、n個(gè)頂點(diǎn)，m條邊的全連通圖，至少去掉幾條邊才能構(gòu)成一棵樹(shù)?
8、正則表達(dá)式(01|10|1001|0110)*與下列哪個(gè)表達(dá)式一樣?
1.(0|1)* 2.(01|01)* 3.(01|10)* 4.(11|01)* 5.(01|1)*
9、如何減少換頁(yè)錯(cuò)誤?
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)的調(diào)度機(jī)制
5. 減少頁(yè)大小
10、實(shí)現(xiàn)兩個(gè)N*N矩陣的乘法，矩陣由一維數(shù)組表示
11、找到單向鏈表中間那個(gè)元素，如果有兩個(gè)則取前面一個(gè)
12、長(zhǎng)度為n的整數(shù)數(shù)組，找出其中任意(n-1)個(gè)乘積最大的那一組，只能用乘法，不可以用除法。要求對(duì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度作出分析，不要求寫(xiě)程序。
google浙大招聘筆試題
一、單選
1、80x86中，十進(jìn)制數(shù)-3用16位二進(jìn)制數(shù)表示為?0010000
2、假定符號(hào)-、*、$分別代表減法、乘法和指數(shù)運(yùn)算，且
1)三個(gè)運(yùn)算符優(yōu)先級(jí)順序是：-最高，*其次，$最低;
2)運(yùn)算符運(yùn)算時(shí)為左結(jié)合。請(qǐng)計(jì)算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、下列哪個(gè)數(shù)據(jù)結(jié)構(gòu)在優(yōu)先隊(duì)列中被最廣泛使用?a
(A)堆 (B)數(shù)組 (C)雙向鏈表 (D)圖 (E)向量
6、以下算法描述了一個(gè)在n國(guó)元素的雙向鏈表中找到第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、正則表達(dá)式L = x*(x|yx+)。下列哪個(gè)字符串不符號(hào)
(A)x (B)xyxyx (C)xyx (D)yxx (E)yx
9、為讀取一塊數(shù)據(jù)而準(zhǔn)備磁盤(pán)驅(qū)動(dòng)器的總時(shí)間包括
(A)等待時(shí)間 (B)尋道時(shí)間 (C)傳輸時(shí)間 (D)等待時(shí)間加尋道時(shí)間 (E)等待時(shí)間加尋道時(shí)間加傳輸時(shí)間
二、算法
1、打印出一個(gè)二叉樹(shù)的內(nèi)容。
2、在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。如abaccdeff，輸出b。
3、給定一個(gè)長(zhǎng)度為N的整數(shù)數(shù)組（元素有正有負(fù)），求所有元素之和最大的一個(gè)子數(shù)組。分析算法時(shí)空復(fù)雜度。不必寫(xiě)代碼。
附上算法題第3題的動(dòng)態(tài)規(guī)劃做法的參考答案:
最大子序列
問(wèn)題：
給定一整數(shù)序列A1， A2，... An （可能有負(fù)數(shù)），求A1~An的一個(gè)子序列Ai~Aj，使得Ai到Aj的和最大
例如： 整數(shù)序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和為20。 對(duì)于這個(gè)問(wèn)題，最簡(jiǎn)單也是最容易想到的那就是窮舉所有子序列的方法。利用三重循環(huán)，依次求出所有子序列的和然后取最大的那個(gè)。當(dāng)然算法復(fù)雜度會(huì)達(dá)到O(n^3)。顯然這種方法不是最優(yōu)的，下面給出一個(gè)算法復(fù)雜度為O(n)的線(xiàn)性算法實(shí)現(xiàn)，算法的來(lái)源于Programming Pearls一書(shū)。 在給出線(xiàn)性算法之前，先來(lái)看一個(gè)對(duì)窮舉算法進(jìn)行優(yōu)化的算法，它的算法復(fù)雜度為O(n^2)。其實(shí)這個(gè)算法只是對(duì)對(duì)窮舉算法稍微做了一些修改：其實(shí)子序列的和我們并不需要每次都重新計(jì)算一遍。假設(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;
}那怎樣才能達(dá)到線(xiàn)性復(fù)雜度呢？這里運(yùn)用動(dòng)態(tài)規(guī)劃的思想。先看一下源代碼實(shí)現(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，若這個(gè)和不斷增加，那么最大子序列的和max也不斷增加(不斷更新max)。如果往前掃描中遇到負(fù)數(shù)，那么當(dāng)前子序列的和將會(huì)減小。此時(shí)temp_sum 將會(huì)小于max，當(dāng)然max也就不更新。如果temp_sum降到0時(shí)，說(shuō)明前面已經(jīng)掃描的那一段就可以?huà)仐壛耍@時(shí)將temp_sum置為0。然后，temp_sum將從后面開(kāi)始將這個(gè)子段進(jìn)行分析，若有比當(dāng)前max大的子段，繼續(xù)更新max。這樣一趟掃描結(jié)果也就出來(lái)了。
google面試試題匯總
筆試題目：9道單選+3道問(wèn)答
時(shí)間：100分鐘
我做的是B卷。
單選題：
1，求兩個(gè)二進(jìn)制數(shù)的異或值，基本上學(xué)過(guò)一點(diǎn)計(jì)算機(jī)的東西的人都能對(duì)的題目。。
2，不記得了。。也是不需要思考的題目。。
3，大概是如下的函數(shù)：
int someFunc(int x){
if (x == 0)
return 0;
else
return x + someFunc(x - 1);
}
問(wèn)這個(gè)計(jì)算的是什么。。。
4，不記得了。。不需要思考吧。。
5，不記得了。。不需要思考吧。。
6，參見(jiàn)2，4，5。。
7，似乎需要思考一下。。
8，問(wèn)鏈表結(jié)構(gòu)和數(shù)組相比的優(yōu)勢(shì)不包括哪項(xiàng)，
包括：
插入的時(shí)間
刪除的時(shí)間
存儲(chǔ)空間
剩下兩個(gè)不記得了。。
9，如下函數(shù)：
T(x) = 1 (x <= 1)
T(n) = 25 T(n/5) + n^2
問(wèn)T(n)隨n的增長(zhǎng)。
選項(xià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è)單向鏈表的中項(xiàng)，如果存在兩個(gè)則返回前一個(gè)。給出了C的格式，同樣你可以選擇。。。。
struct {
Node* next;
int value;
} Node;
Node* someFunc(Node* head){
}
3，給一個(gè)長(zhǎng)度為n的整數(shù)數(shù)組，只允許用乘法不允許用除法，計(jì)算任意(n-1)個(gè)數(shù)的組合乘積中最大的一組。。。寫(xiě)出算法的時(shí)空復(fù)雜度。
ps：懷疑這道題目出錯(cuò)啦。。雖然我也做錯(cuò)了。。。。。。
一些補(bǔ)充：
1，問(wèn)答的第一題是google上學(xué)期 intern的大題原題;
2，google很喜歡考鏈表，無(wú)論intern的面試以及兩次的筆試都有這樣的題目;
3，google一般大題第三道都是寫(xiě)算法的時(shí)空復(fù)雜度;
4，選擇題基本上偏簡(jiǎn)單，但是要做得準(zhǔn)確率高似乎并不那么容易;
5，根據(jù)傳言，小道消息，人云亦云以及以訛傳訛，google的高速審卷政策來(lái)源于審卷時(shí)以選擇題為主，如果你全對(duì)啦，那么恭喜你pass啦;如果你錯(cuò)了好幾道，那么下次努力吧，如果還有下次。。。大題基本是做參考的。。。
Google筆試題2006
選擇題
1. 把一個(gè)無(wú)符號(hào)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)哈希表正確的說(shuō)法(不定項(xiàng))
a.哈希表的效率和哈希函數(shù)。。。。相關(guān)
b.哈希表的解決沖突方法慢，回影響哈希表效率
c.使用鏈表哈希可使內(nèi)存緊湊
7. 一種無(wú)饑餓調(diào)度方法是：
a. 輪叫調(diào)度
b.
c. 最短使用時(shí)間
d. 最新隊(duì)列
8. 下列排序方法最差情況時(shí)間復(fù)雜度為O(n^2)的是：
a. 插入
b. 歸并
c. 冒泡
d. 快速
編程題：
1. 求一個(gè)二叉樹(shù)的高度，如果只有root結(jié)點(diǎn)，高度為0
2. 將稀疏疏組中的非零元素提取出來(lái)，用鏈表表示
3. 兩個(gè)n維數(shù)組，已排序，為升序。設(shè)計(jì)算法求2n的數(shù)中
第n大的數(shù)。要求分析時(shí)間和空間復(fù)雜度。不用給出代碼
==================================================================
這是部分google面試題目,希望后來(lái)者好運(yùn).
1.求直方圖的最大內(nèi)接矩形,假設(shè)每個(gè)細(xì)條的寬度為1.這個(gè)題很hot,兩個(gè)人來(lái)問(wèn).我沒(méi)想出什么好的算法.
2.NxN行列有序的矩陣查找一個(gè)數(shù).以前有人遇到過(guò).O(N)的時(shí)間復(fù)雜度
3.給定一篇文章,求包含所有單詞的最短摘要.O(N)的時(shí)間復(fù)雜度
4.將MxN的矩陣轉(zhuǎn)秩,要求O(1)的空間復(fù)雜度.參考群論中cyclic group,group generator
5.開(kāi)放式問(wèn)題,怎么避免重復(fù)抓取網(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等