隨手扎
LAG挑戰資深實習生 BFS 程式面試考題
解法
其實再上一篇後沒多就,就有朋友提到:「那麼我需要花多久時間完成題目呢?」。
恩…我也挺好奇的。
實際上也就那幾天就已經自己量時間測驗過了。雖然是有些馬後炮,但我花了16分18秒完成第一個版本(repl.it):
async function searchGraph(start) {
let visited = new Set();
let curr_nodes = new Set([start]);
let next_nodes = new Set();
while(curr_nodes.size > 0) {
next_nodes = new Set();
for(let node of curr_nodes) {
console.log(node);
visited.add(node);
let neighbours = await fetchNeighbours(node);
neighbours.data.forEach((node) => {
if(!visited.has(node)){
next_nodes.add(node);
}
})
}
curr_nodes = next_nodes;
}
}
然後又花了14分鐘27秒調整成第二個版本(repl.it):
此外,其實我覺得Terry後續的部份引導還不錯的。有讓我想到其他調整方式…
async function searchGraph(start) {
let visited = new Set();
let next_nodes = new Set();
let curr_nodes = [start];
while(curr_nodes.length > 0) {
next_nodes = new Set();
let p = curr_nodes.map(node => {
console.log(node);
visited.add(node);
return fetchNeighbours(node).then(({data: nxts}) => {
for(let n of nxts){
if(! visited.has(n)) {
next_nodes.add(n);
}
}
})
});
await Promise.all(p);
curr_nodes = Array.from(next_nodes);
}
}
其實會再分享這篇,是因為看到Coding4Fun - .NET 老司機挑戰 BFS 程式面試考題,不過我並沒有仔細看看這篇的程式碼內容。但是我認為我與朋友討論的解法和時間複雜度的分析是可以來分享分享的。
Mock題目
首先需要先完成題目基本樣板,但是照著影片題目照抄一次,會發現fetchNeighbours()
裡呼叫的HTTP API已經不同。沒關係好歹我也有寫過一點點Unit Test的經驗,可以自己來mock一個:
async function fetchNeighbours(node) {
switch (node){
case 1:
return {data: [2, 3, 4]};
case 2:
return {data: [1, 5]};
case 3:
return {data: [1, 5]};
case 4:
return {data: [1, 6]};
case 5:
return {data: [2, 3, 7]};
case 6:
return {data: [4, 7]};
case 7:
return {data: [5, 6]};
}
}
實際上還可以加入一些亂數時間延遲因子,模擬HTTP Request有一秒左右才收到結果的樣子。在調整上,也可以不只是console.log
輸出結果,而可以把結果收集下來,最後回傳數值陣列回去。
有興趣可以自己嘗試解解看: Repl.it
async function fetchNeighbours(node) {
switch (node){
case 1:
return {data: [2, 3, 4]};
case 2:
return {data: [1, 5]};
case 3:
return {data: [1, 5]};
case 4:
return {data: [1, 6]};
case 5:
return {data: [2, 3, 7]};
case 6:
return {data: [4, 7]};
case 7:
return {data: [5, 6]};
}
}
async function searchGraph(start) {
let neighbours = await fetchNeighbours(start);
console.log(neighbours.data);
// your code
}
searchGraph(1);
時間複雜度分析
從實現上來分析,最困難的點在於中間forEach()
部分。
let neighbours = await fetchNeighbours(node);
neighbours.data.forEach((node) => {
if(!visited.has(node)){
next_nodes.add(node);
}
})
因為這個與每個節點的「度(degree)」有關,也就是當前節點有多少鄰居,但是每個節點的鄰居是不確定的。
或許依然可以使用主定理(Master Theorem)進行分析,但我想從一個更簡單的方式來分析,一個我一開始設計解法的想法來分析。
在圖論的一些演算法中,甚至圖本身的描述中,都會有幾個概念:節點集合、邊集合。也就特別是 集合 這個資料結構的概念。
如果僅僅是寫成虛擬碼(pseudocode),上面程式碼片段,其實就只是很簡單的「集合差集」的概念,將相鄰節點排除掉已經拜訪過的節點。
SET(neighbours) - SET(visited)
那麼這個時間複雜度就可以簡化為O(1)
的常數時間。
再接著需要分析的就是while
的部分:
while(curr_nodes.size > 0) {
next_nodes = new Set();
for(let node of curr_nodes) {
console.log(node);
visited.add(node);
let neighbours = await fetchNeighbours(node);
// next_nodes += (neighbours - visited) // <= 都是集合操作
}
curr_nodes = next_nodes;
}
裡頭for
迴圈部分是當前level(與起點距離)的節點數量。while
部分會是有多深的level。拿題目來說,就會是 1 + 3 + 2 + 1
。
每一個數字代表該level的節點數量,細看的話會是:
- 1 :
[1]
- 3 :
[2, 3, 4]
- 2 :
[5, 6]
, - 1 :
[7]
其實也就會發現,因為排除掉已經拜訪過的,所以時間複雜度結果就會是O(n)
。
後記
說實話,我並不經常計算時間/空間複雜度,對於學術上的一些東西也有點忘了。歡迎留言分享討論~~
LINE Pay贊助 信用卡小額贊助