#59 出國工作的 Why and How?

如果自己的家鄉有個地方可以滿足自己的理想並且能得到好的待遇，我相信大部份的人會選擇留在自己的家鄉工作．就像在花蓮台東長大的孩子，若是踏上了軟體開發一途，幾乎應該都會離開自己家鄉到北部或其他地方找工作，一來工作機會多，二來待遇也比較好．相同地，如果台灣的資訊業滿足不了你的理想或期望的待遇，你一定也希望找台灣以外的機會．但從台灣到國外並不像從花蓮到台北那樣地單純．所以，我寫這篇文章是用來留下一個記錄，讓年輕人參考有什麼方式可以進行．

再談論可行的方法之前，請先好好想一想你為什麼想出國工作．以下的原因可能是大部份人的答案:

1. 為了理想: 希望到具有規模的軟體公司接受更多的考驗來充實自己的人生經驗．
2. 為了更好的待遇: 台灣薪資普遍低落，想追求更好的薪水．

原因可能有上百種，但這兩種應該是符合大多數人的答案之一．水往低處流，人往高處爬，這是再自然不過的事情．因此，我先就這兩個原因說明．

第一，為了理想．以台灣的純軟體開發產業來說，真的不多，若你還想找個有軟體產品賣向全世界的公司，可能用手指頭就數完了．畢竟，台灣的整體 IT 產業結構並不是強於這一塊．早期的那些軟體產品，如作業系統，資料庫系統，程式語言，辦公室軟體或是一些企業用的商務軟體，這些早被許多美國公司和其他國家的軟體公司搶佔了市場．所以這一類型的工作基本上都給在台灣以外才能找的到．較近期的手機作業系統，也早被 Android 和 iOS 把市場括分光了．因此，要做出一個手機作業系統跟 Google 和 Apple 去對拼，以目前來看幾乎是不太可能的事情．因此，在台灣的軟體公司大部份都是做商業用或消費端的應用程式，例如開發 ERP, CRM, 製造業用的 MES 產品等．這類型的軟體除了軟體開發本身的知識外，還需要有其他領域的專門知識，如財務會計或製程等等．因此，你在台灣能找到的軟體工作大部份都是這類型的工作，也就是說用某公司的作業系統，用某公司的程式語言，用某公司的資料庫系統來開發自己所需的商業軟體，這類的工作在許多的國家都有．因此，如果你想做的是這種商業軟體，那就不一定要離開台灣．例如，台灣有許多製造業大廠，全世界沒幾個國家有台灣製造業的能力，因此若要從事製造業的軟體開發，離開台灣不見得能學得較多經驗．如果你想做的不是這種應用程式面的軟體，而是還再往底層走的，如作業系統，程式語言等等，那麼離開台灣到外面找工作看來是必然的．

第二，為了更好待遇．這點其實不需要太多說明了．錢嘛，人之常情，大家都懂的!

接下來，我記錄下我看到的可行方法．

這幾年我在網路上看到有越來越多的人想嘗試著找國外軟體公司的工作．有的人到日本，有人去新加坡，有人遠渡重洋到了歐洲或美國．我之前看到日本 Amazon 到台北招聘人才的消息，裡面曾提到會不會日文不是絕對必要的條件．從招聘的介紹文來看，在日本 Amazon 有許多外國人，因此他們內部反而比較需要英文．我想這是比較特別的例子，貼那文章的是一位已經在日本 Amazon 工作的台灣人，已經有前人成功了，後面的人也可以參考其做法．由於我本身是到美國，所以我分享美國這一條路的情況．通常來說，要到美國工作有幾條路可以選擇:

1. 透過念書: 來這邊念個大學或碩士 (網路上俗稱洗學歷)，畢業後就可以合法找工作．在美國找工作的競爭很大，因為實在太多人，每年都有一堆中國和印度來念 computer science 的學生，而且美國政府每年釋放的工作簽證有一定的限額，所以不代表你找到工作就沒事了，因為沒抽到工作簽證的話，還是得打包回家．我覺得許多事情一切都是緣份，不用太強求．幾年前，我工作的單位來了個剛畢業的印度人，想想他也好不容易找到了在微軟的工作，但偏偏運氣不好就是沒抽到工作簽證，最後只能打包回印度去．一般的大公司比較不會要求求職者要有美國公民或具綠卡的身份，但許多小公司就比較會要求．因此，無形中也造成要擠進大公司還真的不光是實力的問題，還需要有運氣．
2. 透過公司內轉: 如果在一般美商公司而且他們在台灣或是你工作的國家裡有分公司的話，透過公司內轉到美國也是一種方式．例如，從台灣 Google 到美國 Google, 從中國微軟到美國微軟等等．
3. 到美國自行創業: 這需要許多資金，我想這應該不是大部份的人會走的一條路．
4. 取得合法身份到美國後再找工作: 我以前念書時，有一位中國來的同學，他老婆跟著他一起到美國來念書，後來他老婆找到了一家小公司的工作．相當利害，但這需要轉換簽證，因為陪老公念書來的簽證和一般工作簽證不同．

如果你還年輕 (如三十歲以下)，我會建議你走第一條路．在美國找科技業的工作，最好還是有一張美國學校的學歷．如果你想要到好一點的公司，那麼學校最好是榜上有名，也就是大約在美國排前一百名的學校．另外，在學校念書時，也能讓自己加強英文的聽和說，這是很重要的部份．即便是你考過 TOEFL 到美國來念書，那還是差很多．因為你要加強的不僅是老美的英文，你還得熟悉各地的口音，因為工作後遇到的人可能來自不同的國家，尤其是印度人很多．想要跟他們打交道，還真的得多練習聽懂他們的英文．

在美國這裡的科技業文化跟亞洲的許多公司有很大的差別，工程師也是可以做到年紀很大的，我想這是一般亞洲公司比較難發生的，我想在台灣公司也是如此．所以，在美國做技術職不見得會比管理職差．

如果你只是為了更好的待遇而想出國工作的話，我提供以下的資料給你參考．以我在西雅圖的生活以及在微軟公司從事工程師待遇做為例子．

1. 薪資: 在微軟公司，剛畢業的社會新鮮人或是應徵初階工程師的人，年薪大約是十萬出頭美元．微軟公司給的薪資不是最頂尖，但也算不錯．如果是到 Facebook 或 Google，有機會可以再高一點．
2. 所得稅: 以年薪十萬出頭來說，單身的人要繳的稅大約是 30%，如果是一個小家庭有老婆小孩要養，稅率大約是 20%．
3. 房價: 西雅圖這房價這幾年漲的很多，我現在租屋處的對面剛蓋好了新房子 (town house)，每一戶有三層樓，三層樓一共面積大約 56坪，一樓是車位，二樓是客廳廚房，三樓是寢室，要價 86 萬美元，這價錢也差不多可以在台北市買個不錯的公寓，而在我這區域每年要繳的房屋稅，這可是比台北的房屋地價稅高很多．
4. 房租: 我以前也曾在台北租過小套房，以我經驗來看，等級差不多的公寓，在房租上西雅圖 (非市中心) 比台北 (市中心) 高個 2 - 3 倍左右．
5. 醫療: 微軟公司提供不錯的醫療保險，若看一個小病 (如發燒，喉嚨發炎)，自付費用可能是一兩百美元．是的，你沒看錯，是美元．你該好好珍惜台灣的醫療資源和便宜的費用．前幾年，我有次去看了心臟專科，看了醫生，照了心電圖，照了超音波，抽個血檢查，事後醫生打電話跟我說明結果，這樣子的診療自付額是四百多美元．請記得我前面說了，微軟公司提供不錯的醫療保險，如果沒提供那麼好的醫療保險，那麼自付額的比例將會拉高．
6. 吃飯: 這裡在外面餐廳吃飯貴，我在附近一間便宜餐館吃中飯跟你在台北 101 地下樓的美食街吃一頓是差不多的價錢．

大致上粗略地算一下，如果你在台灣已經有了一百多萬到兩百萬的年薪的話，那麼到美國西岸來工作不見得能比你在台灣能存下更多錢．若看長遠一點，在台灣年薪兩三百萬應該是工程師薪資的天花板了，在美國，如果你能做到資深工程師的位置或是當上主管的話，純以金錢考量是值得來這拼一下的．

最後，每個人都有權利選擇自己的人生，看你要的是什麼，就努力把時間花在那上面，讓自己的人生能豐富精彩些．

Hope it helps,

閱讀全文

#58 資料庫引擎對交易 (Transaction) 的執行情況

在上一次文章裡介紹了基礎的交易 (Transaction) 性質與特點，讓你可以了解為何關聯式資料庫引擎需要它．在一般的情況下，一個資料庫引擎在同一個時間內服務的應用程式非常可能不只一個，而且同一個應用程式也可能在同一個時間發出兩個不同的交易來要求資料庫引擎執行．因此，我們都知道一個資料庫引擎在同一時間執行多個來自用戶端的交易是相當平常的事情．同時可以服務多個用戶端等於是增加了整個系統的處理效能，也因為要同時服務多個用戶端，資料庫引擎的效能對於磁碟存取就會變得相當敏感．因為磁碟存取速度快，整體效能才夠快．但只有磁碟效率快就夠了嗎? 在上一次文章裡介紹了交易的特點之後，你就能明白光是快還不夠，還需要在多個交易執行讀取之間不造成衝突才行．因此，資料庫引擎的設計就會面臨兩個挑戰:

1. 如何執行多個交易時還能保持資料的正確性?
2. 如果硬體出錯或是用戶端取消交易執行時，資料庫引擎該如何處理以保持資料的正確性．

為了面對這兩個挑戰，資料庫引擎得引進一個排程 (Schedule) 的想法．所謂 Schedule 是指一連串的動作 (讀或寫)，而這一連串的動作可以是由不同的交易而來的，更重要的是不論這份 Schedule 裡那一個交易先執行，其結果都該和 Schedule 的結果一致．這樣講可能有點抽象，直接看下圖:

資料來源: 我以前在學校的筆記

上圖是一個 Schedule，裡面有兩個交易，分別是 T1 和 T2，其中 T1 有 4 個動作，而 T2 有兩個．時間軸是由上而下，所以 R(A) 是整個 Schedule 裡第一個動作，它代表到 A 做讀取動作，而 W(C) 是最後一個，它代表到 C 做寫入動作．這份 Schedule 安排的很好，因為 T1 讀寫的對象和 T2 完全不同，所以這兩個交易之間不會產生衝突的情況．而每一個交易最後都會有一個 commit 的動作，用來告訴資料庫引擎可以把放在暫存區的結果寫回到磁碟上．如果資料庫引擎可以安排出好的 Schedule，似乎就能克服先前說的兩個挑戰．接下來看一個簡單的例子．

假設銀行要執行兩個交易，一個交易是做轉帳，從 A 帳戶轉 100 元到 B 帳戶，另一個交易是做分派利息，兩個帳戶同時增加 50% 的利息．以動作來看，第一個交易有兩個動作，A=A-100 以及 B=B+100，第二個交易也有兩個動作，A=A*1.5 和 B=B*1.5．假設，不同的用戶端分別同時發出這兩個交易，那麼資料庫引擎該怎麼設計 Schedule? (無法保證 T1 , T2 那一個會開始執行)

如果 Schedule 被安排的如下:

資料來源: 我以前在學校的筆記

這份 Schedule 是可行的，因為它的結果跟單獨先執行 T1 再執行 T2 是一樣的．如果 A , B 都有 100，先執行 T1 再執行 T2，這樣 A=0, B=300 符合這份 Schedule 的預期，所以它是可行的．

如果 Schedule 被安排成另一種:

資料來源: 我以前在學校的筆記

這份 Schedule 似乎就不行了，因為順序影響結果．假設 A, B 一開始有 100，先執行 T1 再執行 T2，變成 A=0, B=300，但是這份 Schedule 完成之後是 A=0, B=250，顯然這份 Schedule 裡動作的順序安排的不適合了．

設計出適合的 Schedule 讓資料庫引擎可以一起執行多個交易也算是增加效能的方法之一．下一篇文章會再繼續談到為何需要好的 Schedule 以及動作衝突時如何解決．

閱讀全文

#57 出神入化的用介面 第一集_什麼是介面 (Interface)

出神入化這詞用的誇張了，為何選用這詞呢? 在 2016 年底辦了一個 .Net公益課程，課後的問卷裡詢問未來若有機會，大家有興趣聽什麼主題的內容．結果有位朋友寫了 "出神入化的用介面"．我想這應該是當天課程上曾提到跟 Interface 有關的事情．後來，我想了想，這主題要描述的清楚並不是件容易的事，也不是三兩句話可以交待的完．所以，用一個說故事的方式來說明這個主題．透過這個主題可以一直延伸到許多程式設計和軟體開發上的事情．

如果你在業界有多年的軟體開發經驗，相信你對 Interface 一定有某種程度以上的使用與了解．但如果你現在還是一個在學的學生或是剛進入職場沒多久的社會新鮮人，也許你對 Interface 的了解可能只限於課本上或是老師口授而來的知識．由於 Interface 這種東西並不是什麼學術研究的題材 (應該說這是很舊的題材了)，再加上許多學校裡的教授大部份很少有大量的產業界開發經驗，因此你能從課本或老師那邊得到的了解便是相當有限的．不論你是在業界打滾多年的好手或是剛進入職場沒幾年的菜烏，先來讓我們一起回想一下當初在學校裡上的物件導向程式語言的課程．也許許多人在學校並沒有上過這門課或是學校沒有開這門課，可能是一邊工作一邊看書學習．不論是那一種方式，我相信你一定都看到課程上或書本上介紹 Interface．當你看了 Interface 之後，你覺得你有什麼感覺嗎 ?

老實話，我以前在學校學的時候，還真的沒掌握到重點．只是覺得奇怪，為什麼要多弄一個 Interface，感覺上好像多了一個用不到的東西．其實，後來才發現，並不是用不到，只是還不會用而己．在物件導向式程式設計的世界裡，你一定都知道什麼是 Class，也一定知道什麼是 Object．這關係就有點像關聯式 (Entity relational model) 資料庫裡的 table schema 與 table 裡的資料．舉個例子，在資料庫中建立一個表格時，你一定會告訴資料庫引擎你需要的表格是長什麼樣子．如一個 int 欄位，一個 varchar(50) 欄位，以及一個 boolean 欄位．因此，你能寫入的資料一定要符合這個 table schema 的定義．相同的感覺，當你的 Class 定義好它的長相時，之後依這個 Class 建立出來的 Object 裡面的內容值也一定符合這個 Class 的定義．在資料庫設計中，表格和表格之間可以建立所謂的一對一或一對多等等的關係，同樣的在 Class 和 Class 之間也可以設計出這樣的關係．物件導向式模型有一個東西是關聯式模型裡面所沒有的，那就是 Interface．

Interface 和 Class 都是用來定義 Object 要長成什麼樣子．如下面看到的簡單例子．

class IAmAClass {
    public int Id { get; set;}
    public string Name { get; set;}
}

在撰寫程式時，你可以直接透過 new 這關鍵字來告訴電腦你需要一個記憶體空間來放一個依照 IAmAClass Class 長相所建立出來的 Object，如下

IAmAClass cls1 = new IAmAClass();
IAmAClass cls2 = new IAmAClass();

依照上面的程式碼，此時記憶體裡面有兩個 IAmAClass objects, 一個名字叫 cls1，另一個叫 clas2．這兩個 objects 是依照 IAmAClass 的長相所建立出來的，所以當我想要操作這兩個 objects 時，我就知道他有那些公開的屬性和方法可以使用．這些是最基本的事情，相信你一定知道．接下來，那 Interface 呢 ? 前面說了，Interface 和 Class 都是用來定義 object 要長成什麼樣子，那我們能直接定義一個 Interface 透過 new 關鍵字來建立 object 嗎? 很可惜，似乎不行．Interface 和 Class 好像蠻像的，但 Interface 卻不能直接透過 new 關鍵字來建立 object，這其中一定是有什麼設計上的考量!

相信你以前也想過這樣的問題．Interface 的用途很多，在第一集的文章裡，我先提出一個用途讓你看到為什麼有 Interface 的存在是比較好的．

假設，你的公司有好幾個部門，每個部門做的工作都是獨立又相依，意思就是說你要達成某項任務時，必須要使用其它部門的程式．舉例來說，你做的是一個寄信的程式，但信件的內容是根據各部門的需求而產生的，你不負責信件內容的產生，你只負責做寄信的動作．此時，A部門告訴你它的信件內容是 MailAContent class，它的長相如下 (細節忽略):

class MailAContent {
    public string ReceipentEmail { get; set;}
    public string HtmlContent { get; set;}
    public string Subject { get; set;}
    public bool Importance { get; set;}
}

於是，當你寫寄信程式時，你必須要拿到 MailAContent class 的定義，也就是說你得把對方的 dll 加入到你的程式專案裡，因為要這麼做，你的程式才能明白什麼是 MailAContent class．因此，當你在製做寄信程式時，你的程式某個片段可能會長成如下:

public void SendEmail(MailAContent mail) {
    EmailServer server = new EmailServer();
    server.IP = "1.1.1.1";
    server.Username = "admin";
    server.Password = "password";
    server.Connect();
    server.Send(mail.ReceipentEmail, mail.HtmlContent, mail.Subject, mail.Importance); // 假設寄信程式只需要知道這四個資料
    server.Close();
}

到目前為止，看起來似乎合理．接下來，B部門也會產生 email，也要透過你的寄信程式來把信寄出去．但 B部門有自己的 email class，叫 MailBContent class，長相如下:

class MailBContent {
    public string ReceipentEmail { get; set;}
    public string HtmlContent { get; set;}
    public string Subject { get; set;}
    public bool Importance { get; set;}
}

於是你為了要把 B部門的 email 寄出去，你也寫了以下的程式在你的寄信程式中．

public void SendEmail(MailBContent mail) {
    EmailServer server = new EmailServer();
    server.IP = "1.1.1.1";
    server.Username = "admin";
    server.Password = "password";
    server.Connect();
    server.Send(mail.ReceipentEmail, mail.HtmlContent, mail.Subject, mail.Importance);
    server.Close();
}

結果看到這程式，發現有點蠢，這麼多重覆目的的程式碼，於是進行了一個小小的 refactor :

public void SendEmail(MailAContent mail)
{
    SendEmailInternal(mail.ReceipentEmail , mail.HtmlContent , mail.Subject, mail.Importance);
}

public void SendEmail(MailBContent mail)
{
    SendEmailInternal(mail.ReceipentEmail , mail.HtmlContent , mail.Subject, mail.Importance);
}

private void SendEmailInternal(string receipent, string content, string subject, bool importance) {
    EmailServer server = new EmailServer();
    server.IP = "1.1.1.1";
    server.Username = "admin";
    server.Password = "password";
    server.Connect();
    server.Send(receipent, content, subject, importance);
    server.Close();
}

經過小小的 refactor 之後，你會覺得程式碼好像比較沒那麼蠢了．但接下來, C部門，D部門相繼地把需求提過來，而你也發現每個部門的 email class 都是不一樣的 class，因此你就能想像你的寄信程式就要為 C部門再多弄一個 SendEmail(), 也要再為 D部門再多弄一個 SendEmail()，如果有十個部門而且每個部門的 email class 都不一樣，那麼你就得有十個 SendEmail()，這時你應該會發現程式碼真的有點蠢了．除此之外，因為你寫的寄信程式是要提供給其他部門使用，讓他們的程式碼呼叫你的 SendEmail() 才能寄信．此時，你會發現因為你的寄信程式 reference 每個部門的 email class，所以使得每個部門都要 reference 其他部門的 email class 才能正確地 compile．這真的是相當蠢的一件事．透過這個例子也剛好說明了 Class 真的是軟體開發的一個麻煩源頭之一．

從上面的例子來看，你會發現如果每一個部門都採用相同的 email class 的話，那不就好了嗎? 可能的做法是把 email class 定義在某一個共享元件裡，然後要求每個部門都 reference 這一個共享元件以使得用到相同的 email class．理論上，這是一個可行的方法．在這個例子裡，email class 只是一個很簡單的 data structure，沒有任何 implementation code．如果今天遇到的是一個有 implementation code 的 email class 時，就會遇到一個小麻煩，它就是當這個 email class 改版時 (修改 implementation code)，就得通知所有部門更新這一個共享元件．除了這方法以外，你還可以用 Interface．

如前面所說，Interface 和 Class 都是用來定義 Object 要長成什麼樣子，但 Interface 不能用來建立 object，卻可以用來表達一個 object 是否具有其他的 "特定長相". 在元件之間的互動，認定的是長相而不是真正的 object 是什麼，並且放在共享元件裡的是 Interface 而不是 implementation code，因此 email class 改版時，共享元件不需要更新，只有在 interface 改版時才需要更新共享元件．

因此，以上述的例子來說，在共享元件的 interface 長成這樣:

Interface IMailContent {
    string ReceipentEmail { get; }
    string HtmlContent { get; }
    string Subject { get; }
    bool Importance { get; }
}

以 A部門來說，它的 email class 改成如下:

class MailAContent : IMailContent 
{
    public string ReceipentEmail { get; set;}
    public string HtmlContent { get; set;}
    public string Subject { get; set;}
    public bool Importance { get; set;}
}

MailAContent class 使用了 IMailContent，這表示 MailAContent class 一定要有 IMailContent 裡所有成員的 implementation code．一旦 MailAContent class 被建立成 object 時，這個 object 既是 MailAContent 也是 IMailContent，也就是說這個 object 有著兩種 data type 的感覺，這樣說不精確，但感覺起來像是如此．接著，寄信程式可以改成如下:

public void SendEmail(IMailContent mail) {
    EmailServer server = new EmailServer();
    server.IP = "1.1.1.1";
    server.Username = "admin";
    server.Password = "password";
    server.Connect();
    server.Send(mail.receipent, mail.content, mail.subject, mail.Importance);
    server.Close();
}

當 SendEmail() 被 A部門呼叫時，傳進來的 IMailContent 其實是 MailAContent object，因為這個 object 實做了 IMailContent ，所以這樣傳進來並不會有什麼問題．在 SendEmail() 裡面只認得 IMailContent 的長相，因此在 SendEmail() 存取該物件的成員時，只能用那些 "看" 的到的成員，也就是 IMailContent 上有的成員．同理，當 SendEmail() 被 B部門呼叫時，傳進來的 object 是 MailBContent object，也因為此 object 實做 IMailContent，所以 SendEmail() 執行時不會造成問題．以推類推，所有部門的 email class 都實做了 IMailContent，這樣寄信程式只要一個 SendEmail() 就可以，這樣不是更好嗎?

也許以上寄信這個例子不是很精準，但也把最基本的 Interface 應用呈現出來．如果你還沒機會參與多部門或多人開發的軟體專案，Interface 其實仍是重要的．因為它不僅用在跨部門的情況下相當好用，而且也能幫助你做更好的 unit test．

這集的重點是:

1. Interface 和 Class 都是用來定義 Object 要 "長" 成什麼樣子，但 Interface 不參與 implementation，只專心定義一個 object 能 "長" 成什麼樣子．Interface 提供了 object 一種 "外衣"，不同的 email content object 只要有相同的 "外衣" (IMailContent)，都可以在 SendEmail() 裡面使用．一個 object 可以有多個 "外衣"，因此使得物件導向程式設計變得很彈性也很有趣．
2. 當你要使用別人的 Class 時很可能會造成麻煩，應盡量使用 Interface．以上的故事也告訴你當你把一個 class 建立成一個 object 時，這其實就是許多問題的根源之一．

閱讀全文

#56 Coding面試 LeetCode #230. Kth Smallest Element in a BST

原文的題目網址在這

有好長一段時間沒有到 LeetCode 網站上去看題目了，今天去的時候才發現 LeetCode 網站做了一些小改變並且增加了更多的題目．不僅演算法類的題目增加，也新增了其他種類．如 OO 設計，系統設計等．真的是稱的上軟體工程師面試題目的最佳網站了．我以前在 LeetCode 上寫了很多題目，這網站有一個優點就是它會把你之前寫過的程式碼保留下來，所以我還能看到我之前寫的答案．

這一題是考找出 BST 中第 K 個最小值．要解決這題，有兩個先決條件．第一，你得知道什麼是 BST (binary search tree)，第二，你得知道第 K 個最小值是怎麼來的．基本上，如果遇到 TREE 這方面的題目都考 "特質"．因此，得先把每個 TREE 的最重要特質記在心裡．BST 最重要的特質就是，在任意一個 tree node 上，其左邊 node 的值比自己小，而右邊 node 的值比自己大．比如下面這邊小樹

5
    / \
   3   7

接著，怎麼找第 K 個最小值 ? 凡是遇到 tree 的題目要你比大小或是找第幾個這類跟順序有關的，一定要想到 tree traversal．Tree traversal 有三種，in-order, pre-order, 以及 post-order．其中 in-order 的走法用在 BST 上時，把樹走完後，拜訪的順序剛好就會把值從小排到大．以上圖而例就是 3->5->7，因此想找第 K 個最小值剛好就等於 in-order 走法拜訪的第 K 個 tree node.

如果以上都沒問題的話，接著就直接寫程式了．Tree 的拜訪我一向習慣用的是 iterative 的方法來寫．所以寫出來的程式如下:

如果你在面試時遇到這類的問題，我都會建議用 iterative 的寫法．這能避免使用 recursive，避免的原因就是在於當 tree 很大很大時, recursive 會造成 call stack overflow，這是做產品的公司所不能接收的大禁．

這是我以前的答案，使用 Stack 來記錄拜訪 BST 的走過痕跡．當我再重新 submit 到 LeetCode judge system 後，它告訴我上述的程式花了 189ms 跑完，在 C# 的答案裡面打敗了 41% 的答案．這表示有 59% 的答案效能跑的比這程式還快．看來這程式用了 Stack 果然還是有影響．為了追求更好的效能，把程式改成如下:

再重新讓 LeetCode judge system 測驗後，這次它回傳此程式的效能打敗了 68% 的答案．顯然 32% 的答案有更快的效能，的確很利害．不過 LeetCode 這一題的 test case 中並沒有很大很大的樹，所以用 recursive 的寫法並沒有造成 stack overflow 的現象．

閱讀全文