我記得這一題我被問過兩次，是兩個不同的團隊，而且都是跟資料庫有關的工作．所以，若你也要尋找資料庫相關的開發工作，看來 Tree 的題目是很難避免的．
這題的題目很單純，就是要寫一個 function 用來驗證題目的 Tree 是不是 Binary Search Tree (BST).
根據 BST 的定義，左邊的節點值必需小於父節點值，而右邊的節點值必需大於父節點值.
但這題有一點要小心的是，別只是檢查父節點值而己，應該要檢查所有上層的父節點值都要小於或是大於．
如果題目只給你 tree root，那麼你可以寫出像下面的 function 來檢查這個 tree 是不是 BST.
public bool IsValidBST(TreeNode...
#26 資料庫基礎 - 存取 Page (Sorted File)
上一篇文章談的內容是針對資料之間是沒有順序的情況，因此在尋找資料時就是採用依照資料的排列順序來尋找．因此整個尋找過程的時間複雜度是 O(n) ．通常來說，資料庫設計者不會讓這樣的事情發生，除非資料本身是一個相當小的參考資料而己，否則資料一旦多了， O(n) 實在不是一個好現象．
在真實世界中的應用，我們常常可以為資料找到至少一種排列方法，例如，在學校的資料庫中，基本上可以用學生證的號碼來排序學生的資料，因為在同一個學校裡不會有相同的學生證號碼．我們在前面的文章中也提過，一旦資料排序過了之後，時間複雜度就會從 O(n) 下降成 O(log...
#25 資料庫基礎 - 存取 Page (Heap File)
在前面的幾篇文章中提到了資料庫引擎讀取與寫入資料時在面對固定長度與非固定長度時所可以採用的儲存方式，其中提供了 Page 為一個儲存空間的管理單位，透過 Page 的機制，讓資料庫引擎能以 Page 為單位做資料讀取與寫入的動作．搭配上 Page 裡的 manifest 資料，資料庫引擎就可以很清楚地知道這個 Page 裡面有多少筆資料以及有多少剩餘空間可用．這時候我們把層次往上拉高一點來看，那 Page 跟 Page 之間的關係是如何定義呢 ? 舉例來說，當某一個表格裡的資料繼續變多時，這些資料很可能會需要很多的...
#24 我的 IT 人生 - 簡短篇
這一篇內容我不談資料結構，也不談資料庫，更不談寫程式，我來簡單地談一談自己的 IT 人生．
在我還是高中生時，當時有接觸一些電腦課，學會了操作 MS-DOS 系統，也會寫一些簡單的 BASIC 程式，對電腦的確是有相當興趣，但還沒想過要把它當成一生的工作方向．後來，念了大學之後，我念的是機械工程，原本我的打算是想要念電機工程，因為自認為在物理課本中，電學念的比力學好很多，不過也奇怪，我當時還是把機械工程填入到志願卡裡，若我印象沒錯的話，我記得我的志願卡裡還有土木工程電子工程等等相關的工程科系．大學四年就這樣念到畢業了，說實在，到現在我還是覺得大學那 4 年似乎是浪費的，因為我現在沒需要用到任何機械工程的知識．不過，人生就是這樣，現在回過頭來看，就當做是用人生的時間換來了一些人生經驗．
接著，學校畢業後就直接去當兵了．我想這是我整個...
#23 Coding 面試 Leetcode #73 Set Matrix Zeroes
我打算把以前遇到的一些在面試時遇到的一些特別經驗或感想記錄在這電腦科學筆記裡，一方面，在面試時會遇到的問題大部份都是基礎的電腦科學題目，二方面也把這些過程記錄下來，當做是一種紀念吧!
在美國的軟體行業裡，要做 coding 面試算是很正常的事情，而這些 coding 面試大部份都是資料結構和演算法的內容，所以都是大學的必修課．但其實有許多題目還真的不是光念過課本就能想的到，那些題目還真的需要多練習．在市面上有許多網站會列出一些常見的面試考題，而我之前最常去的網站就是 Leetcode. 這網站不僅記載了許多考題，而且還有 online judge 可以直接測驗你的程式碼是否正確.
今天來聊聊這一題，在 Leetcode 網站上的第 73 題．我被問過一模一樣的題目，面試者連改都沒有改，而這一題也讓我體會到另一種空間複雜度的境界．...
#22 資料庫的資料實體儲存單位 Page - 3
在來延續上一篇文章 (#21 資料庫的資料實體儲存單位 Page - 2) 的內容．在上一篇的文章中看到了如果沒有 page 的概念時，資料庫引擎有那些可行的方法來在硬碟上管理資料，從上一篇文章中，你看感受到空白空間的處理與以及資料的定位並不是很方便．於是在階層管理的方便性上多加了一層 Page．
在一般市面上常見的資料庫產品中，Page 的大小都大約在幾Kb之間，類似於作業系統的儲存單位大小．所以，一個資料庫可能會包含一個或多個資料庫檔案，而每一個資料庫檔案都會包含多個 Page．
我們再看看如何用 Page 來管理資料．如上一篇文章的情況，資料有可變長度與固定長度兩種．固定長度的情況是比較單純好處理，可以參考下圖:
上圖是某一個...
#21 資料庫的資料實體儲存單位 Page - 2
延續上一篇文章 (#19 資料庫的資料實體儲存單位 Page) 的內容，在這篇文章裡，我們來談談有關資料庫的實體儲存結構．所謂的實體儲存結構是指資料放在硬碟中的情況．
首先，我們先來看看一個很簡單的結構，資料長度是固定的．這種情況在前面的文章有提過．因為長度都是固定的，所以每筆資料的長度便可以固定，這樣好處是在於方便計算也方便存取．
另一種情況是資料長度不是固定的，這種情況在前面文章也有提過．因為長度不是固定的，因此必須要想一個方法把不同欄位的資料做一個區隔，這樣在讀取資料時才知道什麼情況下是資料欄位的終點．在實體資料儲存時，有兩個方式可以來達成這種目的．第一，在每個資料欄位之間都用一個特殊符號隔開來，長相如下:
上圖是用一個...
#20 The Power of Ten - 撰寫可靠軟體的思維
標題為 The Power of Ten - Rules for Developing Safety Critical Code 的文章刊登在 IEEE Computer 2006 年 6 月的月刊中，作者是位在 NASA JPL 實驗室的研究科學家，同時也是位學者和工程師．這篇文章可以在 http://spinroot.com/gerard/pdf/P10.pdf 看到．
若以武功修練來比喻的話，這篇文章就像是一個得道高人所寫下來的內功心法，他把自己在 JPL 實驗室工作的多年 C 語言工作心得濃縮成十項重點，作者也為每一個重點留下說明．雖然這一篇文章是將近十年前的文章了，但它的參考價值極高，而且我相信許多資深的軟體工程師幾乎都會同意作者所寫的內容．
其中有幾點並非在所有的程式語言中都會碰的到，尤其是跟記憶體管理有關的工作．以現在一般商業應用裡最常見的...
#19 資料庫的資料實體儲存單位 Page
在上一篇文章中提到了有關資料庫 Storage manager 一點點的資訊．因此，這一篇文章就來談談更基礎的東西，叫 Page．它是什麼呢 ? 它就是 Storage manager 在處理儲存資料上的一種邏輯格式，也就是每個邏輯儲存空間的大小．這樣說可能還不好了解，讓我來直接舉個例子．資料庫引擎中有一個管理員叫 storage manager，它是負責資料儲存和讀取用，也就是說，今天使用者發出一個請求如 select * from table123，那麼這個命令就會經由資料庫引擎裡各式各樣的管理員來做語法確認解析，來做語法最佳化，然後可能還會經由其他管理員的檢查，最後才會到...
#18 資料庫的表格裡有關 nchar 和 nvarchar 的選擇
今天正在思考要來寫個不學術的事情，也就是希望能寫個跟產品相關程度較高的主題，想著想著，突然有個回憶就突然閃過腦子．
大約在十年前，當時還在台灣念碩士班，有位在台灣 IBM 工作的朋友剛好介紹了一個很短期的工作，因為他們急著做一個專案，但臨時抽不出過多的人手來完成這些功能，所以就經由朋友的介紹去參與這項專案的開發，賺一點零用錢，只需要做 5 個 tasks 就行了．當時，我記得是用 Javva 開發，然後資料庫產品是 DB2．不過，當時我做的短暫工作跟資料庫並沒有直接關係．
有一天，我到專案辦公室時，剛好看到 PM 正在輸入一些新的 database schema，我好奇在他旁邊看著那些 schema 資料，然後我就發現了一件頗為特別的事情，所以字串相關的資料欄位都是設計為 nchar，比如...
#17 客戶說程式碼不能有 recursive function，該怎麼辦 ?
不知大家有沒有被客戶這樣要求過，寫程式一律不準出現 recursive 的寫法．這也是十年前左右的故事了，並不是我個人遇到的狀況，是我朋友們遇過的情況．當時對這樣的要求沒太多的頭緒，不過心裡還是把這問題放著，也許有一天我會知道為什麼．
後來，有一次因為一個考試，突然讓我想到這個問題可能的答案，從技術角度來看的話，我想這應該是客戶的顧慮．情況是這樣的，在作業系統中，每個工作被執行的單位是 Process．一個作業系統裡會有許多的 Process 在執行，分別負責不同的功能，例如，有 Process 是專門負責處理 DNS 封包，有 Process 專門負責與印表機的通訊．所以，我們若自己寫一個程式在作業系統裡執行，這個程式也將是一個 Process，作業系統也就會負責他所需要做的工作內容．
在每個...
#16 我是非電腦科系的，真的需要懂這些嗎 ?
這問題其實一個很好的問題．
我假設你是個非電腦科系畢業出身的軟體工程師，回想一下，你當初憑著自己的邏輯能力學習如何寫程式，也學習如何善用大家所熟知的 framework，便可以應付自己工作上所遇到的問題．我想那是因為你的工作以及所面臨到的專案都是屬於商業型導向的應用程式．我所謂商業型導向的應用程式就像是你在金融界中工作，每個需要處理的就是把資料讀出來做報表，或把資料新增進去到資料庫，或是把這資料用某一種格式包裝起來，然後傳到其他的系統再做更多的資料處理．又比如說你在不同領域裡做該領域的工作，例如在航空公司做訂票系統，在電信公司做帳務系統，在電子商務公司做庫存系統．這些軟體工作其實在台灣是佔大多數的．所以，在這些工作中，若你沒有懂這些資料結構或演算法，你照樣也可以把程式寫出來，系統照樣地可以上線，公司照樣可以營運賺錢．因為我自己也曾有過這一段路，所以我知道是可能的．
不知你是否曾問過自己，我怎麼知道我寫的程式是不是好的，我該怎麼評估，或是別人又會怎麼看待我的寫程式能力．我相信非電腦科系畢業的人在做軟體工程師時一定會有這樣的問題．如果你有這樣的問題，很恭喜你，因為你的內心對知識有了渴望，因為你想知道自己的能力或寫程式的技巧是在什麼程度．所以，最好的方法就是回到事情的本質去找答案．因此，資料結構是需要懂的，演算法也是需要懂的，但我們並不用像...
#15 資料結構 Tree
Tree 應該是我們所需要介紹的最後一個基礎的資料結構了．在資料庫的領域中，你可以看到 Tree 在那裡發揮的淋灕盡致．以我個人來說，我喜歡把 Tree 看成是一種 List 的變形金鋼．前面在談論到 List 時，你可以發現 List 的元素後面只會接著一個元素，就這樣一個一個串接下去，這種情況就可以用在作業系統的檔案儲存．你可以把一個檔案想成是一個 List，而檔案的內容就會依照固定的大小分割成很多個元素，然後依照順序排好串在一起，這些元素就會散落在硬碟空間中，他們不需要排列在一起，所以同一個檔案的內容在放置時，可能是最後的元素放在硬碟空間前面的位置，因為元素之間都有一個...
#14 資料結構 Queue
在基礎的資料結構裡，Stack有一個好兄弟，長的跟它有一點像，但是提供的行為結果卻剛好相反，它的名字叫 Queue．在 Stack 中有一個可以把資料放入的行為叫 push，而把資料讀出來的行為叫 pop，並且最重要的重點是最先放進去的資料將會後最後被讀取的，所以這是一種先進後出或後進先出的情況．
類似於 Stack，Queue 也提供了方法可以將資料寫進去和讀出來，習慣稱為 Enqeueue 和 Dequeue．而跟 Stack 最大的不同就是 Queue 先寫進去的資料將會是先被讀出來，是一種先進先出或後進後出的情況．
你可以在資料結構的課本看到以上的內容，也可以找到 Queue 是如何被實做的，通常來說用 Array 來實做 Queue 會比較單純一點，只要一個 Array...
#13 利用 Hash Table 來增加你的資料處理速度
還記得十多年前參加一個專案時，自己做了一件不好的資料處理方式，當時的我還不知道什麼是 hash function．在那時候專案部份的工作需要快速地處理大量的資料，透過資料庫連線讀取資料，然後再讀取相關的參考資料，再經過運算，最後把結果再寫回資料庫，如果你的方法是讀一筆寫一筆的話，那肯定會造成大量的資料庫 I/O，所以比較適合的方法是做批次的處理，也就是一次讀取某個足夠數量的資料筆數，處理完成之後再一次寫回去，這樣可以減少資料庫的 I/O，也可以讓程式運行起來速度可以快些．
以上的想法是可行的，但當時有一個小小的挑戰是有關參考資料，因為資料在運算的過程中必需依靠其他的數據才能計算，而這些數據多達 8 萬多筆資料，簡單的說，它是三個欄位構成，第一個是分行 ID，第二個是一個會計科目 ID，第三個資料值．
...
