Coding4Fun - .NET 老司機挑戰 BFS 程式面試考題

前陣子有支模擬面試 YouTube 影片引發討論，不少讀者認為，連基本 BFS 演算法跟 Big O 都不熟，在真實世界的程式面試必死無疑。

雖然在資訊業打滾了幾十年，我因為不是本科系，在學校沒學過資料結構跟演算法這些東西(這對資訊本科生屬肌肉記憶等級吧)，沒正式學過 BFS/DFS，學習及寫程式全靠一股熱情，靠著各式土砲與雞鳴狗盜雜過日子。再偷偷說件事，Big O 呢，我是入行十幾年後的某天在在臉書留言第一次看到，Google 後才知道這個言簡意賅的演算法效率指標... 不過呢，即使不懂這些，畢竟我也做過十幾個大小網站專案(註：都有順利驗收拿到尾款)，還寫過不少框架與程式庫幫助團隊加快開發，自認是個及格的開發者。但若面試都得現場完成這些基本演算法，我應該場場都領無聲卡。

我的理解是 - 這類基本知識不算做好資訊開發的必要條件。資訊職務需求很多樣化，不是只有演算法跟寫程式本身。不少開發工作更著重理解需求、甚至要有業務流程 Know-How 才能勝任，寫程式部分比較像拼積木，理解並熟悉 API 特性，別犯低級錯誤，一樣能把工作做好。甚至溝通技巧有時也比技術能力更重要，有能力問出真正需求勝過寫一堆精美但使用者不想要的模組，有本事說服客戶拿掉三年用一次的功能比花一個人月完成它更威。另一方面，演算法外還有很多技術能力，有時多懂些 CSS 或 SQL 語法還更實用。但不可否認，當其他條件相同，基本觀念正確紮實的開發者，遇到要動手寫演算法或判定架構好壞，更能正確判斷，表現通常會比缺乏觀念的人好，是技術面試用演算法考題篩選應徵者的理由吧!

我自己的觀察，非本科系轉職程式設計的人，不管因工作需求或興趣自學程式語言，多半會聚焦語法、API 或實作技巧，很少人會回頭去練演算法、資料結構等基本功，這也導致即使寫了多年程式，渾然不知 Big O 也不算新鮮事。

我在多年前曾一時興起，看了幾天演算法，但動機不夠強烈(不比在校修課，沒有被當的壓力，東西一枯燥就... 你知道的)，如今腦中對 BFS、DFS 細節連渣都沒留下。但題目看起來挺有意思(題目細節請自己看影片)，一時手癢，便想挑戰「沒學過演算法沒背過題目的多年 .NET 老司機，能不能憑經驗解題？」

雖然順利解出來，以時間來看是不及格的，超過半個小時才寫完(還是中途跑去洗澡想到的靈感，哈)，我依直覺選擇用遞迴解題(註：其實用 while 就夠，但我也沒多想便開始遞迴)，再配合 Dictionary 等 .NET 現有資料結構，第一個版本如下：

using System.Collections.Concurrent;
using System.Diagnostics;

var results = new Dictionary<int, string>();

var sw = new Stopwatch();
sw.Start();
await searchGraph(1);
sw.Stop();
Console.WriteLine($"Elapsed: {sw.ElapsedMilliseconds:n0}ms");
Console.WriteLine(string.Join(", ", 
    results.OrderBy(o => o.Value.Length).Select(o => o.Key)));

async Task searchGraph(int start, string path = "") {
    path = path + start;
    if (results.TryGetValue(start, out var currPath) && currPath.Length <= path.Length) return;
    Console.WriteLine(path);
    results[start] = path;
    var neibours = await fetchNeighbours(start);
    foreach (var n in neibours) {
        await searchGraph(n, path);
    }
}

async Task<int[]> fetchNeighbours(int node) 
{
    await Task.Delay(1000);
    switch (node) 
    {
        case 1: return new[] { 2, 3, 4 };
        case 2: return new[] { 1, 5 };
        case 3: return new[] { 1, 5 };
        case 4: return new[] { 1, 6 };
        case 5: return new[] { 2, 3, 7 };
        case 6: return new[] { 4, 7 };
        case 7: return new[] { 5, 6 };
        default: return Array.Empty<int>();
    }
}

我自做主張在 searchGraph() 加了第二個 path 參數 (亂改題目，應該當場謝謝再聯絡...)，用 Dictionary<int, string>() 用字串記錄每個節點從 1 走到該點一路經過的節點，取最短者。再來，用 foreach 遍歷子節點並以遞迴深入，得到結果如下：

這個題目設計成呼叫 API 會延遲一秒才回傳結果(之前試過 WebAPI 還能存取，後來被停用，改以函式寫死回傳結果模擬)，第一版耗時 10 秒。

考量查詢太耗時，我加了 Cache，查過的節點就不再查，預計可省下三次查詢：

var cache = new Dictionary<int, int[]>();

// ... 略 ...

async Task searchGraph(int start, string path = "") {
    path = path + start;
    if (results.TryGetValue(start, out var currPath) && currPath.Length <= path.Length) return;
    Console.WriteLine(path);
    results[start] = path;
    if (!cache.ContainsKey(start)) cache[start] = await fetchNeighbours(start);
    var neibours = cache[start];
    foreach (var n in neibours) {
        await searchGraph(n, path);
    }
}

省下 3 秒，順利加快到 7 秒：

過程有跑迴圈查三個點的狀況(例如 2,3,4)，若改用平行處理會再快一點：

var cache = new ConcurrentDictionary<int, int[]>();
var results = new ConcurrentDictionary<int, string>();

// ...略...

async Task searchGraph(int start, string path = "") {
    path = path + start;
    if (results.TryGetValue(start, out var currPath) && currPath.Length <= path.Length) return;
    Console.WriteLine(path);
    results[start] = path; // 可能有 Thread-Safe 問題，先裝死
    if (!cache.ContainsKey(start)) {
        cache.TryAdd(start, await fetchNeighbours(start));
    }
    var neibours = cache[start];
    await Parallel.ForEachAsync(neibours, async (n, cancelToken) =>
    {
        await searchGraph(n, path);
    });
}

最終成品，4 秒完成。

[2023-04-27 補充] 經網友指正，一語驚醒夢中人，我這是用 DFS 硬解 BFS 題目啊，自己都覺得好笑。(這恰巧也證明了：腦中有概念，看問題更犀利)
DFS、BFS 兩種演算法各有適用情境，用錯了也能硬解，但肯定不是最佳解，這題能過關，其他情境未必可行。

土法鍊鋼完，來看看標準 BFS 寫法該怎麼做？

超精巧! 一個 Queue 放探索軌跡、一個 Queue 存結果，一個 HashSet 記錄踩過的節點，用一個 while 包 foreach 打完收工，這種小問題用不上遞迴，不必動用複雜的資料結構就能完成。
[2023-04-27 更新] 最重要的是，BFS 沒有多餘查詢迴圈，也不需要什麼 Cache 機制避免重複查詢，沒一絲浪費，簡潔到令人讚嘆。相形之下，我是拿著 .NET 給的豪華武器狂掃一通，靠蠻力通關啊。

var sw = new Stopwatch();
sw.Start();
await searchGraph(1);
sw.Stop();
Console.WriteLine($"Elapsed: {sw.ElapsedMilliseconds:n0}ms");

async Task searchGraph(int start) {
    var queue = new Queue<int>(new int[] { start });
    var result = new Queue<int>();
    var visited = new HashSet<int>(new int[] { start });
    int currVertex;
    while (queue.Any()) {
        Console.WriteLine($"Q: {string.Join(", ", queue.ToArray()),-10} V: {string.Join(", ", visited.ToArray()),-20} R: {string.Join(", ", result.ToArray()),-20}");
        currVertex = queue.Dequeue();
        result.Enqueue(currVertex);
        var neibours = await fetchNeighbours(currVertex);
        foreach (var n in neibours) {
            if (!visited.Contains(n)) {
                queue.Enqueue(n);
                visited.Add(n);
            }
        }
    }
    Console.WriteLine(string.Join(", ", result.ToArray()));
}

納入教科書的演算法歷經千錘百練，被全世界 Code Review 過，肯定最簡潔最有效率，許多巧妙寫法是我一輩子都想不出來的。

我有個比喻。有些奇妙繩結打法，手法不複雜但具神奇特性，例如愈拉愈緊，輕輕一抽又能輕鬆解開，讓人心中滿是讚嘆。若沒人教沒看過示範，給我一條繩子自己玩半年都未必想得出來：

來源

經典演算法便像前人發明的巧妙手法，自己未必能想到，但在特定場合異常好用，那還不記下來？(除非要面試，倒也不必硬背，需要時能想到即可) 遇到特殊場合，便多一項武器可以用；而學習其原理或技巧，也能舉一反三應用在其他地方。無論如何，都能讓你實力更堅強。

非本科系出身，該怎麼看待這些基本功？若沒打算參加頂尖軟體廠商面試，不必知道演算法跟 Big O 也能在資訊業混得有聲有色，表現比本科系學生好的大有人在，我看過許多例子。因此，這些知識是成為優秀資訊人員的條件之一，但非必要條件。換個角度，既然都進了這行，花點時間多懂一些，增廣見識確立正確觀念，也不是壞事，決定把演算法重新排入學習清單。(謎：沒發現你的學習 Queue 早就爆了？)

Using .NET to tackle the BFS algorightm problem.