前陣子有支模擬面試 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 過,肯定最簡潔最有效率,許多巧妙寫法是我一輩子都想不出來的。

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

thumbnail
來源

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

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

Using .NET to tackle the BFS algorightm problem.


Comments

# by Joker

非本科加一,西餐廚師,但是還是會學,碰到學起來就對了。

# by 小雞

好啦 我去面試都沒遇到問這個的 我也不會 XD 有遇到自然就會學

# by Jacky

我倒不認為重點在知不知道怎樣寫,而是在於對有甚麼 algorithm,它們可以解怎樣的難題。始終,現實中沒有人告訴你這個這個project請用BFS解決,而是有一個現實難題出現了,你認不認得是哪一個algorithm可以提供有效解法的。

# by Cc

Big O 是數學跟資訊無關, 但資訊要有效率就要懂數學, 但除非想做演算法的延伸應用或發明不然也不用懂數學, 因為核心在 Framework 都寫完了, 一般人只要能寫出有效率(ex. 大量字串組合知道用 StringBuilder)不要放雷(ex. 日期處理不用共用函式硬自己亂算結果某日引爆)的程式就上帝保佑了~

# by Gc

難怪 Windows Bug 那麼多~

# by Nelson

無目的學演算法CP值超低的 不推薦 把時間用在通用知識上都不夠了

# by bruce

大部份台灣本土企業的資訊工作,不懂這些電腦科學的基礎知識能活下來的原因就是你在台灣. 因為 input size 很小,頂多只有台灣人. 當你有能力到了世界一流的科技公司時,你的 input size = 全世界的許多國家,那是台灣人數的上千上萬倍,許多工作就連本科系畢業的學生也不一定能勝任. 有沒有強壯的知識,就完全展現在這裡了. 你應該無法想像當你 Google search 時,按下 search button 十秒鐘後才會出現搜尋結果,早被你罵翻了,公司可能也早倒了. 所以,非電腦本科系能在台灣活的好好的,不是你利害,也不是你運氣好,是環境讓你不會有那麼多的挑戰 (big input size),隨便寫個爛爛的 big O 程式也能過關. 只要你老闆不介意了,自己也不用跟自己過不去,想學就學,不想學也不會擔誤到 small input size 的工作,照樣可以領薪水過的好好的.

Post a comment