[合集] google昨晚的筆試題,最後3道
面試筆試8.47K
發信人: fengisan (一個人......), 信區: Job
標 題: [合集] google昨晚的筆試題,最後3道
發信站: 珞珈山水BBS站 (Sat Oct 28 13:06:46 2006), 站內
☆─────────────────────────────────────☆
qinyubin (轉向你的方向@E.I.S) 於 (Wed Oct 18 13:51:29 2006) 提到:
寫的很快,不過發現自己寫的很爛.下面的解法不是我的.
2.1 // search the value on the Binary Search Tree
struct Node
{
Node* left;
Node* right;
int value;
};
Node* Search(Node* root, int value)
{
while(NULL != root && root->value != value)
root = root->value > value ? root->left : root->right;
return root;
}
2.2 //Tribonacci number : T(i) = i (if i = 0, 1, 3); T(i) = T(i-1) + T(i-2) +
T(i-3) (if i > 2)
int Tribonacci(int n)
{
int t[] = {0, 1, 2};
for (; n > 2; --n)
{
t[1] += t[0];
t[2] += t[1];
t[0] = t[1] - t[0];
t[1] = t[2] - t[1];
}
return t[n];
}
一個n個頂點的連通圖.
寫一個演算法,求任意兩個點之間是否存在長度為k的通路,通路上可以有重複的點.
寫時間和空間複雜度
用matrix multiple, 複雜度是O(N^3logK)
☆─────────────────────────────────────☆
tube (tube) 於 (Wed Oct 18 13:56:27 2006) 提到:
第3題通路上可以有重複的點?我沒看題目上有寫這句阿
☆─────────────────────────────────────☆
qinyubin (轉向你的方向@E.I.S) 於 (Wed Oct 18 14:01:05 2006) 提到:
通路上可以有重複的點,
恩,我剛發現.沒有.
我轉的帖子.
☆─────────────────────────────────────☆
dragonflywww (龍飛) 於 (Wed Oct 18 14:15:57 2006) 提到:
最後一題不用乘整個距陣吧
可以做到O(n^2*k)
那個logk怎麼來的?
☆─────────────────────────────────────☆
tube (tube) 於 (Wed Oct 18 14:16:41 2006) 提到:
說下你的演算法?目前還不知道最後一題怎麼做
☆─────────────────────────────────────☆
tube (tube) 於 (Wed Oct 18 14:19:18 2006) 提到:
上面那個答案是按2點間路徑長可以有迴路做的,通路定義應該是不算迴路的,
鄰接矩陣做的就不對了,另外K應該是常數因子把
☆─────────────────────────────────────☆
dragonflywww (龍飛) 於 (Wed Oct 18 14:25:46 2006) 提到:
用一個bool陣列a[n]表示i步可以達到的點
如果求x,y有沒有k的路徑
初始a[x]=1;其他為0
for(step=0;step {
for(i = 0; i < n; ++i)
{
if(!a[x])continue;
for(j = 0; j < n; ++j)
if(matrix[i][j])b[j] = 1;
}
把b複製到a;
}
最後判斷a[y]==1就存在,否則不存在
☆─────────────────────────────────────☆
dragonflywww (龍飛) 於 (Wed Oct 18 14:35:04 2006) 提到:
你搞錯概念了
另外k是需要輸入的不能算常數因子
☆─────────────────────────────────────☆
Grope (Grope) 於 (Wed Oct 18 23:24:44 2006) 提到:
第2題可以寫log(n)的演算法
第3題 logk*n^3和k*|e|的演算法
☆─────────────────────────────────────☆
Grope (Grope) 於 (Wed Oct 18 23:31:48 2006) 提到:
不對 我剛剛看了題目 你我都搞錯了 是求任意的 不是任意給定的
應該矩陣乘法 N^3logK
☆─────────────────────────────────────☆
Grope (Grope) 於 (Thu Oct 19 11:23:26 2006) 提到:
最終發現只要O(n^3)的複雜度
方法都想複雜了
☆─────────────────────────────────────☆
dragonflywww (龍飛) 於 (Thu Oct 19 13:23:17 2006) 提到:
你在哪裡看的原始的題目?
求任意和給定的演算法思想都一樣撒
就距陣的k次方可以log一下
你說的n^3是用floyd?只能求無向圖的吧?
標 題: [合集] google昨晚的筆試題,最後3道
發信站: 珞珈山水BBS站 (Sat Oct 28 13:06:46 2006), 站內
☆─────────────────────────────────────☆
qinyubin (轉向你的方向@E.I.S) 於 (Wed Oct 18 13:51:29 2006) 提到:
寫的很快,不過發現自己寫的很爛.下面的解法不是我的.
2.1 // search the value on the Binary Search Tree
struct Node
{
Node* left;
Node* right;
int value;
};
Node* Search(Node* root, int value)
{
while(NULL != root && root->value != value)
root = root->value > value ? root->left : root->right;
return root;
}
2.2 //Tribonacci number : T(i) = i (if i = 0, 1, 3); T(i) = T(i-1) + T(i-2) +
T(i-3) (if i > 2)
int Tribonacci(int n)
{
int t[] = {0, 1, 2};
for (; n > 2; --n)
{
t[1] += t[0];
t[2] += t[1];
t[0] = t[1] - t[0];
t[1] = t[2] - t[1];
}
return t[n];
}
一個n個頂點的連通圖.
寫一個演算法,求任意兩個點之間是否存在長度為k的通路,通路上可以有重複的點.
寫時間和空間複雜度
用matrix multiple, 複雜度是O(N^3logK)
☆─────────────────────────────────────☆
tube (tube) 於 (Wed Oct 18 13:56:27 2006) 提到:
第3題通路上可以有重複的點?我沒看題目上有寫這句阿
☆─────────────────────────────────────☆
qinyubin (轉向你的方向@E.I.S) 於 (Wed Oct 18 14:01:05 2006) 提到:
通路上可以有重複的點,
恩,我剛發現.沒有.
我轉的帖子.
☆─────────────────────────────────────☆
dragonflywww (龍飛) 於 (Wed Oct 18 14:15:57 2006) 提到:
最後一題不用乘整個距陣吧
可以做到O(n^2*k)
那個logk怎麼來的?
☆─────────────────────────────────────☆
tube (tube) 於 (Wed Oct 18 14:16:41 2006) 提到:
說下你的演算法?目前還不知道最後一題怎麼做
☆─────────────────────────────────────☆
tube (tube) 於 (Wed Oct 18 14:19:18 2006) 提到:
上面那個答案是按2點間路徑長可以有迴路做的,通路定義應該是不算迴路的,
鄰接矩陣做的就不對了,另外K應該是常數因子把
☆─────────────────────────────────────☆
dragonflywww (龍飛) 於 (Wed Oct 18 14:25:46 2006) 提到:
用一個bool陣列a[n]表示i步可以達到的點
如果求x,y有沒有k的路徑
初始a[x]=1;其他為0
for(step=0;step
for(i = 0; i < n; ++i)
{
if(!a[x])continue;
for(j = 0; j < n; ++j)
if(matrix[i][j])b[j] = 1;
}
把b複製到a;
}
最後判斷a[y]==1就存在,否則不存在
☆─────────────────────────────────────☆
dragonflywww (龍飛) 於 (Wed Oct 18 14:35:04 2006) 提到:
你搞錯概念了
另外k是需要輸入的不能算常數因子
☆─────────────────────────────────────☆
Grope (Grope) 於 (Wed Oct 18 23:24:44 2006) 提到:
第2題可以寫log(n)的演算法
第3題 logk*n^3和k*|e|的演算法
☆─────────────────────────────────────☆
Grope (Grope) 於 (Wed Oct 18 23:31:48 2006) 提到:
不對 我剛剛看了題目 你我都搞錯了 是求任意的 不是任意給定的
應該矩陣乘法 N^3logK
☆─────────────────────────────────────☆
Grope (Grope) 於 (Thu Oct 19 11:23:26 2006) 提到:
最終發現只要O(n^3)的複雜度
方法都想複雜了
☆─────────────────────────────────────☆
dragonflywww (龍飛) 於 (Thu Oct 19 13:23:17 2006) 提到:
你在哪裡看的原始的題目?
求任意和給定的演算法思想都一樣撒
就距陣的k次方可以log一下
你說的n^3是用floyd?只能求無向圖的吧?
-
新浪08校園招聘部分筆試題(部落格編輯)
新浪08校園招聘部分筆試題(部落格編輯)新浪的08校園招聘已經過好久了,很有幸參加了筆試,雖然沒能拿到offer,但也是一次難得的經歷。大致寫一下我還有印象的一些新浪筆試題供大家參考:一、綜合部分(所有人都要做的)單選25個,包括法國現任總統、十七大閉幕時間、嫦娥飛昇時...
-
馬士基筆試經驗分享
好不容易鼓起勇氣擺脫頹廢的生活,投了份簡歷,又好不容易那麼好運接到了筆試通知,結果好不容易記錯了時間小獺和我一起,結果她也清楚地記得是九點半,但是好像就是我倆記錯了,服了,難道接電話的時候兩個都沒睡醒?前天接到電話的時候我真的是午覺剛醒,打電話過來的小姐問我...
-
應聘網易筆試失敗記
自新傳體育最終泡湯之後,又接到了網易北京公司的面試通知。簡直比大學聯考還BT,大學聯考遲到15分還可以進入考場。中午12點半出發,到達清華科技園才1點,正好有一些清華的07年畢業生正在搞一個藝術展,就在一邊看了一會,1點半了上樓,前臺的GG給了一個來賓胸卡,掛在脖子上。這時候...
-
筆試浪潮軟體研發
下午2點開始筆試的,先填寫了一份浪潮的職位申請表,很多與我簡歷中的內容都重複,所以填寫的有些不耐煩,後面幾項還有點意思。是否可以外駐:可以是否服從崗位分配:否期望月薪:3000在進考場之前,跟門外幾個一起來考試的談了一會兒,據說浪潮給應屆本科生的待遇是月薪1500,感...