The two most important days in your life are the day you were born and the day you find out why. -Mark Twain

#62 Coding面試 LeetCode #236 Lowest Common Ancestor of a Binary Tree

原文題目在 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree

題目是說給你三個 TreeNode, 第一個 TreeNode 是這個樹的 root, 第二個和第三個 TreeNode 是這顆樹裡面任意兩個 TreeNode. 所以,題目都這樣說了,你就不用擔心它會給你一個不在這顆樹裡面的 TreeNode.題目問你要在任意給你樹裡面兩個 TreeNode 後,你要找出這兩個 TreeNode 最低位置的父節點.所謂最低位置是指離 root 越遠越好.

看到這題目便想到跟 TreeNode 往上走到 root 的路徑有關,因為你要找的就是從任意兩 TreeNode 出發,會在那一個 node 第一次相遇.有一個很直覺的想法是在這兩個 node 一起往上走,但問題來了,你怎麼知道往上走要走到那去呢 ? 再者,任意兩 node 一起往上走不見得會在最小高度的 ancestor node 剛好碰在一起,因為任意兩 node 的高度不見得是一樣的.我當初想這一題時,便沒有想到要讓兩個 node 一起往上走,而是先讓其中一個 node 一直往上走到 root,把經過的 node 都記錄下來,完成之後便開始另一個 node 往上走,每往上走一個 node 時便比較第一個 node 是不是有走過同樣的 node,如果有的話,就代表找到了,如果沒有的話,就繼續往上走,一直到找到為止.

因此,我們需要把整顆樹的 "路徑" 和第一個參數 TreeNode 往上走的 "路徑" 記錄下來.在這裡,比較特別的是用 Dictionary (Hash table),而不是用 List.第二個參數的 node 只要在每一層往上走的過程中,檢查該位置的 node 是否在於第一個參數 TreeNode 的 "路徑" 就好了,其參考程式碼如下:



為何 Root 和第一個參數 TreeNode 的路徑是用 Dictionary (Hash table),而不是用 Stack/Queue 或 List 來記錄路徑.答案在以前的文章已經說明過了,這點就留給讀者想一想.

Share:

#61 出神入化的用介面 第二集_物件如何在大型軟體系統中移動

在上一集中談到最基礎的 interface 應用和簡單的例子,因此從上一集的內容中應該能讓你了解到 interface 的用途之一.interface 的用途很廣,除了可以做一些物件抽象化的表示方式以外,也可以用來幫助一個物件在一個大型的軟體中不受元件範圍的限制而讓其他不同的元件來使用.在上一集的內容中,你已經看到了最基本的抽象化應用,透過 email interface 的建立,讓所有的團隊可以依照同一份 interface 的規格實做出各自所用的物件,在這一集的內容中將展現一個極為簡單的例子用來說明一個物件如何在大型的軟體系統中移動.

首先,簡介此簡單的例子,下圖是這例子中的元件,一共有四個元件:


WindowsFormsApp1.exe 是整個軟體的基礎,它提供 IDE 介面,以及負責尋找系統上有那些元件,並且呼叫各元件的註冊程式,將每個元件所提供的功能記錄下來.

CommonLibrary.dll 是一個讓各元件都能使用到的共用內容,如一些共用的 interface 定義以及元件被註冊時所需要的空間.

ClassLibrary1 包含了該元件所提供的 Form 和相關的功能,同樣地,ClassLibrary2 也包含了一些 Form 和相關的功能.

上圖中的線條代表 dependency 關係,所以 WindowsFormsApp1 認識另外三元件,ClassLibrary1 只認識 CommonLibrary,ClassLibrary2 也只認識 CommonLibrary,所以 ClassLibrary1 和 ClassLibrary2 彼此並不認識,最後 CommonLibrary 完全不認識其他元件.這裡所用的 "認識" 就是 reference 的意思.

假設以上四個元件分別是由不同的團隊所製作而成,現在 ClassLibrary1 圖隊需要在他們自己的 Form 上面做兩個按鈕,而這兩個按鈕所需的畫面和功能分別是由 ClassLibrary2 團隊所提供的.正常來說,如果一個團隊要用到另一個團隊所開發的功能時,最直接且直接的方法就是將對方的元件在自己的專案中加入 reference,這樣做就能讓自己團隊的元件可以認識另一個團隊的元件,但這樣子做在較大型的軟體團隊中是不方便的,因為第一集已經說明過了.因此,如第一集所說的內容,比較好的方法是要做一個共用的 interface 讓兩個團隊都可以認識這個共用的 interface.於是,ClassLibrary1, ClassLibrary2, 和 CommonLibrary 這三個團隊做成了一個協議,CommonLibrary 團隊將製作一份 interface 讓 ClassLibrary1 和 ClassLibrary2 可以實做.除此之外,CommonLibrary 團隊還提供了一個 Dictionary 用雙方可以將自己實做好的元件放在這個 Dictionary 裡頭.

public interface IOperation
{
    string Name { get; }
    string Description { get; }
    int AddIntOperation(int i);
    string ChangeStringOperation(string input);
}

public class ObjectContainer
{
    public static Dictionary<string, IOperation> Operations = new Dictionary<string, IOperation>();
    public static Dictionary<string, Form> Dialogs = new Dictionary<string, Form>();
}

IOperation 介紹讓是讓雙方可以依自己的邏輯實做成物件,然後放在 Operations dictionary 裡面.因此,只要 ClassLibrary1 團隊知道如何在這個 dictionary 中取出 ClassLibrary2 所放入的物件,那麼 ClassLibrary1 可以使用 ClassLibrary2 團隊所提供的功能了,如 AddIntOperation(), ChangeStringOperation().

於是 ClassLibrary2 團隊將 IOperation 實做如下:

public class Operation2 : IOperation
{
    public string Name => "Operation2";

    public string Description => "This is Operation2 from ClassLibrary2";

    public int AddIntOperation(int i)
    {
        if (i < int.MaxValue - 1)
        {
            return i + 2;
        }

        return i;
    }

    public string ChangeStringOperation(string input)
    {
        return string.IsNullOrEmpty(input) ? null : input.ToLower();
    }
}

然後 ClassLibrary1 團隊在一個按鈕的 code-behind 寫出以下的程式碼來使用 ClassLibrary2 的 IOperation.

private void button2_Click(object sender, EventArgs e)
{
    if (ObjectContainer.Operations.TryGetValue("operation2", out IOperation op))
    {
        int i = 5;
        richTextBox1.Text += $"int starts at {i}\n";
        i = op.AddIntOperation(5);
        richTextBox1.Text += $"int becomes {i} after Operation2\n";

        string s = "aBc";
        richTextBox1.Text += $"sting starts as {s}\n";
        s = op.ChangeStringOperation(s);
        richTextBox1.Text += $"string becomes {s} after Operation2";
    }
    else
    {
        richTextBox1.Text = "Cannot find Operation2";
    }
}

這樣做的話不能成功,因為在 CommonLibrary 的 Operations dictionary 裡面並沒有 ClassLibrary2 所製做的 IOperation 物件,因此 ClassLibrary1 團隊使用上述的程式碼時會看到 "Cannot find Operation2" 的訊息.比較簡單的方法是在整個軟體一開始啟動的時候,ClassLibrary2 就得把 IOperation 物件寫入到 CommonLibrary 的 Operations dictionary 裡.當然,這並不是最好的方法,只是在這極為簡單的例子中,我們暫用這個方法來簡化許多細節.

因為 WindowsFormsApp1 是整個軟體的啟動點,所以我們就在 WindowsFormsApp1 啟動的時候來將相關的物件都寫入到 CommonLibrary 裡面.由於每個團隊會有不同的啟動邏輯,因此,每個團隊可以提供一個入口來讓 WindowsFormsApp1 直接呼叫,而這份入口裡的內容就是將自己的 IOperation 物件寫入到 CommonLibrary 的 Operations dictionary 裡.同樣地,除了 IOperation 以外,每個團隊也可以寫入不同的 Form 物件到 CommonLibrary 的 Dialogs dictionary 裡.

以下是 ClassLibrary2 團隊所使用讓 WindowsFormsApp1 執行注冊的內容:

public static class Starter
{
    public static void Register()
    {
        ObjectContainer.Operations["operation2"] = new Operation2();
        ObjectContainer.Dialogs["library2"] = new Lib2WinForm1();
    }
}

以上的做法是一個極為簡化的方式,在 ClassLibrary2 裡直接做一個 static method 讓 WindowsFormsApp1 呼叫,所以 WindowsFormsApp1 必須知道這一個 "入口".在正常的方式來說,WindowsFormsApp1 找到並執行 ClassLibrary2 的入口不會用這種直接的方法,因為這樣會把程式碼限制住,這方面細節的內容以後將再寫文章來說明,現在就先假設 WindownsFormsApp1 可以找到 ClassLibrary2 並且執行 Starter.Register() 來達成將 Operation2 物件和 Lib2WinForm1 物件寫入到 CommonLibrary 的 dictionary 中.因此,WindowsFormsApp1 的啟動程式看起來如下:

static class Program
{
    [STAThread]
    static void Main()
    {
        // 尋找相關元件並且執行他們所提供的註冊方法
        ClassLibrary1.Starter.Register();
        ClassLibrary2.Starter.Register();

        Application.Run(new Form1());
    }
}

這樣一來,ClassLibrary1 團隊就可以在 CommonLibrary 的 dictionary 裡找到 ClassLibrary2 所製做的 Form 物件以及 IOperation 物件,並且使用它們,如下圖所示:



Form1 是 WindowsFormsApp1 團隊製做的主要 Form,也就是整個軟體最基礎的 IDE,而 Lib1WinForm1 是 ClassLibrary1 所製做的 Form,透過 WindowsFormsApp1 的呼叫將它顯示在畫面上.在 Lib1WinForm1 裡第一個按鈕 (Let's show Lib2WinForm1) 的 code-behind 如下:

private void button1_Click(object sender, EventArgs e)
{
    if (ObjectContainer.Dialogs.TryGetValue("library2", out Form lib2WinForm1))
    {
        lib2WinForm1.ShowDialog();
    }
}

直接到 CommonLibrary 的 Dialogs dictionary 去找是否有 CommonLibrary2 的 Form 物件,如果有找到,就直接對它做 ShowDialog().因此,ClassLibrary1 團隊不一需要 "認識" ClassLibrary2 團隊的元件也可以將它提供的 Form 顯示在畫面上.

同樣地,Lib1WinForm1 的第二個按鈕 (Run Operation2) 是使用 ClassLibrary2 的 IOperation 物件所執行的功能,它的程式碼如下:

private void button2_Click(object sender, EventArgs e)
{
    if (ObjectContainer.Operations.TryGetValue("operation2", out IOperation op))
    {
        int i = 5;
        richTextBox1.Text += $"int starts at {i}\n";
        i = op.AddIntOperation(5);
        richTextBox1.Text += $"int becomes {i} after Operation2\n";

        string s = "aBc";
        richTextBox1.Text += $"sting starts as {s}\n";
        s = op.ChangeStringOperation(s);
        richTextBox1.Text += $"string becomes {s} after Operation2";
    }
    else
    {
        richTextBox1.Text = "Cannot find Operation2";
    }
}

當這個按鈕被按下後,它的結果如下:



你可以看到數字被加 2 (7 = 5+2) 並且字串變小寫 (abc),這都是前面提到 ClassLibrary2 所實做 IOperation 的內容.

當我們把 Visual Studio 的 break point 設定在這程式碼時,你會看到如下畫面:



此時,你可以看到 op 的 data type 是 IOperation,而它裡面真正的物件是 ClassLibrary2.Operation2.

這個範例用極為簡化的方式說明了 Interface 如何幫助 ClassLibrary2 團隊的物件可以在 ClassLibrary1 的程式中呈現,並且是在兩團隊元件互相不 "認識" 的情況下.

Operation2 的實做完全保留在 ClassLibrary2 裡面,其他團隊無法變更,也不需要知道實做細節,讓團隊之間的合作只需要關心 Interface 的定義.

用這個例子可以讓你看到不同的團隊各司其職而達成一個共同的目標.以上的例子 IOperation 是定義在 CommonLibrary,通常來說,自已團隊所開發的 Interface 應該是放在自己所定義的 Interface 元件裡,然後再將這一個 Interface 元件公開給其他團隊來使用.因此,這份 Interface 是大家都看的到,理論上你就不能修改,否則別人用了就會出現問題.下一集的內容將說明當公開共用的 Interface 需要修改時,該怎麼處理比較好.

Share:

#60 Coding面試 LeetCode #199 Binary Tree Right Side View

原文網址在這裡

這題是一個標準的走訪樹節點的題目.這題多一個限制,就是只抓出每一層最右邊的節點.因此,最簡單的方法就是用 breadth first 的走法,把每一層逐漸地一層層往下走.在每一層走完要往下一層走之前,把該層最後一個走到的節點儲存到欲輸出的 List 上即可.這題參考的程式碼如下:



通常來說你不會遇到一模一樣的面試題目.我能想到有關這一題的變化就是要能得到左右兩邊看的結果,或者是主考官規定你要用 depth-first 的走法來得到答案.有興趣的話,不妨試著寫寫這兩種變化題目.

Share: