[合集] google昨晚的筆試題,最後3道

發信人: 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?只能求無向圖的吧?