前面的文章曾提過，在這世界上有很多不同類型的問題，基本上我們太不可能找到一個方法來解決所有的問題．所以，不同類型的問題就會有不同的解法．有的解法很好理解並且單純，有的解法不易理解．解法本身並沒有所謂的好壞，只有適不適合使用的情況．通常來說，難的問題若要有好的執行結果，通常那個解法不見得簡單，就算是簡單，也絕非容易可以想的出來．這也許就是演算法美妙的地方，或許可以說是邏輯之美．廣泛地也可以說成是數學之美，都是宇宙空間裡所擁有的一些特質．
今天要提的解法是一種貪心 (Greedy) 的 “精神”．若你沒念過演算法這門課，恭喜你可以免除這個宇由特質的迫害，可以遠離那種整晚埋頭寫作業的崩潰時光．我想我是比較笨的，所以我以前寫演算法和計算理論的作業時，常常抱著頭在燒．如今，回頭看看，這些都是人生裡蠻有趣且值得回憶的時光．演算法課本裡，前面一半的內容中主要是提到一般市面上對問題的...
#77 部落格的原始動機與人生所需的財務智商
這篇文章來分享二個主題，第一是為何我開始寫這個部落格，第二是人生所需的財務智商．
我在 "大毛電腦科學筆記" 裡從 2015 年 3 月開始寫下第一篇文章到現在已經有三年半的時間了．剛開始的第一年，由於我沒有設計任何的讀者回饋方式，因此第一年並不知道寫的內容是否有用．後來第二年開始加入 Google Form 讓讀者們可以留下回饋資訊，並且也為網站上加入 Google Analytics 用來查看網站的流量資訊．大約一年前成立了 Facebook 社團以及舉辦公益課程來做為另一種推廣此部落格的管道．從去年 (2017) 開始，我陸陸續續收到一些讀者們的回饋，有些是單純地謝謝我寫這些淺顯易懂的內容，也有些是來問我一些工作上的問題．謝謝大家的捧場和問題讓我知道這個部落格已經發揮了一些作用．其實，我最早的想法並不是寫部落格，而是打算把所有的資訊匯集成冊出版用．早在十年前，我收集了以前在台灣和美國念的上課筆記，打算將這些內容寫成書來出版．但可惜，後來因為搬家緣故，那一大本的筆記已下落不明，所以把筆記匯集成書的想法便中斷了．但我並沒有忘記要分享電腦科學的基礎知識這件事．後來心想，匯集成冊需要大量時間並且有出版時程的壓力，於是...
#76 演算法裡一個基本的觀念 - Reduction
Reduction 是一個在演算法知識裡基本且簡單的觀念．其實在各位的工作中也一定常用到這觀念，只是你不知道而己．在這文章裡一如往昔，不用學術理論的描述方式，而是用平常寫程式的例子來讓非電腦科系畢業的資訊人了解什麼是 Reduction．
接下來用寫程式的角度來看什麼是 Reduction．假設你需要寫一個影像辨識的程式，這個程式需要辨識一個圖片裡是否含有某個數字，所以你寫的 function 可能會像下列:
This file contains bidirectional Unicode text that may be interpreted...
#75 將問題和演算法分類
學習基礎的演算法過程中，許多課本最常用的方式是將問題分類好，然後對每一類問題進行討論並給出一些著名的演算法來解決這一類的問題．因此，要了解自己面對的問題屬於那一類型的問題便是件重要的課題．在這一系列的文章中，我的目的並不是要告訴你大學課程的演算法內容，而是希望用一種比較實際工作上會遇到的普遍情況來說明在工作中可能會碰到跟演算法課本內容有關係的課題．就像上一篇文章提過的，演算法的內容就像是你寫的程式裡某一個 function，每一個 function 一定有一個特定的目的．因此，你可以想像世界上存在許多的演算法，每一個演算法都有一個目的．當你認識了許多演算法時，有一個簡單的方法來分類演算法的種類，就是按照目的來分類．只要你知道你的問題是屬於那一類，這樣你就知道該去找那一類的演算法．例如，你的工作裡某一個任務需要將資料庫中的訂單做排序，因此，你就可以在市面上找到許多的排序演算法，挑一個適合用在你的工作裡．排序是一個相當簡單的例子，你甚至不用找演算法，因為這類基礎的演算法都已被實做在許多產品裡．另外一個例子，你的工作是做一個檢查文章裡的英文字是否拼錯，如果拼錯的話，必須列出一些建議清單來讓使用者選擇．這一類的演算法通常不會在一般的...
#74 演算法從零開始
資料結構和演算法算是最基礎而且重要的知識．若沒有這兩個科目的足夠知識的話是很難在其他電腦科學領域有所進步的，其中也包括程式設計這一條路．基本上來說，程式設計這條路需要強大的邏輯基礎，除了你得對 if .. else .. for loop 用的很熟練外，你還得了解你所用的 SDK, framework 的優缺點，這樣使用起來，你才知道你的 SDK, framework 為你的程式做了什麼事情．除此之外，你便需要知道資料結構和演算法的基本知識，這兩個學科是能幫助你寫出好程式的關鍵．
從前面的文章裡，我談了許多資料結構及其應用，也談了許多面試考題．當你看完那些文章後，你應該能抓到一個重點，這重點就是儘量地省時間 (省運算步驟)，不然的話，就得用空間來換時間 (提高空間複雜度來降低時間複雜度)．雖然每一種問題的情況都不一樣，不見得都能用空間換時間，但至少這是一個讓你思考的方向．演算法在這過程中扮演了重要角色，因為這門學問能幫助你辨別問題，知道什麼樣的問題...
#73 Coding面試 LeetCode#14 Longest Common Prefix
原題目網址是 https://leetcode.com/problems/longest-common-prefix/description/
這一題在 LeetCode 的難易度分類屬於簡單級，題目的意思是你會得到一個 string array，然後你得從這個 string array 裡面找到最長從頭開始的共同子字串．在題目裡有給了簡單的範例，例如 Input: ["flower","flow","flight"] , 則答案就是 "fl"．如果找不到合適的子字串，就直接回傳空字串．同時題目也告訴你，input 字串只有 a 到 z 之間的小寫字母，不會有其他的符號，這個條件大大降低了答案的難易度，因為可以少一些大小寫辦別或特殊字元或文化上的處理．
解法的邏輯也相對單純．找出最短長度的字串，以它為基礎，然後去比對每一字串從頭開始的字母，以此類推做到有一個字母是不符合條件或是最短長度已經到達．
參考的程式碼如下:
...
#72 一秒38萬個交易的故事 - 資料庫引擎篇
與資料庫有關的文章到目前為止已張貼了二十二篇文章，這些文章所談論的內容大部份都是描述資料庫引擎裡 Storage 和 Transaction 的內容．資料庫引擎裡的內容當然不只這些，還包括 SQL query parser, query optimizer, logging manager, 以及一些基本的功能如 security control 等等．光是有關 storage manager 的故事就能寫一本書了，除非你想做資料庫引擎的專家才需要知道所有的細節，不然的話，只要了解一些基本的設計便能幫助你在工作上做到更好的境界．在這些二十二篇與資料庫引擎有關的文章，我寫的那些內容其實簡化或跳過不少的細節，但那些細節並不會影響你對資料庫引擎設計的了解，只讓你可以用比較高層次的角度來檢視資料庫引擎會為你做的事情．畢竟這些內容主要的對象是給非電腦科系畢業的資訊人所參考用，因此忽略了許多數學上的推導與比較．若你是電腦科系的學生正在學習資料庫理論，請以課本內容為主，因為課本內容裡面會用一些數學來明確表達運作成本等事情．為什麼要說這些呢...
#71 資料庫引擎 - Deadlock 偵測 (Wait-For graph)
前兩篇文章談完了 table join，接著這篇文章把主題拉回到資料庫的 Transaction．
之前文章曾提過 deadlock 的發生，這在關聯式資料庫裡算是件平常可見的事情．之前曾提過當 deadlock 發生時，資料庫引擎可利用 wait-for graph 來偵測 deadlock 的發生．這篇文章將說明什麼是 wait-for graph．
Wait-for graph 是一個簡單的圖形，是一個有方向的圖形 (directed graph)，也就是它圖形上的邊具有方向性，這裡的方向性用來代表是那一個交易等待那一個交易．如下圖:
上圖的...
#70 Coding面試 - LeetCode #5 Longest Palindromic Substring
原文網址 : https://leetcode.com/problems/longest-palindromic-substring
這一題與之前曾提過的試驗字串是否為 Palindromic 的題目蠻雷同的．如果搭配 Palindromic 字串的檢驗法用在這題上，可能的解法如下:
從上面的程式碼你可以看到是將所有可能的子字串從大到小的長度逐一檢查是否為 Palindromic．因為題目是要找最長的 Palindromic，所以子字串長度才會從大到小．上述寫法的空間複雜度是 O(1)，但時間複雜度卻是 O(n3) ，主要因為有三個迴圈與字串長度是有關係的．雖然上述的寫法可以在合格的時間內通過 LeetCode 的 test cases，但若你提了這樣的 solution，面試官很有可能會再問你在空間複雜度上還有進步的空間．
如果你從第一篇文章看到現在的話，你應該可以發現我在許多文章都提過不少次...
#69 資料庫引擎 Table Join 的運行方式 - 下集
在 table join 上集的文章裡談到了最基本的 table join 運作的方式，也讓你知道資料庫引擎是如何進行 table join．你可以發現到不論用什麼方式進行 table join，資料庫引擎所處理的資料必須位在記憶體中才能被處理，因此，將資料從硬碟讀到記憶體的次數和方式將是主宰了整個大部份的執行時間．因此，要讓 table join 的完成速度變快就得在資料從硬碟讀到記憶體的過程中去下點功夫．由於資料量有大有小，記憶體的量也有大有小，所以不同情況下可能要採用不同的方法才能達到最好的效果．接下來，這篇文章來談談另一種 table...
#68 資料庫 Table Join 的運行方式 - 上集
在資料庫引擎中，table join 是一個很重要並且常見的動作．這一篇文章將討論以邏輯上來看資料庫引擎是如何進行 table join 的動作．
假設資料庫中有兩個表格，一個是學生表格，一個老師表格，這兩個表格裡都各自有一個 id 欄位用來代表學生編號與老師編號．對這兩個表格來說，這個 id 非常適合做為 primary key．學生表格裡有一個欄位是老師 id，這用來代表某學生的班導師是某位老師．這是一個一對多的關係，所以只要在學生表格上有一個老師 id 的欄位便能說明這個關係．用一個簡單的 SQL 語法可以用來表示這樣的關係
Select...
#67 IT人生 - 有關你的銀行戶頭
最近工作上和生活上寫太多 code 了，用了許多腦筋，於是今晚決定來休息一下 ，來寫篇與 IT人生有關的事情．今天的主題將和錢有關係．
由於我花了太多的時間在學校，當我在博班三年級決定離開學校去工作時，我已經三十五歲了．當時的我，口袋沒什麼錢，只是一個剛離開學校的窮人．以前二十多歲時雖然也沒什麼存款，但錢這件事並沒有真正對自己產生很大的衝擊．這樣的情況在我三十五歲離開學校後沒多久有了很大的改變，因為我當時看到了一個調查．這份調查是台灣一份財經雜誌，針對台灣三十五歲以上的人所做的調查．這份調查的內容主要是詢問被調查者在三十五歲時是否擁有超過一百萬以上的資產．根據這份調查結果，75% 左右的調查者在三十五歲時並沒有一百萬元的資產．當時才發現自己也是在 75% 的這一群人中，仔細想想，一百萬並不是很多的錢，許多人都當成是人生的第一桶金，而自己連第一桶金也沒有，這似乎是件不太妙的事情．在那之後便讓我開始重視有關錢的事情．首先要做的功課就是除了一般的工作薪資以外，還有什麼方式可以增加收入，好為自己的未來與退休生活做準備．接著找了許多資料和評估自己的情況後，我選擇的方式是...
#66 Coding面試 LeetCode #24 Swap Nodes in Pairs
原題網址 : https://leetcode.com/problems/swap-nodes-in-pairs
題目與一般的 List 題目類似，主要都是在考 next pointer 的位置安排．這一題比較特別的是兩兩成雙來交換位置，交換的邏輯並不會太難，用心推演一下就能推導出來，只有處理第一個 node 時需要做點額外處理即可．題目中有特別規定答案只能使用 constant space，也就是指你使用記憶體的量不能和輸入的 List 大小有關係．除此之外，題目也要求不能更改 node 裡的值來做交換位置的方法，所以你該做的就像一般 List 的考題來換 next pointer．參考的程式碼如下:...
#65 資料庫引擎的交易資料鎖定 (Lock) 策略
延續上一次資料庫的交易文章內容，在一個資料庫系統中同一時間可以執行多個交易 (Transaction)．在這同時執行的交易內容中，當遇到共同讀取和寫入同一個物件時，此時便有很大的機會將發生如上一篇文章中提到的資料衝突現象．為了要解決這個現象，資料庫引擎得採取一種策略．以學術的角度而言，策略有好幾種，但比較常見和合理的策略將是本篇文章中將討論的資料鎖定 (Lock)．
Lock首先定義上一段文字中所說的 "共同讀取和寫入同一個物件"，物件是指交易內容中所感興趣的資料．可能是一筆資料，例如某一個學生的基本資料，可能是符合某條件的資料，例如去年十月份的所有訂單．以邏輯處理而言，通常來說這資料可能只存在於同一個表格，但也有可能存在於多個表格．以實體上而言，資料有可能在同一個...
#64 資料庫引擎交易 (Transaction) 進行中的讀寫異常
前面的文章曾談到交易 (Transaction) 需要具有 ACID 的特性．在一個繁忙的資料庫系統中一定會有許多的交易同時執行，這篇文章便來談論許多交易同時執行時會遇到那些挑戰．
許多交易在進行時，非常有可能會遇到對相同的資料進行讀或寫的動作．如果所有的交易對相同的資料進行讀的動作，則這情況並沒有什麼好擔心的，因為所有的交易對這份資料都是讀的動作，早讀和晚讀都是同一個答案，所以不會造成任何的資料異常現象．但如果情況變成其中有一個交易或多個交易對同一份資料進行寫的動作時，那麼早寫和晚寫就會有很大的影響了．因此，我們在乎的情況便是當有交易在進行寫的動作．以下假設某個資料庫系統中有兩個交易，這兩個交易會對同一份資料進行讀和寫的動作:
如上圖所示，T1...
