電腦科學 ^ IT人生 ^ 公益課程

#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;
        }

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





Share:

#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 的精神.

Share:

#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. 後面的文章會再繼續介紹其他方法.

Share:

#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 人生寫的很簡短,現在我有新的人生方向,但短期內還不會離開資訊業,就如同前面說的,這一切都是自己的選擇而造就自己的人生經驗,也希望這些經驗能提供其他年輕人做為參考.如果你認為我有值得讓你參考之處,歡迎你留言給我. ^_^

Share:

#23 Coding 面試 Leetcode #73 Set Matrix Zeroes

我打算把以前遇到的一些在面試時遇到的一些特別經驗或感想記錄在這電腦科學筆記裡,一方面,在面試時會遇到的問題大部份都是基礎的電腦科學題目,二方面也把這些過程記錄下來,當做是一種紀念吧!

在美國的軟體行業裡,要做 coding 面試算是很正常的事情,而這些 coding 面試大部份都是資料結構和演算法的內容,所以都是大學的必修課.但其實有許多題目還真的不是光念過課本就能想的到,那些題目還真的需要多練習.在市面上有許多網站會列出一些常見的面試考題,而我之前最常去的網站就是 Leetcode. 這網站不僅記載了許多考題,而且還有 online judge 可以直接測驗你的程式碼是否正確.

今天來聊聊這一題,在 Leetcode 網站上的第 73 題.我被問過一模一樣的題目,面試者連改都沒有改,而這一題也讓我體會到另一種空間複雜度的境界.

第 73 題的題目是指,給你一個 m x n 的矩陣,如果在第 (i,j) 的位置上出現 0 時,就要把 row i 和 column j 的元素全部變成 0.剛看到這個題目,覺得不會很難.最直覺的方法是你可以宣告兩個 Array 或 List 來記錄那些 row 和 column 裡面有 0 ,最後再依據 Array 或 List 的內容把相關 row 和 column 的內容變成 0.如果你是這樣想的,其實這方法也沒什麼不好,只是要多浪費一點空間,因為另外宣告了額外的 Array/List 來記錄那些 row, column 有 0 的元素存在,而且 Array/List 的大小會根據矩陣的大小而改變,因此在空間複雜度上就不是 constant 了,而是 O(m+n).如果這時候面試官沒繼續要求的話,那基本上就過關了.但生活中有時很難會如此順利,面試官很可能會要求你在空間複雜度上做到 constant space.也就是說你可以用其他的空間,但是這些額外的空間不能隨著矩陣大小變化而改變.

既然是這樣規定的話,這題目就真的變得有相當的難度了.我自己在做這題目時也無法在五分鐘之內想到好的解答.為什麼是五分鐘呢 ? 因為一個面試通常是一小時,其中做 coding 考試的時候大約有三十分鐘,所以在五分鐘之內沒有想出正確答案的話,那就很難可以在剩下的時間把程度寫完在白板或電腦上.
後來,我參考了網路上其他人的解法,我找到一個蠻好的解法.基本上,這個解法要宣告兩個基本的變數,這是  constant space,而它把每個 row, column 有 0 的資訊直接記錄在輸入矩陣之中,因此,根本就不需要用到非 constant space 的空間了.



如果你用心把這個解法看完的話,你一定也會覺得這方法實在太妙了,而且保證你對空間複雜度的應用會有更高一層的體會.原來把 input parameter 的空間拿來做為暫存空間,也是一種省空間的好方法.

Share: