## 資訊產業科技專案設計第一次作業
<contributed by 蔬菜煲-HotPot>

:neutral_face: ：interviewer
:smiley:：interviewee

### [160. Intersection of Two Linked Lists](https://leetcode.com/problems/intersection-of-two-linked-lists/)

:neutral_face: 嗨我是你今天的面試官，等等我們會出一些題目來測驗你的基本程式能力。
:smiley: 好的 。
:neutral_face: 首先題目會給你兩個 single linked list ，你要找出兩個 single linked list 相交的節點，若兩個串列沒有相交的節點則回傳 NULL 。以下有幾個例子...
對了這裡有一個要注意的地方，你寫的這個解法不能改變這兩個 single linked list 的結構，這很重要。那麼題目解釋完了，你有想提出什麼問題嗎?
:smiley: 好的，所以我確認一下這兩個 linked list 的 intersection 是指兩個串列使用相同的 ListNode 一樣 Memory location 的意思嗎?
:neutral_face: 沒錯。
:smiley: 好那我想再問一下，這兩個 linked list 的長度是題目會提供的嗎?
:neutral_face: 沒有喔，我們只會給兩個串列的開頭節點，長度的部分你可能要自己去遍歷取得喔。
:smiley: 好我了解了(開始畫圖) ，我想我會先找出他們的長度，然後根據比較短的串列長度 n 來一一比對較長串列的後 n 個 ListNode，因為他們一樣節點的個數不會超過較短串列的長度嘛。
:neutral_face: 好，那你可以開始寫程式了。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
    if(!headA || !headB)
        return NULL;
    
    struct ListNode *through = headA;
    int sizeA = 0;
    int sizeB = 0;
    
    for(;through->next !=NULL;through = through ->next){
        sizeA++;
    }
    through = headB;
    for(;through->next !=NULL;through = through ->next){
        sizeB++;
    }

    int short_len = 0;
    
    if(sizeA > sizeB)
        short_len = sizeB;
    else
        short_len = sizeA;
    
    
    struct ListNode *a = headA;
    struct ListNode *b = headB;
    
    while(sizeA - short_len > 0){
        a = a->next;
        sizeA--;
    }
    while(sizeB - short_len > 0){
        b = b->next;
        sizeB--;
    }
    
    while(a && b){
        if(a == b)
            return a;
        a = a->next;
        b = b->next;
    }
    
    
    return NULL;
    
}

:smiley: 基本上這個程式的時間複雜度是 O(m + n)，m 和 n 分別是 linked list A, B 的長度。
:neutral_face: 在小部分或細節上面你覺得哪個地方可以做得更好 ?
:smiley: 我覺得在三元運算子的地方我可以把它寫成 Min() 巨集做程式碼展開，這樣在程式多次呼叫的時候效率會高一些。

#define Min(x ,y) ({    \
    typeof(x) _x = (x); \
    typeof(y) _y = (y); \
    (void)( &_x == & _y);\
    _x < _y ? _x : _y; })

:neutral_face: 好，這題看起來沒錯。那接下來我們看下面一題。

### [3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)

:neutral_face: 這題的題目是請你計算出最長沒有重複字元的子字串長度，字串提供的內容就是英文大小寫、符號、數字。下面有幾個例子...。那請問你對這個題目有甚麼問題嗎?
:smiley: 好的，所以這個題目是會出現 ascii code 的符號比如 &@#$% 之類的嗎?
:neutral_face: 對的。
:smiley: 好的，那我認為我這裡可以使用 sliding windows 的方式。在沒有碰到重複字串前就使 windows 往前增大，若碰到重複的則使 windows 開始的地方往前縮小。至於計算是否重複可以用陣列儲存哪個 ascii code 有被計算過。
:neutral_face: 好那就試著寫看看吧

int lengthOfLongestSubstring(char* s) {
    
int hash_array[256] = {0};
char *start = s;
char *last = s;

int result = 0;
    
while(*last != '\0'){
    hash_array[*last]++;
    while(hash_array[*last]>1){
        hash_array[*start]--;
        start++;
    }
    last++;
    result = result > (last - start) ? result : last - start;
        
}
    
return result;

}

:neutral_face: 這個 code 看起來可行，不過使用到 hash_table 有沒有更快更有效率的方法?
:smiley: 我們可以紀錄目前這個 character 出現在這個字串的位置，這樣之後我們就可以直接剪掉重複的 idx 位置。
:neutral_face: 聽起來不錯，那你試著修改看看吧!
:smiley: 好的。

    int hash_array[256] ;
    int i;
    for(i = 0; i < 256; i++){
        hash_array[i] = -1;
    }
    
    int result = 0;
    
    char *start = s;
    int char_idx = 0;
    int last_start_idx = -1;
    
    for(; *start != '\0'; ch++,char_idx++){
        
        if(hash_array[*start ] == -1){
            hash_array[*start ] = char_idx;
            
        }
        else  if(hash_array[*start ] > -1){
            

            int repeat_one_idx = hash_array[*start];
            
            last_start_idx = last_start_idx > repeat_one_idx ? last_start_idx : repeat_one_idx; 
            
            hash_array[*start ] = char_idx;
            
        }
        
        result = result > char_idx - last_start_idx  ? result : char_idx - last_start_idx 

    }
    
    return result;
    

:smiley: 大概是這樣子的修改，可以一次前進好幾格，在字串長度拉長之後可以省下不少時間。
:neutral_face: 看起來沒甚麼問題，好今天的面試差不多到這裡，我們討論完後會再另行知會你，感謝。

## 檢討

* 打 code 的速度有很大的進步空間，打不用解釋的 code 時間太長會使得面試官失去興趣
* 在邊打 code 邊講述表達的時候會卡卡的
* 整個模擬面試過程還是需要看稿才比較能馬上反應，應該要練自然一點不用看稿順順的把解題思路講出
* Leetcode 刷得不熟，短時間內很難寫出臨時要 optimize 的程式碼