[合集google昨晚的筆試題,最后3道
發(fā)信人: fengisan (一個(gè)人......), 信區(qū): Job
標(biāo) 題: [合集] google昨晚的筆試題,最后3道
發(fā)信站: 珞珈山水BBS站 (Sat Oct 28 13:06:46 2006), 站內(nèi)
☆─────────────────────────────────────☆
qinyubin (轉(zhuǎn)向你的方向@E.I.S) 于 (Wed Oct 18 13:51:29 2006) 提到:
寫的很快,不過發(fā)現(xiàn)自己寫的很爛.下面的解法不是我的.
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
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];
}
一個(gè)n個(gè)頂點(diǎn)的'連通圖.
寫一個(gè)算法,求任意兩個(gè)點(diǎn)之間是否存在長(zhǎng)度為k的通路,通路上可以有重復(fù)的點(diǎn).
寫時(shí)間和空間復(fù)雜度
用matrix multiple, 復(fù)雜度是O(N^3logK)
☆─────────────────────────────────────☆
tube (tube) 于 (Wed Oct 18 13:56:27 2006) 提到:
第3題通路上可以有重復(fù)的點(diǎn)？我沒看題目上有寫這句阿
☆─────────────────────────────────────☆
qinyubin (轉(zhuǎn)向你的方向@E.I.S) 于 (Wed Oct 18 14:01:05 2006) 提到:
通路上可以有重復(fù)的點(diǎn),
恩,我剛發(fā)現(xiàn).沒有.
我轉(zhuǎn)的帖子.
☆─────────────────────────────────────☆
dragonfly (龍飛) 于 (Wed Oct 18 14:15:57 2006) 提到:
最后一題不用乘整個(gè)距陣吧
可以做到O(n^2*k)
那個(gè)logk怎么來的?
☆─────────────────────────────────────☆
tube (tube) 于 (Wed Oct 18 14:16:41 2006) 提到:
說下你的算法？目前還不知道最后一題怎么做
☆─────────────────────────────────────☆
tube (tube) 于 (Wed Oct 18 14:19:18 2006) 提到:
上面那個(gè)答案是按2點(diǎn)間路徑長(zhǎng)可以有回路做的，通路定義應(yīng)該是不算回路的，
鄰接矩陣做的就不對(duì)了，另外K應(yīng)該是常數(shù)因子把
☆─────────────────────────────────────☆
dragonfly (龍飛) 于 (Wed Oct 18 14:25:46 2006) 提到:
用一個(gè)bool數(shù)組a[n]表示i步可以達(dá)到的點(diǎn)
如果求x,y有沒有k的路徑
初始a[x]=1;其他為0
for(step=0;step<k; 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復(fù)制到a;
}
最后判斷a[y]==1就存在，否則不存在
☆─────────────────────────────────────☆
dragonfly(龍飛) 于 (Wed Oct 18 14:35:04 2006) 提到:
你搞錯(cuò)概念了
另外k是需要輸入的不能算常數(shù)因子
【[合集google昨晚的筆試題,最后3道】相關(guān)文章：
分享Google筆試題目06-20
Google產(chǎn)品經(jīng)理筆試題分享08-15
Google技術(shù)崗位筆試題目08-13
360筆試題目07-11
華為2017筆試題08-16
Google15個(gè)面試題以及答案11-25
華為2017筆試試題08-10
戴爾的12道筆試題目11-25
桂林銀行筆試題筆經(jīng)07-20