Finding Most Frequent Duplicates Mode(s) in Binary Search Tree (BST) in C

描述

不同於傳統二元搜尋樹，節點的值可以重複，所以左子樹的值小於等於根的值，右子樹的值大於等於根的值，在樹上找到重複頻率最高的節點(們)並回傳

範例

輸入：空樹
輸出：{}

輸入：單節點

    0
   / \

輸出：{0}

輸入：不同節點各出現一次

    0
     \
      1

輸出：{0,1}

輸入：某節點出現二次

    1
     \
     (2)
     /
   (2)

輸出：{2}

輸入：某些節點出現二次

    (3)
   /   \
 (1)    5
 / \   / \
0   2 4   6
   / \
 (1) (3)

輸出：{1,3}

想法

要先知道哪些/個節點出現頻率最高，必須先走訪節點們比一次。取得最高頻率後，找出節點出現頻率等於最高頻率的個數，用這個動態分配回傳陣列的記憶體，再走訪一次把出現頻率最高的節點(們)加入陣列。

情境是記憶體有限，想一次走訪用雜湊表紀錄節點值和頻率，除了發生衝突(conflict)會算錯頻率，記憶體因為表太大爆掉，變成不得不用時間換空間。

實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void get_modes(struct TreeNode *root, double *last, int *freq, int max, int *modes, int *i)
{
    int val = root->val;
    
    if (root->left)
        get_modes(root->left, last, freq, max, modes, i);

    if (*last != val)
    {
        *freq = 1;
        *last = val;
    }
    else
        (*freq)++;
    
    if (*freq == max)
    {
        modes[*i] = *last;
        (*i)++;
    }
    
    if (root->right)
        get_modes(root->right, last, freq, max, modes, i);
}

void get_num_of_modes(struct TreeNode *root, double *last, int *freq, int max, int *returnSize)
{
    int val = root->val;
    
    if (root->left)
        get_num_of_modes(root->left, last, freq, max, returnSize);
    
    if (*last != val)
    {        
        *freq = 1;        
        *last = val;
    }
    else
        (*freq)++;
    
    if (*freq == max)
        (*returnSize)++;


    if (root->right)
        get_num_of_modes(root->right, last, freq, max, returnSize);
}

void get_max_freq(struct TreeNode *root, double *last, int *freq, int *max)
{
    int val = root->val;
    
    if (root->left)
        get_max_freq(root->left, last, freq, max);
    
    if (*last != val)
    {
        *freq = 1;
        *last = val;
    }
    else
        (*freq)++;

    if (*freq > *max)
        *max = *freq;
    
    if (root->right)
        get_max_freq(root->right, last, freq, max);
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findMode(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    
    int *modes = NULL;
    double last = -2147483649; // Out of int range to avoid 0 case
    int freq = 0;
    int max = 0;
    int i = 0;
    
    if (root == NULL)
        return NULL;
    
    get_max_freq(root, &last, &freq, &max);
    
    freq = 0;
    last = -2147483649;
    get_num_of_modes(root, &last, &freq, max, returnSize);

    freq = 0;
    last = -2147483649;
    modes = (int *)malloc(sizeof(int) * (*returnSize));
    get_modes(root, &last, &freq, max, modes, &i);
    
    return modes;
}

Validating Binary Search Tree (BST) in C

描述

驗證二元搜尋樹是否有效，有效的二元搜尋樹必須符合下列原則

• 左子樹的值小於根的值
• 右子樹的值大於根的值
• 左右子樹也是二元搜尋樹

範例

• 有效

無節點

單節點

    0
   / \

左右子樹

    2
   / \
  1   3

• 無效
有相同的值

    1
     \
     (1)

右子樹節點的值小於根的值

    10
   / \
  5   15
     / \
   (6)  20

左子樹節點的值大於根的值

    3
     \
     30
    /
   10
     \
     15
       \
      (45)

原理

用中序走訪(inorder traversal)二元搜尋樹取得節點的值會升冪排列，一旦走訪節點的值小於等於前面節點的值，就不是有效二元搜尋樹

實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool validate(struct TreeNode* root, double *last)
{   
    if (root->left)
        if (validate(root->left, last) == false)
            return false;
    
    // Check ascending order
    if (root->val > *last)
        *last = root->val;
    else
        return false;
    
    if (root->right)
        if (validate(root->right, last) == false)
            return false;
    
    // Subtree is valid
    return true;
}

bool isValidBST(struct TreeNode* root){  
    double last = -2147483649; // integer type minimum is -2147483648, last should be able to store integer minimum
    
    if (root == NULL)
        return true;

    return validate(root, &last);
}

Remove nth node from end of a linked list in C in Linear Time

描述

刪除從串列尾巴往回數第n個節點，n一定有效，回傳輸出串列的head

範例

輸入：1->2->3->4->5, n = 2 輸出：1->2->3->5
輸入：1, n = 1 輸出：NULL
輸入：1->2, n = 2 輸出

想法

用兩個距離n+1的串列指標，一個走訪在前，一個跟在後，走訪在前的指標碰到串列尾節點時，後面的指標在欲刪除節點的前一個。前述的想法適用於3個以上的節點，所以0到2個節點用特殊狀況處理。

實作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    int x = 0;
    struct ListNode *rear = NULL;
    struct ListNode *ahead = NULL;

    // Empty linked list
    if (!head)
        return head;
    
    // Linked list with one node, n must be 1
    if (!head->next)
        return NULL;
    
    // Linked list with two nodes, n is either 1 or 2
    if (!head->next->next)
    {
        if (n == 1)
        {
            head->next = NULL;
            return head;
        }

        return head->next;
    }
    
    ahead = head;
    for (x = 0; x < n; x++)
        ahead = ahead->next;   
        
    // head is to be removed
    if (!ahead)
        return head->next;
    
    rear = head;    
    while (ahead->next)
    {
        ahead = ahead->next;
        rear = rear->next;
    }
    
    rear->next = rear->next->next;
    return head;
}

Check if Parentheses is Valid in C

規則

• 括弧只有'('、'['與'{'三種
• 括弧必須成對
• 括弧順序必須正確

範例

有效

• "()"
• "{}[]()"
• "[{}]"

無效

• "([{]})"
• "(]"
• "([])("
• "([])}"

原理

• 遞迴：有效的成對括弧內必含有有效括弧
• 堆疊：有效的成對括弧順序是close先進open後出
• 不符合以上原則都是無效括弧

實作

// MODE 0 for recursive, 1 for iterative
#define MODE 1

struct stack {
    char items[65535];
    int top;
};

void push(struct stack *s, char c)
{
    s->items[s->top] = c;
    s->top++;
}

char pop(struct stack *s)
{
    s->top--;
    return s->items[s->top];
}

bool open(char c)
{
    return c == '(' || c== '[' || c == '{';
}

bool worker(struct stack *t, char *s)
{
    char s0 = s[0];
    char top = '\0';
    
    if (s0 == '\0')
    {
        // No pair for open
        if (t->top != 0)
            return false;
        
        return true;
    }
    
    if (open(s0))
    {
        push(t, s0);   
        return worker(t, s + 1);
    }
    
    // No pair for close
    if (t->top == 0)
        return false;
    
    top = t->items[t->top - 1];
    
    if (s0 == ')' && top != '(')
        return false;
    
    if (s0 == ']' && top != '[')
        return false;

    if (s0 == '}' && top != '{')
        return false;

    pop(t);
    return worker(t, s + 1);
}

bool isValid(char * s){
    struct stack t = {0};

#if MODE == 0
    return worker(&t, s);
#else
    int i = 0;
    char c = '\0';
    char top = '\0';

    for (i = 0; s[i] != '\0'; i++)
    {
        c = s[i];
        
        if (open(c))
        {
            push(&t, c);
            continue;
        }
        
        // No pair for close
        if (t.top == 0)
            return false;
        
        top = t.items[t.top - 1];
        if (c == ')' && top != '(')
            return false;
        
        if (c == ']' && top != '[')
            return false;
        
        if (c == '}' && top != '{')
            return false;

        pop(&t);
    }
    
    // Check no pair for open
    return t.top == 0;
#endif
}

Finding Length of Longest Substring without Repeating Characters in C in Linear Time

出處

原理

走訪字串中每個字元，若當前被掃瞄字元沒有被走訪過則暫存到陣列中，目前長度加1，否則判斷當前被掃瞄字元是否在不重複字元的子字串中，若不在則目前長度加1，否則檢查最大長度與目前長度，若目前長度大於最大長度就將最大長度設定為目前長度，並且移動不重複字元子字串的起始點到重複字元的下一個字元，例如輸入為"dxdy"，遇到第二個d而且d已經在不重複字元子字串"dx"中，則不重複字元子字串起始點從d移動到x，例如輸入為"pwwkew"，遇到第二個w而且w已經在不重複自原子字串"pw"中，則不重複自原子字串起始點從p移動到第二個w，最後重設目前長度，長度應為新的不重複字元子字串起始點算到當前被掃瞄字元，走訪完所有字元後的目前長度再跟最大長度比較決定最大長度。

實作

#define NUM_CHAR 256

int hash(char x)
{
    return x % NUM_CHAR;
}

int length_of_longest_substring(char * str)
{
    char visited[NUM_CHAR] = {0};
    char temp[NUM_CHAR] = {0};
    char * current_scanned = NULL;
    char * nrcs_start = NULL;  // nrcs: non-repeating character substring
    int key = 0;
    int cur_length = 0;
    int max_length = 0;
    
    current_scanned = s;
    nrcs_start = str;
    while (*current_scanned != '\0')
    {        
        key = hash(*current_scanned);
        if (visited[key] != *current_scanned)
        {
            visited[key] = *current_scanned;
            cur_length++;
            goto end;
        }
        
        strncpy(temp, nrcs_start, cur_length);
        if (!strchr(temp, *current_scanned))
        {
            cur_length++;
            memset(temp, 0, NUM_CHAR);
            goto end;
        }
        
        memset(temp, 0, NUM_CHAR);
        
        if (cur_length > max_length)
            max_length = cur_length;

        while (*nrcs_start != *current_scanned)
            nrcs_start++;
        nrcs_start++;
        
        cur_length = current_scanned - nrcs_start + 1;

end:
        current_scanned++;
    }

    if (cur_length > max_length)
        max_length = cur_length;
    
    return max_length;
}

The Clean Code Talks - Don't Look For Things! 整理

重點整理：

• 用細緻的方式回到基本去討論依賴注入(Dependency Injection)
• 測試系統時需要實例化物件，實例化物件時常放了很多測試替身(Test-double)進去，讓測試更困難
• 類別的靜態變數有時牽涉到單例(Singleton)設計模式，要一起實例化，讓測試更麻煩
• 實例化很困難意味著難以測試
• 超文本文件類別為例，文件只在乎客戶端產生的文件，不需要瞭解客戶端如何產生文件
• 車類別為例，車只在乎產生的引擎，不需要了解引擎怎麼產生

服務定位器模式(Service Locator pattern)的問題：

• 違反得墨忒耳定律(Law of Demeter a.k.a. LoD，簡單說即只拿直接需要的物件)
• 將服務定位器傳給要實例化的物件，看建構子參數不夠，還得追建構子程式碼才知道相依的物件，這會隱藏物件間真正的相依性
• 以房子類別為例，實例化房子卻傳入整個家的狀態，追建構子才知只要門、窗與屋頂
• 給房子還要給整個家的物件，導致物件重用性變差
• 解決方式是不透過定位器，明確將門、窗與屋頂作為參數傳給房子
• 此舉能讓獨立測試變得容易
• 服務定位器把查詢與建立物件的功能混淆
• 還需要額外的介面、覆寫或仿造服務定位器的設定方法(setter)
• 以致一旦依賴服務定位器，也需要依賴其他跟服務定位器有關的東西
• 服務定位器有很多別名，本質上都是只需要部分物件但給了全世界

得墨忒耳定律：

• 以結帳為例，一般來說只會拿錢(直接需要的物件)給店員(請求物件的物件)，不會整個錢包(全域狀態)給店員
• 只請求直接需要的物件
• a.getX().getY()亦即間接取得物件即違反得墨忒耳定律
• 好萊塢法則(Hollywood principle, that is "Don't call us, we'll call you")

破解依賴注入的迷思

• 子物件新增一個參數，則父物件要一路傳遞參數直到給子物件
• 事實上父物件並不負責建構子物件，父物件並不知道子物件怎麼建構的，所以也沒有傳遞參數的問題
• 房子類別為例，房子並不知道門有門把，房子只需要建構好的門物件
• 工廠模式(Factory pattern)負責將物件組合起來，與業務邏輯分開
• 同一個生命週期的類別們只要同一個工廠組合就夠，並不用一個類別一間工廠，所以不會導致類別倍數增生
• 注入的物件生命週期應該大於等於被注入的物件，如果有生命週期較短的物件，應該調整架構，將短生命週期的物件分群

偏執狂程式設計(Paranoid programming/coding)

• 到處是空指標檢查讓測試變得困難
• 測試房子的油漆功能不需要門，傳入門的空指標，但門的空指標檢查讓測試無法繼續
• 與其到處用先決條件檢查，不如用許多測試確保程式能跑
• 如果物件是給外部使用的應用程式介面(API)，加入先決條件檢查是合理的
• 但若給內部使用，一堆先決條件檢查表示對程式的穩定性沒有信心
• 產品程式碼不應該傳空指標給物件，應該用空集合代替，若希望傳入的集合做事就實作方法，不然就給無操作(NOP a.k.a. NOOP)
• 測試程式碼可以傳空指標給物件，目的在表明此物件與測試無關
• 產品程式碼不應該在工廠類別外的類別呼叫new運算元，即業務與建構邏輯混淆
• 測試程式碼為了實例化小部分的程式做測試可以呼叫new運算元

總結

• 絕大部分的情況應該避免呼叫new運算元實例化物件，除了最基底的類別或物件圖的葉類別，其餘有與其他類別互動的類別，應該請求物件
• 將業務類別與建構類別分開，測試會變得容易，因為可以將業務邏輯與建構邏輯分別獨立測試
• 若將業務與建構邏輯混淆，測試建構邏輯時還不得不跑業務邏輯做的事

Q&A

• 問：是否建議不需要假(dummy)物件？
• 答：否，當測試的時候，無關的物件可以傳空物件進行無操作(NOP)，空物件是假物件更強的表現形式

"The Clean Code Talks -- Inheritance, Polymorphism, & Testing" 整理

重點整理：

• 讓程式碼更好懂、更好測試與更好擴充
• 盡可能用多型代替if
• 一個類別負責一種事情
• 若看到switch則用多型代替
• 若出現重複判斷某個flag的if則用多型替代
• 把建構子類別(工廠模式)與業務邏輯類別分開，在建構時做if判斷，處理業務邏輯時就不用一直做if判斷

優點：

• 多型能讓不同的功能分散在不同檔案
• 程式碼更好被理解與測試
• 能讓重複的if判斷改成集中在一個地方
• 不再有重複的程式碼，減少錯誤發生
• 用類別將負責工作分開，不再需要全域變數做狀況判斷

Q&A重點整理：

• 確保類別只單一繼承，多重繼承表示類別負責多種事情
• 多型在運算子實例化時就決定，類別的方法只會給那個類別用，不會一個類別只在某些狀況用到某些方法，另一些方法在別種狀況才用到

練習：

寫一個小專案盡可能用多型代替if

10 Tips For Clean Code 整理

引言重點整理：

• 為了趕交期寫出骯髒的程式碼，產生更多臭蟲，日後改版會讓維護成本越疊越高
• 看程式碼與寫程式碼的時間比例最好落在10:1
• 花時間寫出易讀的程式碼，日後更易寫

十點建議：

1. 為程式碼的品質負責，別為了交期放棄專業態度與做法
2. 與其用簡短的變數加註解，不如把變數意義直接寫在變數上，好的程式碼如一篇散文，變數就是散文中的名詞
3. 函數/方法宣告名稱要表達明確的意圖，不需要前後文、不用先懂他的類別就知道意思
4. 註解常說謊，盡量做到程式碼即註解（CTO說這個比較有爭議性。其他文章看到頗認同的是，好的註解是寫「為什麼」，後續開發者看註解才能理解並檢討前人的動機）
5. 童子軍守則(Boy Scout Rule)，改善訪視過的程式碼讓他變得更好（實務上最好問一下原作:P）
6. 單一功能原則(Single-responsibility Principle a.k.a. SRP)：一個函數/方法/類別幾乎只做一件事，一個需要太多參數的函數可能做太多事；一個類別某些物件只用到部分性質與方法，另一些物件則用到其他的，這個類別應該拆分成多個類別
7. 寫測試，分為整合性測試與單元測試，使用測試驅動開發
8. 疊代式開發，用畫畫比喻，漸進/疊像是把畫中某一塊畫到完美再進行下一塊，反覆/代是先畫整張畫的草稿，再上底色，再做後續直到完美
9. 軟體架構是獨立的，用來支持使用者案例，框架只是用來達成架構的工具，不是要遵循的架構，講者用WordPress舉例
10. 練習，練習，再練習，台上一分鐘，台下十年功

The Clean Code Talks - "Global State and Singletons" 整理

重點整理：

• 全域狀態(Global State)會有幾個問題：測試時每次結果不一樣(Flakiness)；測試時必須有順序；某些測試無法平行進行
• 單例(Singleton)封裝了全域狀態
• 有全域狀態的程式會變得很難測試
• 單例直接或間接碰到的變數或狀態，理論上會變成無限多個
• 測試無法觸及實例化的單例中的私有變數，只能寫專門測試的方法來測
• 單例(Singleton)容易產生欺騙性的API
• 欺騙性的API獨立測試會產生許多問題，必須回溯並解決相依類別
• 相依類別間沒有明顯的順序性，讓最佳化效能或流程增加許多阻礙或負擔
• 有依賴注入(Dependency Injection)，測試目標類別初始化與其相依類別的順序會很清楚，後續開發者看到程式碼很容易了解類別初始化的流程。
• 依賴注入強制編譯時期初始化的順序
• 每一個相依類別可以獨立測試

Q&A重點整理：

• 不要混淆業務邏輯與物件初始化
• 只有需要用到相依物件的物件才知道相依類別，其他層不會知道
• 依賴注入讓類別間的相依明確，若一個類別初始化時吃太多參數，也許是這個類別負責太多事情，最好將它拆開成不同類別
• 某些情況，例如框架強制無參數的建構子，導致無可避免地使用單例，則委派某個單例類別專門處理這些事情，用最少的力氣去處理它
• 每個物件應該知道它直接合作的物件，間接需要的物件不應該知道
• 當一個應用程式需要多個實例來執行不同的任務，全域變數會阻礙這樣的可能性
• 即使一個環境有許多全域變數，能避免使用它可以讓程式更容易測試