# info2024-homework2
> 歐麥-Allmine
> 哈哈球-Hahaball
> R : Interviewer, E : Interviewee

| 影片 | Interviewer | Interviewee |
| -------- | -------- | -------- |
| [影片1](https://www.youtube.com/watch?v=8zD7ZNKfKKo) | 哈哈球 | 歐麥 |
| [影片2](https://www.youtube.com/watch?v=EohokVYF_Ug) | 歐麥 | 哈哈球 |

## [20. Valid Parentheses()](https://leetcode.com/problems/valid-parentheses/)
R : 您好，我是哈哈球，我們最近有一個改進內部IDE的需求，當開發人員在寫扣時，經常會出現括號不匹配的問題，這不僅可能導致執行錯誤，也會增加代碼調試的負擔。為了改善這一點，我們希望在內部的 IDE 中添加一個即時的括號匹配檢查功能。這個功能要能即時檢查各類括號（如 `()`, `{}`, `[]`）的匹配情況，並在發現不匹配的括號時立刻顯示提示，以協助同仁迅速找到並修正錯誤。

### (Repeat)
E : 所以您的問題是, 我需要實作一個功能, 檢查IDE裡的括號是否有各自正確匹配?

R : 對的

### (Example)
E : 兩個左括號`([`, 如果對應到兩個右括號`])`就可以回傳`True`
但如果括號大小不匹配, 例如`{(})`,或是數量不匹配`{}}}}`,則都要回傳`False`

R : 對的,僅需考慮括號數量匹配與否, 不用考慮大小括號優先順序問題

### (Approach)
E : 好, 我先寫下方法,
我想用`stack[]`LIFO的特性, 來記錄括號的順序,
遇到左括號就push進`stack`,
遇到右括號則pop, 但要與`stack`最上方的左括號匹配,以及top不能為`-1`,否則就回傳`false`
最後回傳`top==-1`

#### psuedo code

top = -1
stack[top]
1. *s = '(', stack[++top] = *s;
2. *s = ')', if(top>-1且stack[top]=='(') 跳出switch-case, 否則return false
最後return top==-1.

R : 恩,你的做法聽起來沒有太大的問題

### (code)

bool isValid(char* s) 
{
    int len = strlen(s);
    char stack[len];
    int top = -1;
    while(*s!='\0')
    {
        switch(*s)
        {
            case ')':
                if(top>-1 && stack[top--]=='(') break;
                else return false;
            case ']':
                if(top>-1 && stack[top--]=='[') break;
                else return false;
            case '}':
                if(top>-1 && stack[top--]=='{') break;
                else return false;
            default :
                stack[++top] = *s;
                break;
        }
        s++;
    }
    return top==-1;
}

#### 時間複雜度:O(N), 空間複雜度:O(N)

R: 那可以請你用`()[]`解釋一下程式如何運行嗎?
### (Test:) `( )[ ]`
E : 跑測資

R: 在switch-case的部分, 針對左括號的操作邏輯看起來一樣的, 那可以請你用if-else將左括號的操作統一處理嗎?

### (Optimization)

bool isValid(char* s) 
{
    int len = strlen(s);
    char stack[len];
    int top = -1;
    while(*s!='\0')
    {
        if(*s=='('||*s=='['||*s=='{')
        {
            stack[++top] = *s;
        }
        else
        {
            if(top==-1 || \
               (*s==')' && stack[top]!='(') || \
               (*s==']' && stack[top]!='[') || \
               (*s=='}' && stack[top]!='{')){
                return false;
               }
            top--;
        }
        s++;
    }
    return top==-1;
}

#### 時間複雜度:O(N), 空間複雜度:O(N)

R: 恩, if-else的部分也沒有甚麼問題, 感謝您今天的寶貴時間。

## [9. Palindrome Number](https://leetcode.com/problems/palindrome-number/)
R: 你好，我們公司最近在對文本處理和自然語言處理(NLP)中需要做更精確的識別和分類，而其中一項關鍵技術為回文(Palindrome)的檢查，它可以幫助識別一些特定語義或文本的特徵，並應用於判別抄襲或重複內容，甚至是垃圾郵件的檢測。為了簡化測試，為了簡化測試，我們將以整數作為文本內容，請你寫出一個能達到上述效果的函式。

### (Repeat)
E: 所以在這個問題我會先拿到一個整數，那這個整數有可能是正數或是負數吧?而我需要做的事情就是去檢查他是否為一 Palindrome ?

R: 沒錯。

### (Example)
E: 舉例來說，假使我今天拿到的數字是 -595 ，那就要回傳 `False` ，而如果是 595 就要回傳 `True` ?

R: 是的。

E: 那我的想法會是先去判斷輸入的數是否為正數，如果不是直接 return `False` ，是的話再去做回文的判斷。而判斷的方式為從 `x` 的個位數開始往高位移動，並記錄每一次的值，使得最終得到一個與 `x` 完全相反的數，最後再去判斷兩數是否相等即可。

### (Code)

bool isPalindrome(int x) {
    if(x < 0)
        return 0;
    int temp = x;
    int rev = 0;
    while(temp > 0){
        rev = rev*10+temp%10;
        temp /= 10;
    }
    return rev == x;
}

R: 看起來是可行的，但如果輸入的整數位數比較多，那就會造成 overflow 的情況，你的程式碼有辦法改進嗎?

E: 那如果是考量到 overflow 的情形，主要發生的地方會在程式碼中 `rev = rev*10` 的操作，因此我會選擇將 `rev` 的型態從 `int` 改為 `long long` ，如此一來便能使用 64 個位元去儲存。

int rev;  ->  long long rev;

### (Test) : 464

R: 你使用了 long long 讓 `rev` 從 32 轉為 64 bits ，這的確可以讓它擁有更大的數值範圍，那如果我希望不使用 `long long` 呢?

E: 如果不希望使用 `long long` 且又要避免 overflow 的情況發生的話，那我會選擇用陣列來解決這個問題。首先，將 `x` 的每一位數儲存至陣列裡，然後直接對陣列中相對應的位置判斷是否相等即可，例如有一個大小為 4 的陣列，若他是回文，則 index 0 和 3 的值以及 index 1 和 2 的值必須相等，若有不相等的情況發生則不用繼續比較，直接回傳 `False` 就可以了。

bool isPalindrome(int x) {
    if(x < 0)
        return 0;
    int temp = x;
    int count = 0;
    while(temp){
        temp /= 10;
        count++;
    }
    int* arr = (int*)malloc(count*sizeof(int));
    for(int i = 0; i < count; i++){
        arr[i] = x%10;
        x /= 10;
    }
    for(int j = 0; j < count/2; j++){
        if(arr[j] != arr[count-1-j])
            return 0;
    }
    free(arr);
    return 1;
}

R: 謝謝你今天的參與。

## 初步自評
### 影片1 : Interviewee
* 聲音有點小
* 時常用滑鼠反白做說明, 除非有分享螢幕, 否則Interviewer會看不到
* [2:48](https://youtu.be/8zD7ZNKfKKo?t=168), [5:15 ~ 5:40](https://youtu.be/8zD7ZNKfKKo?t=315)應為`stack[top--]=='('`,stack最上方須對應到`(`左括號,　才能`pop`出,直到[8:03](https://youtu.be/8zD7ZNKfKKo?t=483)才發現錯誤

### 影片2 : Interviewer
* 與Interviewee互動過少, 提出問題後就沒有交流了
* [3:23](https://youtu.be/EohokVYF_Ug?t=203) 問如何避免`overflow`時, 應該用實際遇過的問題包裝來詢問Interviewee如何改進