2

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

 1 year ago
source link: https://blog.darkthread.net/blog/bfs-code-test/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

.NET 老司機挑戰 BFS 程式面試考題-黑暗執行緒

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

Fig1_638181201524783058.png

雖然在資訊業打滾了幾十年，我因為不是本科系，在學校沒學過資料結構跟演算法這些東西(這對資訊本科生屬肌肉記憶等級吧)，沒正式學過 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 遍歷子節點並以遞迴深入，得到結果如下：

Fig2_638181201526562560.png

這個題目設計成呼叫 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 秒：

Fig3_638181201528323433.png

過程有跑迴圈查三個點的狀況(例如 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;
    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 秒完成。

Fig4_638181201530080978.png

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

超精巧! 一個 Queue 放探索軌跡、一個 Queue 存結果，一個 HashSet 記錄踩過的節點，用一個 while 包 foreach 打完收工，這種小問題用不上遞迴，也不必動複雜的資料結構就能完成。

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

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);
        if (!cache.ContainsKey(currVertex)) {
            cache[currVertex] = await fetchNeighbours(currVertex);
        }
        var neibours = cache[currVertex];
        foreach (var n in neibours) {
            if (!visited.Contains(n)) {
                queue.Enqueue(n);
                visited.Add(n);
            }
        }
    }
    Console.WriteLine(string.Join(", ", result.ToArray()));
}

Fig6_638181201531865744.png

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

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

thumbnail
來源

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

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK