#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 號伺服器上收集到的資料是一樣的，這也是一個很大的學問．往後的主題將會來討論這部份．

閱讀全文