Coding4Fun - .NET 老司機挑戰 BFS 程式面試考題
7 | 8,842 |
前陣子有支模擬面試 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.
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 的工作,照樣可以領薪水過的好好的.