發信人: OfferRain (offer的大雨), 信區: job
標 題: Google筆經
發信站: 飲水思源 (2006年10月11日03:06:04 星期三), 站內信件

開章明義，我是個廢人，上來積攢rp了。
在宣講會的時候，聽旁邊的師姐説上海只招兩個職位每個職位只招一個人。
現在後悔只選了北京和上海的SWE了。
不過反正……也不指望了。。。


筆試題目：9道單選+3道問答
時間：100分鐘
我做的是B卷。

單選題：
1，求兩個二進制數的異或值，基本上學過一點計算機的東西的人都能對的題目。。

2，不記得了。。也是不需要思考的題目。。

3，大概是如下的函數：
int someFunc(int x){
if (x == 0)
return 0;
else
return x + someFunc(x - 1);
}
問這個計算的是什麼。。。

4，不記得了。。不需要思考吧。。

5，不記得了。。不需要思考吧。。

6，參見2，4，5。。

7，似乎需要思考一下。。

8，問鏈表結構和數組相比的優勢不包括哪項，
包括：
插入的時間
刪除的時間
存儲空間
剩下兩個不記得了。。

9，如下函數：
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的整數數組，只允許用乘法不允許用除法，計算任意(n-1)個數的組合
乘積中最大的一組。。。寫出算法的時空複雜度。
ps：懷疑這道題目出錯啦。。雖然我也做錯了。。。。。。





一些補充：
1，問答的第一題是google上學期 intern的大題原題；
2，google很喜歡考鏈表，無論intern的面試以及兩次的筆試都有這樣的題目；
3，google一般大題第三道都是寫算法的時空複雜度；
4，選擇題基本上偏簡單，但是要做得準確率高似乎並不那麼容易；
5，根據傳言，小道消息，人云亦云以及以訛傳訛，google的高速審卷政策來源於審卷時
以選擇題為主，如果你全對啦，那麼恭喜你pass啦；如果你錯了好幾道，那麼下次努力
吧，如果還有下次。。。大題基本是做參考的。。。
6，選擇題很多記不清了，因為一遍做下來的，回去隨便掃了兩眼。。。加上過了這幾個
小時，記不得了。希望大家補充修正以及修改。。。

7，google會在11號開始3天內發麪試通知，據小道消息等等，有四輪面試。bless大家~~