#38 Coding 面試 - LeetCode #2 Add Two Numbers

原文題目 https://leetcode.com/problems/add-two-numbers/

這題是個基本的 Linked List 考題，如果題到這類型的 List 題目，若題目沒特別說的話，就一律想成是 Single Linked List 了．其實，我個人不是很喜歡 List 考題，原因是大部份的問題都蠻無聊的，可能就在 List 上把元素搬來搬去，而且不一定會有一個很好的邏輯來搬這些元素，所以就會造成一個 function 寫的長長的．像這一題就是這樣．

題目給了兩個 input list，要把每個元素加在一起後，然後輸出一個最後的 list．其實也蠻簡單的，你只要在這兩個 input list 上一個一個元素去拜訪，然後把加起來的答案寫到新的位置上，同時再注意進位的事情．並且你也要考慮到兩個 input list 的長度可能是一樣長，也可能是不一樣長，甚至可能是空的．如果你按照這個想法寫，答案就可以寫的出來．

但是，就這麼簡單嗎 ? 基本上是的，但要注意一件事，上面的想法是會製造出另一個新的 list，算到最後把這個 list return 出去．這樣做的話就等於空間複雜度是 O(n+m) 了，假設 n,m 分別是兩個 input list 的長度．

所以，比較好的做法是讓空間複雜度變成 O(1)，也就是說每當計算一次元素的加法時，就把答案寫到某一個 input list 上，最後 return 這一個 input list 就行了，所以就不需要宣告出其他不是 O(1) 的空間．

參考的程式碼如下:

沒錯吧，又臭又長! 如果你能想到更好的方法來簡化以上的程式碼，再麻煩你教教我! ^_^

閱讀全文

#37 資料庫基礎 - Clustered Index 與 Non-clustered Index

在編號 #33 的文章中介紹了什麼是 Index．這可以說是資料庫對資料能快速尋找的主要方法，基本上也是一個用空間換取時間的方法，也就是為了更快速地找到資料，於是犧牲了更多的硬碟儲存空間來達成這件事．也因為如此，所以資料庫引擎也需要有相對應的功能來妥善管理這些特別的儲存空間．然而，儲存空間的內容不同也會影響不同的管理方法，所以這一篇文章將來介紹不同的儲存空間 -  Clustered Index 和 Non-clustered Index．

如果你曾撰寫過資料庫應用的相關程式或是你本身是資料庫管理員，相信你一定聽過 Clustered Index 和 Non-clustered Index．這兩個 Index 有什麼不同呢 ? 給一個比較簡單直覺的答案就是 Clustered Index 是根據某個資料在儲存空間上排列的順序而建立，而 Non-clustered Index 不一定要按照實體的資料排列順序而建立．

把 #33 那篇文章中的圖片再貼過來一次．

之前提過這是一份資料，按照學生證號碼排列寫入儲存空間的概念圖，所以你可以看到學生證的號碼有 1,5,7,11,13,16,23,24,36 這些號碼，而這些號碼基本上會被選做為 primary key，所以資料庫引擎可以利用這個號碼做為資料儲存位置的順序．因此，號碼小的一定寫在號碼大的前面，若不是在同一個 page 上的話，那一定是在前面的 page 上．所以，如果資料庫引擎用學生證號碼做為依據來建立 Index 的話，它的 Index tree 就有如上圖所承現．這一個 Index tree 我們就稱為 Clustered Index，也就是這個 Index 是依據決定實體順序排列的資料而建立起來的．其他種類的 Index 就稱為 Non-clustered Index．

所以，你就能知道為什麼在建立 Clustered Index 的時候你只能建立一個，而 Non-clustered Index 可以建立好多個，那就是因為實體順序排列只會有一種．

在尋找資料時，Index 特別強大的功能是在於某一個範圍內的尋找，比如，你要找學生證號碼 5 號的資料，或是找學生證號碼大於 20 號的資料．這類型的範圍尋找對使用 Index 來說是最好的．而 Clustered Index 和 Non-clustered Index 在這方面又有什麼差別呢 ? Clustered Index 的建立是依據資料實體的排列順序，所以當你執行了一個 SQL command 如 select * from students where ( ID < 10 and ID >0) ，你就會發現這只需要讀取一個 page 而己，這是以上圖為例子．如果你執行了另一個 SQL command 如 select * from students where street = '1st'，假設有一個 Non-clustered Index 是根據 street 資料而建立的，所以當你要尋找 street = 1st 時，這一個 Non-clustered Index 就會被用到，而且很有可能會指到許多不同的 page，比如 1 號學生和 36 號學生都住在 1st street．所以，Clustered Index 的尋找所需要讀取的 page 數量理論上會小於或等於 Non-clustered Index 所需要讀取的 page 數量．

總結，對資料庫引擎而言，不論是 Clustered Index 或是 Non-clustered Index，尋找資料的過程基本上都是一樣的，由於這兩種 Index 的特性不同，所以造成 Clustered Index 所帶來的維護成本較高 (因為實體的儲存順序就是 Index 上資料的順序，要變動比較麻煩)，而 Non-clustered Index 所帶來的維護成本相對較低 (因為只要改 pointer 指到新的 page)．

閱讀全文

#36 Code Review - 檢視你的程式碼

不論是寫好一個新的功能或是修改 bug，在程式碼都能正確執行並且在 check-in 到 source control server 之前，一定都會有一個 code review 的動作．這件事情通常是由比較資深的人員或對整體程式較為熟悉的人員來執行．Code review 帶來的好處很多，在這裡不一一描述，這對比較資淺的人員或新進的人員來說是一件好事．透過 code review，新進或資淺的人員可以比較快進入情況．有時我們進入了一個龐大程式碼專案，短時間之內蠻難完全了解所有細節和該團隊寫程式碼的文化，所以透過 code review 來了解程式碼，也是一種學習．

如果你工作的地方有執行 code reivew 的動作，真的恭喜你，畢竟教學相長，透過檢視彼此的程式碼是一種良好的學習方式．因為這跟團隊文化與團隊技術能力與要求上有很大的關係，所以 code review 實在很難說有什麼標準可言．除了程式碼要符合團隊的寫作規定外，要求嚴格的團隊甚至是極為嚴苛的地步．

接下來，我分享一些我以前在 code review 中學習到的經驗．

1. 每個公司或團隊因為人的不同，所以要求的標準也不同，先不用假設對方是來找你麻煩，如果他對你寫的程式碼有意見，他一定能說的出原因，讓你相信他是對的．

2. 如果你寫的是 Java/C# 之類的物件導向的程式，可能就有點小複雜．因為同一個功能因每個人對物件設計理解程度不同而會有不同的設計，再加上會導入一些 pattern 等因素，容易造成你不明白全部的內容時，就犯了一些錯．也不用過於放在心上，這種事情是常常發生的．

3. 以我個人而言，在程式碼效能發揮到極致後，程式碼寫的簡單乾淨好閱讀就行了，但是你很可能會遇到資深的工程師要求你要改的更簡潔．例如，

bool visited;
if (isActive == true) {
    visited = true
}

改成

bool visited;
visited |= isActive

基本上這兩個邏輯是一樣的，如果你被要求要寫成下面那樣的語法，就當做是個學習經驗吧!
其他像是變數名稱，物件名稱或屬性名稱也是會有類似的情況．

4. Comment 寫註解．做產品的公司會連註解也有嚴格的格式要求．如果是一般的程式註解，也是要寫到讓人看的懂，否則有寫跟沒寫是一樣的．

所以，如果你是新人，那就好好享受 code review 的過程吧，因為當你遇到一位功力深厚的前輩幫你 code review 時，保證你會收益良多的．

閱讀全文

#35 Coding面試 - LeetCode #94 Binary Tree Inorder Traversal

這題目出現在這 https://leetcode.com/problems/binary-tree-inorder-traversal/

如果要考 Tree 相關的題目，這一題算是相當經典的考試題目了．我想經典的原因就是 Tree inorder traversal 是資料結構課本裡面一定會教到的內容．大部份的課本裡面都會提供 recursive 的方式來做 inorder traversal，其程式如下

        public List<int> InorderTraversal(TreeNode root)
        {
            List<int> result = new List<int> ();
            if (root == null) return result;
            if (root.left != null)
                result.AddRange(InorderTraversal(root.left));
            result.Add(root.val);
            if (root.right != null)
                result.AddRange(InorderTraversal(root.right));
            return result;
        }

但面試官既然要考你這一題的話，絕對不可能只問你 recursive 如何寫，也一定還會問你怎麼用 iterative 的方式來寫．
如果你完全沒做過相關的練習，一時之間還真的很難想的出來該怎麼把 recursive 改成 iterative. 在這可以分享一件小事，因為寫 recursive 有階層的關係，所以程式的 call stack 就一層一層往上加，上一層結束回到下一層時也自然知道該從什麼地方繼續執行．但是若改用 iterative 的話，就沒有這種記住上次執行到那的好處了．對於這種需要記住位置的情況，就可以直接想想 Stack，因為 Stack 能幫助我們記住走過的痕跡．

所以，改成 iterative 的程式碼如下

        public List<int> InorderTraversal(TreeNode root)
        {
            List<int> result = new List<int> ();
            if (root == null) return result;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode node = root;
            while (stack.Count != 0 || node != null)
            {
                if (node != null)
                {
                    stack.Push(node);     // <-- 幫我們記住位置
                    node = node.left;
                }
                else
                {
                    TreeNode temp = stack.Pop();    // <-- 把上次記住的位置拿出來
                    result.Add(temp.val);
                    node = temp.right;
                }                              
            }
            return result;
        }

沒感覺嗎 ? 多寫幾次就會有了.

閱讀全文

#34 資料結構 - 非電腦科系的工程師們，你們體會多少了呢 ?

我第一次念資料結構時是因為準備台灣的資工研究所考試而念的，當時為了考試再加上時間也不夠多，所以念的很匆忙，沒有太多的時間思考著這門課程的精華．後來，念了研究所之後，研讀了一些學術論文，才慢慢了解到資料結構的精華．在許多學術論文裡都是討論著許多真實世界上的問題，通常這些問題會用一個數學公式或模型來表示，所以接下來的內容討論就可以直接在這數學公式或模型上直接去模擬．而這類的數學公式或模型若要用電腦程式來表達時，通常會發展出適合的演算法與資料結構．所以，這類的論文看多了之後，反而有幫助自己漸漸了解資料結構的精華．

基本上，電腦有二個基本的東西，一個運算器，一個是儲存空間．運算器就是大家所知的 CPU，而儲存空間就是記憶體和硬碟，其中記憶體是速度快但記憶時間較短，而硬碟是速度慢但記憶時間較長．這兩個東西你可以想成他們是長長的紙條，運算器可以在這長長的紙條上寫下資料，也可以讀取資料．

資料結構基本上就包含了兩件內容，一個是你需要用的資料是要寫在紙條上的何處，另一個就是如何在這些資料之間進行讀取或寫入．舉個例子，之前的文章提到 Array 這個資料結構．它的特性就是當你建立這個資料結構時，你必須先在紙條上找到一個符合你需要的足夠大的空間，而在資料之間進行讀取寫入的方式就是直接透過計算要讀或寫第幾個元素，就可以直接算出在紙條上的位址．例如，宣告了一個 byte array，一個有 20 個元素，如果第一個 byte 就是紙條上第 1000 個 byte 的位址，當我們要讀取第 5 個元素時，我們就知道要去 1005 byte 的位址上去讀取資料．

再舉另一個例子，Linked List．當你宣告了一個 Linked List 時，一開始你會先加入一個元素，這個元素可以寫在紙條上任何足夠空間的地方，而當你再加入另一個元素時，此時運算器就在紙條上任意一個足夠空間的地方把資料寫下，然後再回到第一個元素的位址上，把第二個元素的位址寫在第一個元素的空間中．所以，你可以知道在每個元素的空間中，除了元素的資料以後，還有下一個元素的地址．因此，當你想知道這個 Linked List 有多少元素時，你就必須從第一個元素一直讀到最後一個元素．

因此，課本裡面教的都是一些最基本的資料結構，就好像數學裡的四則運算一樣．電腦世界裡面的執行過程都是把紙條上的資料讀過來寫過去．當你發現你需要的問題很難用這些基本的資料結構來表達時，這時就是可以發明新的資料結構的時候了．

也許你會問，那這些跟平常的工作有什麼關係嗎 ? 比如，每天都在寫 JavaScript 搞前端畫面或是都在寫 java 寫後端程式．其實，多多少少會有關係的，尤其是你用物件導向在寫程式時，你所宣告的 class 就像是你定義了一種資料結構，這個 class 裡面所用到的儲存方式和運算方式都會大大地對程式在各方面有影響．就像是你知道了 Array 和 List 有何不同，你才會選得較適合的資料結構，也才能寫出比較快的程式碼．

未來的文章，不論是討論資料庫或是面試題目，你們都可以好好地思考一下是否還有其他可用的資料結構．不同的資料結構就代表程式的內容是不同的，可能會更好，也可能一樣，但也可能更差．所以，非電腦科系的工程師們，你們體會多少了呢 ?

閱讀全文

#33 資料庫基礎 - 什麼是 Index

Index 在資料庫的領域裡算是很基本且極為重要的項目，因為它幫助我們可以在龐大的資料裡快速地找到資料．這一篇文章就來說明 Index 運作的原理．

Index 也是一種典型的用空間換取時間的做法．這感覺就像是書籍裡最後面會有一些專有名詞在那一個頁數中可以找到，透過書籍的 Index，你可以很快找到你要找的專有名詞．同樣的，在資料庫裡也是類似像這樣的做法．資料庫引擎可以將你感興趣的資料製做成 Index，如此一來，資料庫引擎只要在 Index 上尋找目標，就可以很快速地得知該筆資料的位置是在資料庫檔案裡的什麼地方．這些就是 Index 概念．舉個例子，在資料庫裡有一個學生資料的表格，表格的 primary key 是學生證號碼，其他的欄位有名字，班級，地址，電話，性別等等．誠如以前的文章曾提過，這個表格有 primary key，所以基本上來說資料庫引擎就會以 primary key 的排序順序做為資料在 page 上儲存的順序．因此，當我們用學生證號碼做為尋找資料的依據時，資料庫引擎就會在 page 上依序地找出我們要的學生證號碼那筆資料．這是在沒有 Index 的情況下．如果你腦筋動的快，你會發現既然學生的資料已經是用學生證號碼排序好了，當我們要用學生證號碼來尋找時，何不用 binary search 呢 ? 沒錯，若你能這樣想，恭喜你已經漸漸習慣了用電腦科學來想事情了．但在這裡，binary search 真正能派上用場嗎 ? 那就要看資料是用何種方式儲存在 page 裡了．如果是用 directory based 的方式，還可行，但若是其他的儲存方式，那基本上不太實用．所以，為了不受儲存方式的干擾，我們可以用更多的空間來儲存成一個方便資料庫引擎搜找的資料結構，同時也享受快速尋找的好處．於是，有什麼資料結構適合呢 ? 答案就是 Tree．

如果我們把學生證號碼做成 Tree，如下的範例圖:

圖中數字為學生證號碼．資料庫引擎會依據學生證號碼的資料做成 Tree，也就是圖片上 Index tree 的部份，然後在 Index Tree 的末端節點上會放入該筆資料位置的 pointer．因此，只要 Index 一建立好之後，資料庫引擎就可以在 Tree 上遊走尋找想要的資料，若找到目標時，也可以馬上切換到該筆資料的位置．這就是為什麼透過 Index 的使用可以讓資料庫引擎快速找到資料的原因．

如果現在的情況改成要用學生的名字來做為搜尋目標，那麼上圖的 Index 就幫不上忙了，因為那個 Index 是以學生證號碼來建立 Tree．所以若我們希望用學生名字來搜尋時也能像之前的效果一樣，則資料庫引擎就必須以學生名字再來建立另外一個 Tree．所以，Index 的建立就必須是有意義的，如果隨便建立一些資料庫引擎用不到的 Index，那只是增加了資料庫引擎對資料維護上的成本而且也浪費更多硬碟空間．

這篇文章先為基本的 Index 概念先開個頭，之後的文章會再來介紹更多有關 Index 的故事．

閱讀全文

#32 資料庫基礎 - 資料讀取的成本評估

在前面的文章裡曾提供當資料庫引擎要儲存資料時可能有三種方式可以選擇，分別是 heap file, sorted file, 和 hashed file.

Heap file

基本上就是沒依照任何的規則來儲存資料，也就是說你先把資料A寫進去，然後再寫資料B，則自然而然地 A 的位置就會在 B 的前面．正常情況下，我們似乎不太希望用這種方式來儲存資料，因為它對資料搜找的速度上並沒有什麼幫助．

所以，假設資料一共分佈在 p 個 pages，然後每個 page 的讀取或寫入的平均時間為 d，那麼在尋找資料時所花費的成本便是 p*d，這是以最壞的情況來看的，因為我們無法知道我們要找的資料是在前面的 page 還是後面的 page，所以在成本評估時就用最壞的情況來看．

如果做 insert 動作，heap file 的特性會讓新的資料一律從最後面加入，所以必須要從第一個 page 走到最後一個 page，然後再做寫入的動作，所以寫入的成本是 p*d+d．

如果換成是一個資料刪除的動作，那就是尋找資料的時間再加上一個資料寫入的時間，所以也是 p*d+d．這也是以最壞的情況來打算的．

如果我們平均來看的話，假設需要找的資料有一半在前面一半的 page，另外一半落在後面一半的 page，而每筆資料都會被尋找，則搜尋的時間成本就可以想像成 p/2 * d，也就是說長時間下來每一筆資料都會被尋找，所以搜尋成本才會除以2．同樣的想法也可以推廣到 delete 的動作．Insert 的動作都是加在最後一個 page，所以平均來看的話，這並沒有差別．

Sorted file

資料會依照某一個規則來排放在 page 之中，這個規則如果能讓每筆資料能顯露出獨立的效果是最好的，比如依照身分證號碼或是員工編號，但這不是必要條件．我們也可以用員工的姓氏來做為排列的規則，這樣至少你可以確定同一個姓氏的員工資料就會被放在同一個或是附近的 page．所以，我們可以明確地知道如果資料是用 sorted file 方式來儲存，這將對於搜尋會很有幫助 ? 為什麼呢 ? 還記得之前文章曾提過的 binary search 嗎 ? 當資料以某一種規則排列好時，binary search 可以讓搜尋更快速，有多快呢 ? 還記得 binary search 的時間複雜度嗎 ? 它是 O(log n)，再重複一次，在電腦科學的世界裡，大部份的情況下 log 是以 2 為基底．

因此，對於 sorted file 而言，尋找資料的成本就是 log (p*d)，這裡的 p 和 d 跟前面的定義是一樣的．

如果是 insert 的動作，因為這是 sorted file，所以需要找到適當的位置然後再做 insert 的動作，所以 insert 的成本就是尋找 + 寫入，因此就是 log (p*d) + d，前提 insert 動作不會造成 page split 的現象發生，也就是說 page 裡面有足夠的空白空間可以寫入新資料．

如果是一個刪除的動作，資料必須要先找到，然後再加上寫入的動作，所以成本也是 log(p*d) +d．以上這些成本評估都是基於資料排序的規則會被應用到，比如，如果是員工資料用員工編號來排序時，那麼資料在被尋找，被新增與刪除時，都必須提供員工編號才能達到上述的成本評估．

Hashed file

Hashed file 的安放方式是讓資料經過 hash function 的計算之後才決定要放到那一個 page．如果 page 有足夠的量而且 hash function 夠好的話，就不會有 overflow page 的發生，也就是說 hash function 計算出一樣答案的資料在同一個 page 能提供足夠的空間了，不需要再連結到其他的 page．由於 hash function 的時間複雜度是 O(1)，所以這是相當有吸引力的儲存方式．

因此，如果是要找資料的話，只是經過 hash function 運算，然後就知道去那一個 page 進行讀取，所以成本是 d，這前提是沒有 overflow page．如果有 overflow page，那成本就還是加上拜訪這些 overflow page 的成本．

如果動作是 insert，一樣經過 hash function 運算後，就知道要去那一個 page 進行資料寫入動作．假設該 page 仍有足夠大的空白空間，則成本也是 d．如果動作是 delete，一樣經過 hash function 運算後就知道要去那一個 page 做資料寫入的動作．假設沒有 overflow page 的情況，則 delete 的成本也是 d．

你可能會覺得用 hashed file 有很好的成本效果．在真實世界的情況下，資料量通常會大，當然硬碟空間也相對地很大，所以 page 的量也會很大．如果你今天要找的資料是很接近的，比如要找員工第一號和第二號，用 hashed file 的方式很可能會造成兩筆資料會被儲存在相距很遠的 page，雖然資料庫引擎很快就計算出來要去那些 page 抓資料，但是硬碟就會忙於東奔西跑去讀取資料，所以也別被 hashed file 的低成本給騙了．

不同的實體儲存方式都有各自的優點和缺點，資料庫引擎會看資料的情況或管理者的安排來決定什麼樣的安排方式會比較好．如果我們不是專門的資料庫管理員，這種實體的儲存方式通常不需要我們來操心．但若你是專門的資料庫管理員而且資料已經成長到相當大的數量時，此時你就必須要知道你的資料是如何被儲存，這樣才能幫助你思考效能改進的事情．再講下去的話就會偏向市面上的商業產品與工具了，所以就到此打住，畢竟此網誌儘量不講產品和工具，只講跟電腦科學有關的想法．

閱讀全文

#31 程式該怎麼分辨好壞呢 ?

上個星期看到一篇短文，文章網址如下
http://buzzorange.com/techorange/2015/10/08/the-six-most-common-species-of-code/

這文章很有趣，它列出不同的人會如何寫出同一個 function．

看到學生寫的就是很標準的學生該有的答案．儘管 recursive 的寫法會有 call stack overflow 的問題，但對一個學生來說，重點是練習 recursive 的思考，所以這樣寫蠻好的．

看到由 Hackathon 寫出來的答案，哈哈，老實說，我真的是打從心裡笑了出來．這個笑可不是嘲笑的笑，而是一種打從心裡佩服的笑，尤其是看到那一句註解 // good enough for the demo

再來看看新創公司寫出來的，其實看不出來這和學生寫的有什麼大差別．也許作者在暗示些什麼?

再來看看大公司．還真的是有大公司寫法的樣子．你是否曾想過大公司的寫法為何是這樣子呢 ? 明明是個很簡單的數學式子而己．我能想到的幾個原因如下:

1.  大公司所生產的產品都具有一定的規模，所以在具有規模的產品下，一定會有許多設計是為了滿足軟體設計的一致性．所以，可想而知，這種具有規模的程式碼一定都是抽象再抽象化，把物件導向常用到的觀念一定都會套用進去，所以你才會看到也許明明是一個簡單的動作卻要搞的好像很複雜的樣子．

2. 大公司也是從小公司漸漸演變上來的，程式經過長時間的演變並且很可能經過許多不同工程師的改進與維護，所以，一般人很難能很快速地看懂程式碼，因為實在有太多故事在裡面了．

3. 在大公司工作的工程師們，平均來說也都是書念的比較好，程式寫的比較好的人．這些人心中或許有一些優越感存在．這些人也許為了顯出自己的優秀，真的會寫出很優秀的架構與運作流程，但由於實在太優秀了，所以對一般人來說就比較不容易懂．

最後，我們再回到 Fibonacci 數列．在電腦與數學的世界裡，這是一個非常有名的數列．在學校學習有關 recursive 或程式設計時的基本練習題目．也許你也可能在面試的時候會遇到這一個題目．一般來說，大家都會直覺地用 recursive 來寫這個題目，因為學校課本是這樣練習的．以時間複雜度的角度來看，recursive 的寫法並不是最好的，更何況它會有 call stack overflow 的問題．我會建議大家改成用 dynamic programming 的寫法，從小的數字算起，一直累積到大的數字，時間複雜度只有 O(n)，而要付出的代價就是較多的記憶體空間．所以，Fibonacci 若把 recursive 改成用 dynamic programming 來寫的話就是典型的用空間換時間的方法．

再回到主題，那程式到底要怎麼寫才好呢 ? 其實，我欣賞 Hackathon 的寫法，重點並不在於寫的好不好，重點是這樣的寫法非常能表達出來作者明白所需要達成的目的是什麼．所以，把問題回歸本質，我們應該要問的是，輸入參數會是什麼，需要輸出什麼，有多少的 CPU 與記憶體可以用．把目的搞懂，再把限制條件搞清楚，這樣寫出來的程式不會離好程式太遠了．我們只要在我們關心的情況下讓我們的程式能正常運作就行了．在限制條件或需求之外，程式會有問題的話，那也不是我們需要關心的．

閱讀全文

#30 Coding面試 - LeetCode #125 Valid Palindrome

題目的網址: https://leetcode.com/problems/valid-palindrome/

這一種題目算是蠻基本的，以前在台灣找工作時曾遇過有個公司的考卷出這一題，而在美國找工作時，目前還沒遇過有人考這一題或是相似的題目．

基本上，這題就是要寫一個 function 來驗證輸入的字串參數是不是 palindrome．所謂的 palindrome 就是字串中第一個位置和最後一個位置的值是一樣，第二個位置和倒數第二個位置的值是一樣，以此類推．所以一個很簡單的想法就是只要一個 for loop 就可以做完這樣的工作，而且不需要線性成長的空間，因此時間上是 O(n)，空間上是O(1)，這是對答案的要求了．

但 LeetCode 出的這一題有一點點小小的變化，因為輸入字串中可能會有其他的符號，而這些符號是不列入規則的，所以題目上寫 "A man, a plan, a canal: Panama" 是一個合格的 palindrome，因為只要不是符號類的字元都一律跳過．因為有這樣的小變化，我們除了用一個變數來記錄前面開始的比較位置，也還多用了一個變數來記錄從後面過來的比較位置．由於這是固定的兩個變數，數量不會隨著輸入參數而改變，所以在記憶體空間使用上是固定的．

另外，我們透過一個基本的 function (IsLetterOrDigit) 來幫助我們辦別輸入字元是字母還是數字，我們假設 IsLetterOrDigit 的時間複雜度是 O(1)．實際上 O(1) 是可以做的到．最後，整個程式如下:

這個程式碼的時間複雜度是 O(n) , 而空間複雜度是 O(1).
這是一個很基本的考題，如果你的面試遇到這種題目，那表示面試官根本不想為難你．

閱讀全文

#29 測試，該如何開始 ?

對一個好品質的軟體而言，測試的確是件很重要的事情．你寫的程式是否能在你假設的情況下做出正確的反應，這也是許多軟體工程師們的挑戰．一般較年輕的軟體工程師們往往過於著重在寫程式的技巧，所以常常忽略了花時間在學習如何測試你的程式．其實，軟體測試的學問完全不亞於一般的軟體開發所需的知識，而很多人可能會有一個先入為主的想法，那就是程式如何都寫不出來了，那學如何測試有什麼用呢 ? 聽起來好像還有幾分道理，至少在十多年前我是這樣想的．後來接觸多了之後也漸漸發現，如何不知道如何測試的話，那你怎麼能知道你寫出來的程式一定能用呢 ?

一般來說 (至少在我的工作環境下是如此)，軟體工程師自己寫出來的 function 一定要自己寫好 unit test．這是蠻重要的事情，因為除了你，應該沒有人比你更了解你寫的 function 是什麼，但也因為如此，也容易造成自己在測試時會陷入一些假設的情境下而忘了一些測試條件．

我們來看一個很簡單的例子，

int Add(int x, int y) {
    return x+y;
}

以上是一個很簡單的加法，每個人都會寫．如果我們要為這個加法 function 寫一些 unit test，你會寫那些東西呢 ?

首先，我們先來找一些可行的例子，先來試試 test for pass，例如輸入 x=0, y=0 或輸入 x= 10, y = 10 之類的，如果你能得到正確的答案，那看來這個 function 是可以用的．

接下來，我們就要再多想一想，我需要把所有可能的數字組合都測試過一遍以確保這個 function 是正常的嗎 ? 如果你有時間的話，當然應該是要這麼做，因為一旦這個 function 送到客戶那執行時，你已經把所有可能的輸入組合都測試過了，所以你當然知道會不會有問題．但我們真的需要這麼做嗎 ? 其實也不用．關於這點，你可以在一般的軟體測試文章或書藉裡看到一個所謂邊界值條件的測試．據經驗來看，讓程式發生問題時有較高的機率會發生在邊界值的情況，例如 x = int.MaxValue 或 y=int.MaxValue，當你一輸入進去時，你就會發生這個 function 其實是有問題的，因為 integer overflow 了．

接下來，既然 x 和 y 是 int，那表示負數也是接收的，所以你還可以測試負數的邊界值，x = int.MinValue , y = int.MinValue，同樣的也會發生 overflow 的錯誤．所以，你就可以看到只要你把 x, y 的數值在可接受的範圍上跑了一遍，你就會發現這個加法 function 到底有沒有問題了．

接下來，你可能會說現在市面上寫的專案程式不是那麼單純呀．沒錯，我同意你的看法，的確都不單純，但寫 unit test 的精神還是一樣的．再看一個簡單的例子，

Result[] GetData( Connection conn, Command cmd) {
  .....
}

以上的 function 是一個根據命令 (Command) 在連線 (Connection) 上做一個取得資料的動作，取得到的資料將會以 Result[] array 的形式傳出來．

按照上述的第一步，你應該要先測試  test for pass 的情況，傳入正確的 connection 以及正確的 command，然後檢查是不是會得到結果．

接下來，我們可以調整 conn 和 cmd 的物件屬性，來測試 GetData 會如何反應．例如，故意把 cmd 輸入誤會的命令，或是故意把 conn 的狀態設定為關閉．甚至你還可以傳入空物件，看看 GetData 的行為是不是符合預期．

所以，你應該可以感覺到撰寫這些 unit test 的時間與力氣並不會比較少．尤其是一旦軟體能做的事情越多時，這些輸入參數的可能變化將是成指數形式往上成長，我們根本很難把所有可能的情況都試過一遍．如果你真的都試過了，那麼客戶會遇到的問題一定都會在你的掌握之中，甚至你可以在交貨之前就先修正這些問題了．但畢竟這只是理想，對一個具有某程規模以上的軟體而言，這幾乎是不太可能的事情，一來是時間，二來是預算等等的考量．所以，我們要做的也是在時間與預算範圍內能包含大部份的情況，比如 90% 的客戶都不會有問題等．

其實在設計程式時也有些技巧可以幫助你做測試，這些將都是未來文章的內容．

閱讀全文

#28 資料庫基礎 - 存取 Page (Hashed File)

前面兩篇文章提到了存取 page 的兩種方式，在這一篇文章裡要介紹的是另一種方式，我們稱它為 hashed file．聽到這個名字，你可能已經猜到這是和 hash function 有關係的儲存方式．沒錯，它就是利用 hash function 來決定儲存位置，也是就說透過 hash function 的計算來決定要儲存到那一個 page 上．

前面的文章曾提到過基本的 hash function，也介紹了它最簡單的運算方式．所以，假設一開始有十個 page，然後有五筆資料，我們可以將每筆資料傳給 hash function，計算出來的結果是 0 - 9 的數字，而這數字就用來代表要儲存到那一個 page 上．一旦資料變多時，資料的筆數一定會遠遠大於 page 的數量，所以同一個 page 上一定會有許多筆資料．因此，透過 hash function 的方式來計算儲存位置也是個蠻快速的方法．不過，資料庫引擎通常不會被設計成將整筆資料拿來 hash，因為我們在找資料時很少會用全部的欄位做為搜尋的條件，因此，我們通常會選擇幾個重要的欄位或是只選擇 primary key 的欄位來做為 hash function 的輸入值，而 hash function 輸出值就是 page 的號碼．因此，資料庫引擎在為我們找資料的時候，只要欄位條件符合的話，就可以透過 hash function 的計算而快速地得到 page 號碼．

接下來，你可能會問到，一旦資料量越來越大時，一定會有很多的資料經過 hash function 計算後會得到同樣的答案，而這些資料量會遠遠超過一個 page 得記錄的資料量．這種情況在我們談論 hash function 的時候也會發生，當時所採用的方法就是在 bucket 上做一個 list 來承接更多的資料．相同地，在這裡也是可以用相同的觀念．如下圖:

如上圖的上面那個 page，當它沒有足夠的空間承載更多資料時，此時資料庫引擎就必需要一個空白的 page ，然後在前面的 page 做一個連結到空白的 page，接著就可以把屬於同一個 bucket 的資料寫進去．因此，你可以看見的是，如果 hash function 的 bucket 準備不多的話，那麼資料就會長成像幾條很長的 page life，我們並不希望碰到這樣的情況．所以若要採用 hashed file 的儲存方式，則該 hash function 需要有能力產生足夠多的 bucket，甚至最好是能彈性處理，依照資料的多少來決定，但相對地要做多的配套措施．但若以好的角度來看，用 hashed file 的結構來儲存資料，對資料庫引擎而言可以大大提供資料搜尋的速度．

有關資料如何儲存在 page 上，從儲存的方式來看基本上有三種方式，而每一種方式都有其優點和缺點，所以針對不同的資料，根據他們的特性來決定用那一種儲存方式將是比較好的決定．要怎麼評估呢 ? 我會把評估的成本估算寫在未來的文章裡，讓大家知道資料庫引擎是根據什麼樣的數據來決定要用什麼方式儲存資料．

閱讀全文

#27 Coding 面試 Leetcode #98 Validate Binary Search Tree

我記得這一題我被問過兩次，是兩個不同的團隊，而且都是跟資料庫有關的工作．所以，若你也要尋找資料庫相關的開發工作，看來 Tree 的題目是很難避免的．

這題的題目很單純，就是要寫一個 function 用來驗證題目的 Tree 是不是 Binary Search Tree (BST).
根據 BST 的定義，左邊的節點值必需小於父節點值，而右邊的節點值必需大於父節點值.
但這題有一點要小心的是，別只是檢查父節點值而己，應該要檢查所有上層的父節點值都要小於或是大於．

如果題目只給你 tree root，那麼你可以寫出像下面的 function 來檢查這個 tree 是不是 BST.

        public bool IsValidBST(TreeNode root)
        {
            return BST(root, null, null);
        }

        bool BST(TreeNode node, int? min, int? max)
        {
            if (node == null) return true;
            if (min == null && max == null)
            {
                    return BST(node.left, min, node.val ) && BST(node.right, node.val , max);
            }
            else if (min != null && max == null)
            {
                if (node.val > min )
                    return BST(node.left, min, node.val) && BST(node.right, node.val, max);
            }
            else if (min == null && max !=null)
            {
                if ( node.val < max)
                    return BST(node.left, min, node.val) && BST(node.right, node.val, max);
            }
            else
            {
                if (node.val > min && node.val < max)
                    return BST(node.left, min, node.val) && BST(node.right, node.val, max);
            }
            return false;
        }

若你仔細看的話，我是把每個分支出去時可能的節點值範圍也傳遞過去．這樣的寫法也許不是最好，但就如之前文章所說，要在五分鐘內想好然後在半小時內寫完再測試，所以就勉強用了.

這時候如果遇到要求更高的面試人員，他可能會說 recursive 的方法不適合用在 tree，所以要改成 iterative 的方式來寫．
其實要改成 iterative 的方式，說難不難，說簡單也不簡單，因為要在那短時間想出來也是件不容易的事．比較幸運的是之前我有練習過 BST 用 In-order traversal 的走法來驗證 BST，所以這題也就順利寫完了，以下就是改成 iterative 的方式，用 In-order 走訪 BST 之後，得到的答案一定是從小排到大的數值，所以只要多一個 for loop 來檢查數值是不是從小排到大即可.

  public bool IsValidBST(TreeNode root)
        {
            if (root == null) return true;
            List<int> re = InOrder(root);
             if (re.Count == 1) return true;
            for (int i = 0; i < re.Count - 1; i++)
            {
                if (re[i] >= re[i + 1])
                    return false;
            }
            return true;
        }

        List<int> InOrder(TreeNode node)
        {
            List<int> result = new List<int>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (stack.Count != 0 || node != null)
            {
                if (node != null)
                {
                    stack.Push(node);
                    node = node.left;
                }
                else
                {
                    TreeNode t = stack.Pop();
                    result.Add(t.val);
                    node = t.right;
                }
            }
            return result;
        }

雖然在初步面談中都把上述的題目做完了，但這也不代表就有機會可以繼續做後續的面試．所以，很可惜沒能做成資料庫開發的工作，找工作真的一切都是個緣份.

閱讀全文

#26 資料庫基礎 - 存取 Page (Sorted File)

上一篇文章談的內容是針對資料之間是沒有順序的情況，因此在尋找資料時就是採用依照資料的排列順序來尋找．因此整個尋找過程的時間複雜度是 O(n) ．通常來說，資料庫設計者不會讓這樣的事情發生，除非資料本身是一個相當小的參考資料而己，否則資料一旦多了，  O(n) 實在不是一個好現象．

在真實世界中的應用，我們常常可以為資料找到至少一種排列方法，例如，在學校的資料庫中，基本上可以用學生證的號碼來排序學生的資料，因為在同一個學校裡不會有相同的學生證號碼．我們在前面的文章中也提過，一旦資料排序過了之後，時間複雜度就會從 O(n) 下降成 O(log n)，基本上就是 Binary search．因此，如果資料可排序的話，則資料庫引擎就可以依序地將資料寫在檔案中．

資料庫引擎為這些可排序的資料寫入到檔案中有兩個方式．第一種方式是直接將資料依序排列好寫在檔案中，所以每個資料的前後順序就跟排列的順序是一模一樣的，如果中間要插入一筆新資料時，就很有可能會發生 page split 的動作．如圖是一個例子．紅色的框框代表 page，而藍底的框框帶表一筆資料，而藍框裡的數字代表資料的序號，序號不一定要連續，只要不重複即可．所以一開始把資料寫入時，它的排列長相如下:

這時候如果要新增一筆序號 7 的資料，那麼它要排在 5 和 10 之間，但是該 page 已經沒有位置了，因此發生 page split．

資料 7 會放在前面的 page 還是後面的 page，這將由資料庫引擎內定的邏輯來決定．

第二種將資料寫入檔案的方式是讓資料的實體位置不需要改變，另外在建立 "目錄"，然後在這目錄上做 binary search 的動作．

在這種方式下，新增一筆序號 7 的資料時，它就可以直接在 page n+1 的地方寫入，然後資料庫引擎只要更新目錄的內容即可．

當新增一筆序號 7 的資料在目錄 page 時，此時會發現  page split 還是在有足夠的空間下把後面的資料往後移，這將由資料庫引擎的內定邏輯而定．因此，第二種方式就變成直接在目錄 page 上做  binary search ，然後再依照其內容 (pointer) 就可以找到該筆資料．

所以，你的 table schema 的設定理應當是都有 primary key 的存在，如此一來才能做為資料庫引擎排序的依據．其實，以上的內容基本上也就是 clustered index 和 non-clustered index 的精神．

閱讀全文

#25 資料庫基礎 - 存取 Page (Heap File)

        在前面的幾篇文章中提到了資料庫引擎讀取與寫入資料時在面對固定長度與非固定長度時所可以採用的儲存方式，其中提供了 Page 為一個儲存空間的管理單位，透過 Page 的機制，讓資料庫引擎能以 Page 為單位做資料讀取與寫入的動作．搭配上 Page 裡的 manifest 資料，資料庫引擎就可以很清楚地知道這個 Page 裡面有多少筆資料以及有多少剩餘空間可用．這時候我們把層次往上拉高一點來看，那 Page 跟 Page 之間的關係是如何定義呢 ? 舉例來說，當某一個表格裡的資料繼續變多時，這些資料很可能會需要很多的 Page 來能承載，那資料庫引擎又怎麼知道是那幾個 Page 是用來承載這表格的資料呢 ? 因此，我們也必須定義 Page 和 Page 之間的關係．

        要定義 Page 之間的關係最簡單的方法就是採用 Linked List 的概念，也就是說每一個 Page 都會記錄著上下一個 Page 的位置，這就像是 Double Linked List 一樣，所以資料庫引擎便很容易地在 Page 之間游走來尋找資料．參考下圖來看一個很簡單的例子:

上圖一共有七個 Page，其中 page 1, 3, 4, 6 前後之間有 pointer 指著上下一個 Page 的位置，這也代表這四個 Page 儲存著高度相關的資料，比如說是同一個表格的資料，或是同一份 index 的資料等．但什麼樣的資料會讓 Page 用這種方式儲存呢 ? 看來是隨意安排的資料，不需要排序，也不需要特殊的安排，資料先進來就先寫入．因此，當資料庫引擎在存取這類型的資料時所花費的成本就會很高，因為都必須從頭開始往後找．不論是找什麼樣的資料，尋找一律都是從最前面的 Page 開始找到最後的 Page．其實這也就是 Linked List 的特性之一．也就是說你要找的資料剛好落在最後一個 Page 的時候，資料庫引擎就必須要從最前面的 Page 一直找到最後一個 Page．因此，這樣所花費的成本是相當高的．

所以，這也告訴了你一件事情，如果你的資料用上述的方式來儲存，這將造成資料庫引擎花費許多時間成本來尋找與寫入資料，而這種像 Double Linked List 的 Page 關係方式，一般的課本稱它為 heap file. 後面的文章會再繼續介紹其他方法．

閱讀全文

#24 我的 IT 人生 - 簡短篇

這一篇內容我不談資料結構，也不談資料庫，更不談寫程式，我來簡單地談一談自己的 IT 人生．

在我還是高中生時，當時有接觸一些電腦課，學會了操作 MS-DOS 系統，也會寫一些簡單的 BASIC 程式，對電腦的確是有相當興趣，但還沒想過要把它當成一生的工作方向．後來，念了大學之後，我念的是機械工程，原本我的打算是想要念電機工程，因為自認為在物理課本中，電學念的比力學好很多，不過也奇怪，我當時還是把機械工程填入到志願卡裡，若我印象沒錯的話，我記得我的志願卡裡還有土木工程電子工程等等相關的工程科系．大學四年就這樣念到畢業了，說實在，到現在我還是覺得大學那 4 年似乎是浪費的，因為我現在沒需要用到任何機械工程的知識．不過，人生就是這樣，現在回過頭來看，就當做是用人生的時間換來了一些人生經驗．

接著，學校畢業後就直接去當兵了．我想這是我整個 IT 人生的起點．我很幸運地被分配到資訊單位，我還記得一進去時學長丟給我一本書，網路概論．我就從網路開始學習，從區域網路到廣域網域，也包含通訊協定如 TCP/IP 等等的都學了，後來還得學習寫網頁程式，一開始用 CGI 後來用 ASP 寫．在那近兩年的時間裡就像是一個職業訓練所一樣，我把基本的網路和網頁程式學了起來，退伍後就直接在資訊業找了工作．當時是差不多 2000 年的時候，Internet 和電子商務正在蓬勃發展，所以許多公司也不會在乎學歷或科系，只要真的能拿出工具寫出一些真實的東西，很多公司都是歡迎的．我的印象中，當時我快退伍找工作時，每個星期總是可以收到公司邀請面試的信件．

在工作了幾年後，我腦中漸漸地有越來越多的問號，比如要怎麼才能寫出好的程式，要如何才能是好的設計，甚至細節到為什麼資料庫的搜尋可以這麼快，在工作上有太多太多的問題實在讓我很好奇．因為我覺得我如果要在工作上更進一步的話，我最好還是去了解這些問題的原因，因此我決定回學校去念書，但我選擇不是回去念資訊科系的大學部，我選擇是去考資工研究所．我還記得當時大部份的學校都會考資料結構，演算法，作業系統，計算機組織以及離散數學．我當時買了一堆書，一堆補習班的講義就開始念了．在念書的過程中也得到不少的收獲，比如作業系統裡提到了 CPU Scheduling 才知道電腦要做多工環境的概念，念了資料結構也才知道原來程式的效能是透過 Big O 來評估的．在那過程獲得不少心得，但可惜準備的時間太少還無法完全熟悉以及融會貫通，最後我用三個月的念書時間考到一家國立大學後段班的資工所．

在念研究所時，我已經 30 歲了，對自己來說算是項蠻挑戰的投資，在那段時間我到大學部去上課，作業系統，離散，資料結構，演算法等等，把這些基礎課目透過學校課程補起來，然後也念了物件導向，分散式系統與資料庫等課程，自己也蠻開心可以走到這一步．在畢業前，我收到了一間美國大學的入學許可，我申請到了電腦科學博士班，畢業一年後，我就前往美國念書．到了美國後，學校規定演算法和計算理論是必修，成績不達標準不能畢業，光是這兩個科目就讓我很辛苦，重修一次後才過關，也是因為這樣的辛苦，所以對電腦科學才有更進一步的認識．雖然最後沒能把博士學位完成，但還是覺得自己能走到這一步也是不賴了．在我大學剛畢業時，我可從沒想過自己能走到這樣的地步．

寫這篇文章時，我 40 歲了，在美國一家軟體公司上班，每天就寫著一些程式來改進公司的工具與產品．從現在回過看，在我 28 歲之前，連 Big O 是什麼都不知道，也不知道什麼是 Binary search，這十年來的變化就好像變魔術一樣讓自己的 IT 人生起了很多的改變．把自己的 IT 人生寫的很簡短，現在我有新的人生方向，但短期內還不會離開資訊業，就如同前面說的，這一切都是自己的選擇而造就自己的人生經驗，也希望這些經驗能提供其他年輕人做為參考．如果你認為我有值得讓你參考之處，歡迎你留言給我. ^_^

閱讀全文