#51 Coding 面試 - LeetCode #9 Palindrome Number

原文網址 https://leetcode.com/problems/palindrome-number/

這一題跟之前講的有一題 palindrome string 有點異巧同工之妙，但不同的是這題指的是數字，而不是字串．如果你把數字當成字母來看待的話，則也能用之前相同的解法．這在演算法來說算是一種 reduction 的技巧．然後，數字和字串的特性畢竟不同，所以若把數字轉成字串來處理是可以的，但就浪費了一些數字的特質．

其實要把數字反轉，最簡單的方法就是用十來取餘數，也就是說 2 取十的餘數是 2 , 12 取十的餘數是 2 , 102 數十的餘數是 2．因此，對十取餘數之後，我們就能得到個位數的值，然後再對商再取一次餘數，用這個方法一直做到商變成 0，這樣子就可以把原來的數字一個一個取了出來．

剩下的就是將取出來的數字排好，第一個取出來的放最前面，最後取出來的放最後面，這裡不需要 "儲存" 的觀念來做，其實只要在每取出一次餘數時，把之前取出來的數字乘十就行了，這樣就等於先取出來的會被 "進位"，然後再加上最新取出來的餘數．

最後，還要記得處理正負號．這只需要在一開始的時候判斷是正號或負號，若是負號的話，就一律不符合答案，若是正號的話，就檢查反轉前和反轉後的數字是不是一樣的，這樣就完成了．

參考的程式碼如下:

閱讀全文

#50 Coding 面試 - LeetCode #349 Intersection of Two Arrays

原文網址 https://leetcode.com/problems/intersection-of-two-arrays

這一題在原文網址上列為簡易型的題目，看了題目之後，只要你熟悉一些基本的資料結構，應該可以很快想出不錯的解法．題目輸入是兩個 integer array，然後輸出一個 array，這個 array 包含的元素要出現在兩個輸入的 array 裡．

若用最直覺的想法，你可以做一個 for loop 在第一個輸入 array 上，把每一個元素和第二個輸入 array 的元素相比較．以這樣的做法來看，時間複雜度將會是 O(n²)．以這個題目來說，這樣的時間複雜度並不理想．所以得再想想一個比較好的處理方式．

我在寫這題時一開始就想到利用 hash table 來運作，因為 hash table 有極佳的 O(1) 的動作速度．所以一開始把第一個輸入 array 所有的元素透過一個 for loop 加入到 hash table．然後再將第二個輸入 array 利用另一個 for loop 來查看是否有同樣的數字已經存在於 hash table 之中．如果有的話，它就是我們要尋找的對象，但把它加入到輸出的結果裡，這裡是用一個 List 來代表．最後再將整個 List 轉換成 array 輸出，這樣的轉換只需要 O(n). 因此，整個時間複雜度將是 O(n+n+n)．有二個 for loop 和最後的轉換，所以一共是三個 n.程式碼如下:

最後我還發現了 LeetCode 提供了與其他同樣語言解法的比較．上述的解法打敗使用同樣語言 75% 的解法．我想這是以他們電腦執行速度來計算的．由此可見，上述的程式碼在最佳化上還有很大的空間可以改進．

閱讀全文

#49 - 物件導向的最基礎 - Access Modifier

若我們用 Java 語言來做為說明，則 access modifier 有三種，分別是 public, protected, private. 他們分別控制了那些對象能使用他們所定義的東西.

在 https://docs.oracle.com/javase/tutorial/java/javaOO/accesscontrol.html 裡面有一個表格呈現出了整個控制力的對照圖．例如，private method 只能被同一個 class 裡面的 method 所使用，只要超過同一個 class 的範圍是無法使用的．public method 剛好相反，它可以被任何的 class 看到來使用，甚至也可以被其他元件看到來使用．因此，當你將 class, property, method 設定為 public 時，你就要非常地小心．這個稍後說明．最後一個是 protected，它能被同一個 class 裡的東西來使用，而也能被該 class 的 child class 來使用．

Private 的控制力道最嚴格，因為除了在同一個 class 的 method, property 以外，其他人都無法存取．因此，在最初的設計上時比較不會對 private method, class, property 等做太多的說明，甚至會跳過他們．Public 就完全相反了．誠如前面所說，一旦你將 class 設定為 public 時，那表示不止你的程式可以看到來使用，其他人的程式也可以看到來使用，這時候你就要非常小心，因為你得考慮到這個 class 一旦被使用了之後，它所執行的程式碼需要具有什麼意義．同時，也要注意在寫程式時是不是有做一些檢查．

來看一個很笨的例子，假設你今天要設計一個傳送訊息通知的 class，而訊息傳送的功能是透過其他的元件來執行，你需要設計的只是一個簡單的 wrapper ，將該元件包起來，然後只要露出一些你需要提供的功能即可．所以程式碼可能是這樣

public class MessageSender 
{
 private Some.Other.Sender _component;
 
 public void Start()
 {
  _component = new Some.Other.Sender();
  _component.OpenConnection();
 }
 
 public void Send(string message)
 {
  _component.Send(message);
 }
 
 public void End()
 {
  _component.CloseConnection();
 }
}

從上面的程式碼你可以看到 MessageSender class 的 access modifier 是 public，這表示全世界都可以看到它，因此任何人都可以使用它．在這個 class 裡面定義了三個 methods，分別是 Start(), Send(), End()．會這樣設計可能因為你想要讓使用它的人比較清楚知道該如何使用，因為顧名思義看起來就會覺得一開始的時候就要使用 Start()，需要傳送資料時就用 Send()，而最後在結束時就使用 End()．這樣的想法也沒什麼不對，只是漏掉了一點，那就是 public method 是大家都看的到．別人可以看的到不代表他就一定得用它．也就是說，當我 new MessageSender 時，有規定我一定要先呼叫 Start() 嗎 ? 似乎沒有．有規定我最後結束時一定要呼叫 End() 嗎 ? 似乎也沒有．如果我直接呼叫 Send 來傳送字串時，那會發生什麼事呢 ? 答案很明顯，會發生 null object 的現象．

用以上這個笨笨的例子來提醒大家，在設計 public class, public property, public method 時一定要注意到這些 public 的東西被使用時是沒有順序可言的，所以千萬不能自作主張去以為所有人會知道該如何使用，甚至你寫了說明文件該如何使用也不能這樣寫程式．因此，設計 public 時一定要非常地小心，要想到當 public class, public property, public method 是第一個被存取的對象時會發生什麼事．這樣你就會知道上面的程式碼是行不通的，而且相信你也能將上述的程式碼改成一個比較好的程式碼．

閱讀全文

#48 老鼠走迷宮 (mouse maze)

在大學的資料結構的課程裡，大約在教過 Stack, Queue 和 List 這些基本的資料結構之後會有一個老鼠走迷宮的作業．這份作業說難不難，說簡單也沒那麼簡單，對一個正在學習資料結構的學生來說，花個一兩個晚上來寫這份作業是很正常的．如果寫程式正是你的工作，而且你以前沒念過資料結構的話，不妨試著做做看這份作業．

老鼠走迷宮的內容是，要隨機產生一個矩陣，矩陣的大小最好由使用者輸入設定的．然後在矩陣裡的每個位置也會隨機產生三種不同的地形，例如平地，河流與高山．你可以再設計其他不同的地形，老鼠在每一個地形上走動時會花費不同的體力，例如平地是 1 ，河流是 2，而老鼠是無法穿越高山．老鼠的出發點是矩陣的左上角，也就是 (0,0) 的位置, 然後終點在右下角，也就是 (n,m) 的位置，n,m 代表的是矩陣的兩個邊長．

你所要寫的程式是讓使用者輸入矩陣的大小，然後為矩陣的每一個格子隨機產生地形，接著老鼠從出發點開始移動，看看老鼠是否可以走到終點．因為地形中會有高山，所以老鼠不一定都會有一條路可以走到終點．然而，老鼠能走的路也可能不只一條能到終點，你可以試著找出一條就行了．

整個題目的重點在於兩個地方．第一，移動的方向要定出一套規則，第二，要能夠記錄走過的路跡．移動方向的規則可以用最簡單的方式來實行，除了在邊邊與角落以外的格子，每個格子都可以有八種移動方向，上，下，左，右，左上，左下，右上，右下．每到達一個格子時，就可以依照固定的順序來移動到下一個格子，如果在下一個格子都沒有路走或是每個方向都試過了，那就回到上一個格子．因此，路跡的記錄是很重要的，因為需要回到上一個格子．

以下我提供十多年前寫的版本

如果你順利寫完之後，還有一個延伸題目給你繼續挑戰，那就是如果有多條可以走的路跡時，列出最省力的路跡．這延伸題目就不是那麼簡單了，未來再來寫篇文章來討論．

閱讀全文

#47 資料庫基礎 - 以 Hash 為基礎的 Index

前面的文章介紹了資料庫的 Index 是以 tree 為基礎的方式，一般來說大部份資料庫產品都用 B-tree 來建立 Index．然而，除了用 tree 以外，還可以用 Hash 的方式來建立．

可以用上圖來說明 hash index 的運作方式．首先，輸入值會先經過 hash function 的運算後而得到一個 hashed value，這個運作如以前的文章講的是一個 constant time 的運算．輸入值就是使用者要過濾的條件，也就是 SQL statement 中 where 的內容的欄位值．例如，學生證號碼，病歷編號等等．然而，這種輸入值若不是 key 的話，便會發生多筆同樣資料會得到一樣的 hashed value，例如我們是用學生的姓來做 hash index 的話，則同樣的姓就會得到一樣的 hashed value．因此，一個 hashed value 可能會對應到一個或多個在 Data page 上的資料．，以上圖來看，每個 hashed index 的資料可以對應到一筆或多筆在 data page 上的資料，這樣的做法其實並不太好，因為每個 hashed index 的資料大小是無法確定的，就因為我們無法預測每個 hashed index 會對應到多少筆 data page 的資料．因此，可以再改一下如下圖，

我們規定每個 hashed index 的資料只能對應到一筆 data page 上的資料，這樣就可以固定住每個 hashed index 的資料大小．因此，當輸入值經由 hash function 運算之後到達第一個 hashed index 上的位置，便可以得到一筆 data page 的位置而取得資料，然後還要往下一個 hashed index 移動，如果 hashed value 也是一樣的話，就要再取得它所對應在 data page 上的資料，一直到 hashed index 上的值不同了或是沒有下一個了．

以 hashed index 的運作方式來看，其效率比以 tree 為基礎的 index 還要來的好，那為什麼一般的資料庫產品不採用它呢 ? 我想主要的原因就在於 hashed index 無法支援有範圍的尋找．例如，如果用學生證編號做 index，當你下 SQL statement where ID > 10 and ID < 100 時，這在 tree-based index 上可以有很好的尋找效果，只要找到 10 之後就再延著 tree node 一直往下或往旁邊找到 100 就可以停住了．但 hashed index 來說並不是這樣，因為在 hashed index 裡, 10 旁邊的很可能就是 100，要看 hash function 如何設計．所以在 hashed index 上我們找不到一直可以連續讀取資料的方式．如果我們把編號從 10 開始代入一直到 100，這聽起來好像可行，但如果 index 的資料不是數字而是文字，難道要把筆畫漸大的字都帶進去運算嗎 ? 顯然不可能．

雖然 hashed index 不適合用在有範圍的尋找，所以就不適合被一些商業資料庫產品所採用，但還是透過這篇文章介紹 hashed index 讓讀者們可以了解 index 的做法不見得只有 tree 的方式，不同的方式有好有壞，有長處也有短處．

閱讀全文

#46 Coding 面試 - LeetCode #62 Unique Paths

原文網址 https://leetcode.com/problems/unique-paths/

這一題主要是考 dynamic programming 的思考，但老實說，這題過於直覺，所以寫完答案時還沒馬上觀察到這是 dynamic programming 的解法


參考的解法如下:

從 First row 上的可行走法都是1, 因為只有可能從左邊走過來的方式．從 second row 開始，就有可能是從上面或從左邊來的走法，因此才是相加的，也就是上述解法中 r[i,j] = r[i-1,j] + r[i,j-1];

我相信如果你的主考官想要考你 dynamic programming 的話，應該不會用這一題來考你．若是要考簡單的，應該會是用 Fibonacci number 來考你，因為最直覺的 Fibonacci number 的寫法並不是用 dynamic programming 的寫法，而是用 recursive 的寫法．以時間複雜度來看，dynamic programming 的寫法是比較快的，而以空間複雜度來看，recursive 寫法是比較優的.

閱讀全文

#45 資料庫基礎 - Page 的 Fill Factor

前面的文章介紹了許多資料庫引擎中有關 Storage management 的部份，讓你能了解資料庫引擎在處理儲存與讀取資料時所使用的原理基礎．但這些也都只是基礎的運作原理，真正實作的方式也會因為產品的不同也有些差異，但至少你知道了原理，這就能幫助你了解資料庫引擎的工作，也希望對你的學習與工作能有所幫助．

這篇文章將說明的是一個 Storage management 中管理資料的選項，對我而言，這是一個設計技巧．還記得前面的文章中曾提過 Page - 這是資料庫引擎用來儲存資料時所用的一個管理單位．一個 page 可能會有 4K 或 8K 或其他大小的容量設計，所以每個 page 的容量幾乎都是固定的．對一般正常運作的資料庫系統來說，對資料一定會進行新增刪除與修改的功能，所以這樣子的工作就常常會導致 page split 的現象，這個現象在前面的文章曾提過．page split 就相當於是在一個 list 中插入一個新的元素一樣，其運作成本比較高，如果再加上硬碟資料散亂度過大的話．所以，為了減少 page split 的現象，因此存在了 fill factor 的設計．

Fill factor 的意思就是當一個新的 page 產生要寫入資料時，資料庫引擎不會將所有資料空間都拿來寫入資料，而是會留下某一個百分比的空閒空間．這個百分比的大小基本上是可人為控制的．比如，當我們告訴資料庫引擎 fill factor 為 80% 時，則資料庫引擎在 page split 發生或是需要建立新的 page 時，當它寫入資料時只會佔用掉  80% 的可用空間．而剩下的 20% 就留做未來在做資料新增修改時可以利用的空閒空間．舉個例子說明，你有一份學生資料放在資料庫中，而學生資料假設定依照學生姓名排序 (primary key)．假設一開始並沒有設定 fill factor，而它的預設值是 100%，所以這表示所有的學生資料都依序寫入到 page 之中．資料越多，所需要的 page 也會越多．而在這些 page 之間都沒有留下任何的空閒空間．而今天來了一個新學生，他的名字剛好是排在所有學生的中間，當它的資料寫入到資料庫時，資料庫引擎發現它需要在這些 page 中間做一個 page split．Page split 做完後，一個 page 變成 2 個 page，所以這兩個 page 都多有了 50% 的空閒空間，因此新學生的資料就可以寫進去這中間的 page 了．所以，如果一開始設定了 fill factor = 50%，那表示在一開始學生資料寫入到 page 時只會佔用一半的空間，因此每個 page 都有一半的空閒空間．當新的學生資料需要新增時，資料庫引擎找到目的 page  後發現還有一半空閒空間並且足夠用來寫入新資料，則就直接將新資料寫入而不需要做 page split 的動作，因此也讓資料新增的動作可以更快地完成．所以，你可以把 fill factor 想成是一種利用空間來換取時間的方法．這對於經常需要做新增動作的資料庫來說相當有幫助．對於資料變動很小的資料庫來說並沒有什麼太大的好處．

因此，如果你採用的資料庫引擎有提供 page split 的觀察指標，你可以查看你有那些 table 經常發生 page split 的現象，如果有的話，你可以將 table 的 fill factor 改小一點來降低 page split 的發生．

其實 fill factor 也只是一個應用，像這樣預先預留空間做為未來使用的情況，在很多產品的設計都會用到這樣子的 idea，基本上都是用空間來換點時間的做法．希望這樣的 idea 有一天也能幫助你的設計．

閱讀全文

#44 Coding 面試 - 列出公司組織人數

這一題是我以前面試時遇到的題目，不知道當初面試的老闆是在那找來的題目，總之我沒有看過類似題．先來說明題目，

你要寫一個程式，程式的 input 是一個字串，這字串包含了公司裡員工的名字，同時字串裡也包含了老闆與直屬員工的關係．以下是一個例子

A-B,C-B,B-D   這字串代表 A 的老闆是 B，C的老闆是 B, B 的老闆是 D，以此類推，中間會用逗號隔開每一組資料，然後一橫代表老闆和員工，左邊是員工，右邊是老闆．所以，這一個字串其實上就代表了整個公司的組織圖．你可以用手動的方式把每個資訊解析一下就可以把這組織圖的 tree 給畫了出來．

題目要求你要列出某一層次的老闆們下面一共有多少員工 ? 以上述的例子來說，D 是在 level 1, B 是在 level 2, A 和 C 是在 level 3，如果要求你列出 level 2 的老闆時，你的程式就要顯示 B 有兩個員工．

看到這裡，不知道你心裡有沒有想法要怎麼解決這一題．當初這個面試更特別的是，這位面試的老闆帶他自己的筆電過來，Visual Studio 已經開好了，題目的 function 和輸入字串也都打好了，直接要我寫 function 裡面需要的 code．就是上機考．這是我第一次面試遇到上機考，以前遇過的面試都是寫白板而己．寫白板的好處就是有一點小錯誤的話也沒關係，因為面試者主要是看你寫的邏輯對不對，所以不會在乎你是不是打錯 method name 或少了結尾分號之類的．但上機考就完全不一樣了，你一定要讓 compiler 很開心，不然既便有一個再小的錯誤，compile 會失敗的．

基本上，只有 30 分鐘可以這一題，我一開始想了一下，難道真的要建 tree 嗎 ?  寫了建立 tree 的功能之後，還要加上 tree traversal 的功能，這樣才能在 tree 上遊走找人數．當時我還很認真地思考要如何做 tree 和相關功能．後來想想不太對，因為這樣太麻煩了，我只剩 25 分鐘而己．後來就想了一招，雖然不是很好，但是用來解這個題目一定夠用．那就是改用 recursive 的觀念來做．做法如下

1. Parse 輸入字串來建立一個 hash table，key 是員工名，value 是老闆名
2. 用 recursive 的方式在這個 hash table 上找出某一個 level 的員工名稱
3. 根據步驟 2 的結果，把 hash table 上所有員工也是用 recursive 的方式來找看誰的上面老闆是在步驟 2 的結果內，同時把該老闆的下屬員工數做人數統計

因為老闆給的公司組織是真實的資料，所以我知道當我用 recursive 的方式來運作時並不會發生 call stack overflow 的現象．這個觀念在前面的文章中曾提過．

結果，最後我用了 40 分鐘才把整個程式做完，然後直接跑程式給面試老闆看，接下來就是討論我如何做，有沒有什麼改進之處等等．

很抱歉，當時的程式碼就在那面試老闆的電腦裡，沒機會貼在這裡供大家參考．但還是把我當時的做法寫出來供大家參考．

如果你看到在那邊有相似的題目，再麻煩你分享網址．^_^

閱讀全文

#43 StackOverflow.com 2016 年度調查 - 有關畢業科系

調查網址 http://stackoverflow.com/research/developer-survey-2016

Stack overflow 在美國的資訊業界是個名氣響亮的網站，很多開發者都會在這邊做技術問題的問答與交流，因此這網站可說是許多 IT 產品的技術知識庫．在前陣子，他們公布了今年度的調查，調查的內容很廣泛，從年紀，性別，職業，薪水，國家，開發工具，程式語言等等，在最上面的網址可以看到他們調查結果的報告．

在這報告裡顯示了台灣有 76 個回答問題的人，這人數的確是蠻低的，不知道是不是因為英文的關係而讓參與討論的人數與訪問該網站的人數呈現很大的落差．從職業的角度來看，web developer 的人數是最多的 (full stack + front end + back end)，這也顯示了在 IT 業界中 web 相關的工作是最多的，同時也讓 Javascript 成為最普遍使用的語言．

這份報告的內容很多，有興趣的讀者可以慢慢分析，其中比較令我感興趣的，也就是在這個 blog 有關的，到底有多少人是非電腦相關科系畢業在從事程式設計的工作呢 ? 從這份報告算起來有 65.1% 的人是念電腦畢業的 (BS/BA in CS, Master in CS, PhD in CS)，也就是說將近 35% 的人們不具備電腦科學的學歷．想必這 35% 的人一定有很大的興趣在支持著他們在這行業裡繼續工作下去．

不知道這個比例在台灣的話是比較高還是比較低呢 ? 從以前到現在似乎沒看到有任何機構做過這樣的調查．如果你知道一些線索，再麻煩你告訴我．

現在許多的軟體與工具都做的很優良，讓許多非電腦科系畢業的朋友們只是經過適當的訓練或練習就可以真正上戰場去寫 code，在這過程中，我相信一定有人會半路退出了，也一定有人在這條路上找到了一些興趣而繼續努力下去．所以，我也會繼續努力地寫下去.

閱讀全文

#42 資料庫基礎 - Index 所用的資料結構 B tree

在前面的文裡談了有關資料庫 Index，說明了為什麼 index 能加速尋找資料，也說明了 index 有那些種類．在這篇文中，將來簡單談一下 index 所使用的資料結構．

看了前面的文章後，想必你也可以很容易猜出 index 所使用的是像 tree 那樣的資料結構．在前面的文章中也談到了最基本的 tree 資料結構概念．tree 其實在電腦科學的領域裡應用的相當廣泛，不論是學術上或工業界裡，因為 tree 帶來的好處實在很多，但要把 tree 寫出來其實也不是一件很容易的事．不同的應用會衍生出不同的 tree，而在資料庫的 index 所採用的 tree 叫做  B-tree．所謂的 B 就是平衡 balance 這英文字，所以中文你可以用平衡樹來叫它．

B-tree 所指的平衡是指樹的每一個 leaf 到 root 都是一樣的高度，所以整顆樹看起來站的很穩，不會有缺一角的感覺．

source: http://cis.stvincent.edu/html/tutorials/swd/btree

為什麼 index 要選擇這樣的 tree 來做為資料結構呢 ? 原因就在於這個 tree 是平衡的，所有 data pointer 都是在 leaf 的地方，也就是說當資料庫引擎在 B-tree 上找資料時，不論它要去那一個 leaf，它所花的成本都是一樣的，也就是樹的高度．所以，以使用者的角度來看，你今天打 select * from student where studentID ='1' 或 select * from student where stuentID='100' ，在 index 上所花的成本都是一樣的．簡單的說就是把所有的資料一視同仁，讓大家都有一樣的存取時間成本．我想這對資料庫使用者來說是件重要的事情，因為你應該不會想讓某些資料有特權來得到較低的存取成本．

接下來的問題就是，我們怎麼會知道這顆樹會一直平衡呢 ? 這並不是資料庫引擎所要擔心的事情，因為保持平衡是 B-tree 本身就要具有的能力，也就是說當一個新的節點新增到這顆樹來後，樹的平衡機制就要啟動來調整樹本身的結構以保持平衡，同樣地刪除節點也是．所以，要實做 B-tree 的重點就是要看保持 "平衡" 的程式碼是不是寫的夠好．在這裡，我就不談論太多保持平衡的細節，若你有興趣知道 B-tree 是如何保持平衡的，可以參考 http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html ，這個學校用圖案來表示當 B-tree 新增和刪除節點後是如何保持平衡的．

以外，B-tree 還有一些小變形，如 B+ tree，它是在 leaf 之間再加上一個 pointer 可以從一個 leaf 到下一個 leaf，這樣做的好處是我們可以在找到資料後，很快地再移到下一個資料而不需要每次都從 root 出發．我想這應該是大部份資料庫產品會採用的資料結構．

希望透過這篇文章的說明能讓你對資料庫 index 為什麼能為你快速找到資料有幫助．在了解了基本的原理之後，相信以後你在操作資料庫設定 index 時，心裡會有一種踏實的感覺，因為你知道資料庫引擎對這項工作運行時的基本原理了．

閱讀全文

#41 Load Balance 負載平衡

Load Balance 顧名思義就知道是在兩個以上的運算器環境下將每個運算器的運算負載量達成一致的目的．這樣子的概念應該在許多的情境之下，例如大型網站或是大型的資料庫等．這種類型的情境一定都有一個共同的特點，那就是 request 的 client 很多而提供 service 的 server 很少．

我們以大型網站服務為例子．最先開始架設一台網站伺服器來服務某一數量的用戶端，只要用戶端不繼續增加或是服務本身的運算邏輯沒有變的更複雜時，則一切都會相安無事．只要其中一個有增多的現象時，最終總是會面臨到該網站伺服器的資源不用使用的情況．因為每個用戶端連線都需要佔用 CPU/Memory 資源，所以既便是 CPU 再快 Memory 再多，也是會遇到上限．因此，要解決的方法有兩種，一個稱為 scale up，另一個稱為 scale out．Scale up 是指在同一個伺服器內進行硬體的升級以求在同一時間內服務更多的用戶端，例如升級 CPU，記憶體，網路卡等等．Scale out 是指再加入其他的伺服器來服務用戶端．通常來說，scale up的方式比較受限，而且一台伺服器若是要能裝入更多的 CPU 和 Memory，則價錢通常都是非常地高，所以比較經濟的做法就是 scale out．

Scale out 第一個會遇到的問題就是該如何分派工作．既然要達到負載平衡，也就是每台伺服器的運算負載量是接近一致的，那麼首要考慮的事情就是該如何達到一致．如果每個用戶端所要求的工作量都是固定的，很容易就可以做到負載量是一致的．因為只要在這些伺服器前都有一個 dispatcher 來輪流地分配工作，就可以達成負載量一致的效果，就如下圖一樣．

這種方式有一個缺點，dispatcher 將會是 single point of failure，單一失敗點，也就是說它若壞掉了，整個系統便無法運作．這種運作方式也稱為 Round-robin，輪流分配工作．在直實世界中，我們很難要求每一個用戶端都會有相同的運算工作量，因此每個用戶端送過來的需求一定會有不同的運算工作量，因此用 round-robin 的方式是很難達成負載量一致的，只能說是用戶端需求分配數量是一致的，因為很有可能某一個伺服器都會收到運算量很大的工作導致它比別的伺服器來的更加忙碌或是資源更吃緊．Round-robin 的方式算是集中式的管理，因為都是透過 dispatcher 來運作．

另外還有一種比較常見的負載平衡的方法是不需要 dispatcher，而是伺服器之間要互相溝通訊息，把自己的負載量資訊傳給其他的伺服器．所以每個一伺服器都會有一份每個伺服器負載量的資料，而且這分資料是經常地在更新．因此，當新的用戶端需求進來時，這份需求會先被某一個伺服器接收，然後該伺服器會依照這份資料來決定這份工作是要自己做還是傳給其他伺服器來做，這就看系統實作的是什麼樣的演算法．若採用最簡單的，也就是挑選負載量最小的伺服器，那這份工作就會被傳送到負載量最小的伺服器來處理．

這個方式聽起來似乎比較好，因為不會有 single point of failure 的問題，只是這樣的伺服器集合不適合有太多的伺服器在一起．我們簡單地想像一下，如果這個群組有十台伺服器，每一台伺服器在每隔幾秒鐘就要彼此交換負載量的資訊，這似乎不會是一個太麻煩的工作，但如果這群組變成是一百台或是一千台伺服器時，這樣的方法顯然會有問題，因為光是和其他 999 台伺服器完成一輪的負載量資訊交換可能就要花上一段時間和不少的 CPU 與 Memory，顯然不是一個經濟的做法，而且也不見得能儘量達成負載平衡．

其實在許多伺服器之間要對一份資料取得共識，也就是說一號伺服器上收集到的資料和 n 號伺服器上收集到的資料是一樣的，這也是一個很大的學問．往後的主題將會來討論這部份．

閱讀全文

#40 Coding 面試 - LeetCode #150 Evaluate Reverse Polish Notation

原文題目網址 : https://leetcode.com/problems/evaluate-reverse-polish-notation/

這題蠻有趣的．剛看到這題時，老實說並不知道什麼是 Reverse Polish Notation．如果你在被考到這題時也不知道的話，其實也沒關係，因為你可以直接問主考官，主考官一定會告訴你什麼是 Reverse Polish Notation．因為你要懂了這是什麼表示法，你才能做這個題目．

簡單的說，一般的數學，我們習慣寫成像我們從小到大看到的式子，例如 3+4．而 Reverse Polish Notation 就會寫成 34+ ，很簡單吧! 所以你看到題目上給你的例子， 2,1,+,3,* 就是 (2+1) * 3 ，因此答案就是 9．所以，這一題就是要考你寫一個 function，輸入是 Reverse Polish Notation，而輸出是數字答案．因此，我們假設輸入是一個 string array，而輸出是 int．

不知道你看到這種題目時，你會不會馬上聯想到 stack 或是 queue 之類的資料結構，因為可以依序地把數字儲存下來，又可以正向或反向地把數字取出來．如果你能想到這個，解題的方向也算是對的了．

除此之外，一開始還要為輸入字串做檢查，檢查是不是合格可運算的．例如，如果輸入字串都是運算符號而沒有數字，那這是不能算的，需要回傳錯誤．或者是輸入字串只有數字而沒有運算符號，這也是不能計算的．另外，輸入字串的第一個和第二個元素一定不會是運算符號，一定會是數字．所以這幾個條件就當做是程式裡的 throw exception 的條件．

接著，只需要一個 for loop ，把符合所有條件的數字用 stack 記錄下來，然後遇到運算符號時，把從 stack 把之前的數字拿出來運算，算完後再寫回去 stack．所以，用這樣的邏輯就可以把這題的答案寫出來了．

程式碼參考如下:

閱讀全文

#39 物件導向 - Interface 的基本應用範例

記得以前在學習物件導向語言的時候, 學到了 Class 定義,也學到的物件跟物件之間的關係, 後面也學到繼承關係. 在學習這些物件導向內容的時候也有看到 interface, 不過當時對 interface 並沒有太深刻的了解. 所以在這一篇文章裡面就來談一談 interface.

如果你做過一些小專案或者只是個人在用的一些小程式, 基本上來說 interface 用到的機會應該是不多. 相反的, 如果你曾參與大型專案, 那麼 interface 應該是到處可見的. 為什麼呢? 那是因為大型的專案通常是由多個開發者所共同進行, 所以不同的開發者會負責不同的項目, 你也可以把看成不同的開發者會負責不同的元件. 而在一個大型的專案裡, 元件跟元件之間的溝通是件基本的事情. 然而，元件跟元件之間的溝通不一定只是單純的資料傳遞, 傳遞的內容中有可能是物件本身. 所以, 元件和元件之間就必須要遵守特定的規則, 這樣子我們才能夠成功的將資料或者是物件傳送給對方. 除此之外, interface 的好處也可以應用在軟體測試上. 接下來用一些簡單的例子來說明.


這個例子是微軟開發工具產品裡面的某一個視窗, 而在視窗裡面有一些控制項, 它的長相大概就如下圖所示:

可以看到在這個視窗中有一塊大的空白, 裡面顯示這個不同的專案範本. 假設製作視窗元件的團隊和製作專案範本的團隊是不一樣的, 也就是說他們的程式碼是來自兩個不同的專案, 他們要怎麼做才能夠達成協同運作的目的. 其中的關鍵技巧就是使用 interface. 例如說有一個 interface 的定義如下,

public interface ITemplate {
    List<Template> GetTemplate(TemplateKind kind);
    List<TemplateKind> GetTemplateKind();
}

製作視窗的團隊中, 他們一定會去採用這個 interface 定義, 因為在這一個 interface 定義裡面提供了兩個方法. 第一個方法是取得有多少範本, 第二個方法是去取得有多少範本種類. 在他們顯示這一個空白區域的內容時, 他們就可以將這個介面定義作為參數,

public void ShowTemplates(ITemplate templates)

ShowTemplates 方法本身是可以由外部程式來呼叫的, 所以只要能夠準備好所需要的參數, 就可以將物件參數傳進去, 然後這一個方法就可以依照 interface 提供的方法把範本的種類和範本顯示在空白地域上.

所以透過這種方法, 開發範本的團隊就可以很清楚的知道需要傳過去的參數內容長相是什麼樣子．這樣看起來就像是兩個團隊之間有著共同的合約, 合約裡面的內容就是定義這會有哪些屬性或方法.

閱讀全文