# info2023-homework2

> 影片: [漢語](https://youtu.be/6YdHBCxfCq4)
> 🐇:Interviewee
> 🧔:Interviewer

## [143. reorder list](https://leetcode.com/problems/reorder-list/description/)
🧔:你好，我是Kevin, 我希望你能幫我們解決公司有人不小心把資料給打亂了，中間已經有人嘗試修復過，這整串資料每一筆雖然能正常存取下一筆，但我們剛好發現第一筆資料的客戶名稱與最後一筆相同，第二筆與倒數第二筆相同。為了解決這個問題，我希望你能幫忙把正確的資料相關性回復正常，讓同樣客戶資料的先放在一起!
🐇:好的沒問題，我是Sundew，我想先確認一下希望得到的結果，請問每筆客戶資料會超過兩筆以上嗎; 第二個是資料是否存在於一個列表當中呢? 還是必須透過前一筆資料才能存取下一筆。

🧔:對，客戶資料只會有兩筆，必須透過前一筆才能存取下一筆。
🐇:OK好沒問題，那因為資料性質，我會把他想成Linked-List, 並且她是Singly Linked-List, 那在解決這個會用到Recursion... 影片解釋

🧔:OK，聽起來很直覺的做法，不過你有辦法在更快嗎?
🐇:若要省去時間的話，我可能要思考一下，因為我想說用一個額外的空間去儲存算是另一個相對直覺的方式。

🧔:好，這個方法聽起來OK，你想要試著寫寫看嗎?
🐇: 沒問題，我馬上開始，請問有限定語言嗎? 要用C寫嗎

struct UserData{
	//…
	//unique value
	//User Unique ID => hashtable

	//O(n) space, O(n)
	//data head tail 
	//id1_1 -> id1_2 -> id1_3 -> id2_1
	//id2_1 -> id2_2 -> id3_1
	//id3_1 ->
};

struct DataNode{
	UserData val;
	DataNode* next;
}

typedef struct DataNode DataNode;

struct DataNodeStack{
	DataNode* head;
	//push
	//pop
	//top
};
typedef struct DataNodeStack DataNodeStack;


void reorder(DataNode* datas)
{
    if(!datas)
        return;

    DataNode* tmp;
    DataNodeStack stack = malloc(sizeof(DataNodeStack));

    //1 2 3 4
    int n = 0;
    while(tmp)
    {
        ++n;
        stack.push(tmp);
        tmp=tmp->next;
    }
    //1 2 3 4
    //4 3 2 1
    int i=0;
    tmp = datas;
    DataNode* l,*r;
    for(i;i<(n+1)/2;++i)
    {	
        //first
        //1
        //4
        // 1->4 -> 2 -> 3 ->NULL

        //second
        //2
        //3
        l = datas;
        r = stack.top();
        datas=  datas->next; //2
        stack.pop();//3	

        l->next = r;
        r->next = datas; //4->2
    }
    //r =3 
    //1 2 3 4 5
    //1 5 2 4 3 ->NULL
    r->next =NULL;
    datas = tmp;

}

🧔:沒有特別限定語言，不過你都提到C了就用C吧，不過資料結構不用實作沒關係。
🐇:好，謝謝Kevin. 馬上開始 ...

🧔: 那妳可以試著用Testcase跑一次嗎
🐇:OK ...

🧔:那最後請你告訴我這個時間複雜度與空間複雜度
🐇:好的 time: $O(n)$, space: $O(n)$，因為...

🧔:那這個方法會用到一個額外的空間，請問你有辦法省去這部分的空間嗎?
🐇:哦那我需要思考一下

🧔:這邊可以給你一點提示，妳可以思考一下要怎麼過程中調整成像你剛使用的資料結構。
🐇:意思是調整成像是Stack對吧，如果是要這樣的話必須先找到要調整的範圍。喔喔!因為資料性質的緣故，可以調整後半段就好，因為資料是兩兩配對。

🧔:那麻煩你用程式碼證明你的想法吧!
🐇:OK! 馬上...

struct UserData{
	//…
	//unique value
	//User Unique ID => hashtable

	//O(n) space, O(n)
	//data head tail 
	//id1_1 -> id1_2 -> id1_3 -> id2_1
	//id2_1 -> id2_2 -> id3_1
	//id3_1 ->
};

struct DataNode{
	UserData val;
	DataNode* next;
}

typedef struct DataNode DataNode;

struct DataNodeStack{
	DataNode* head;
	//push
	//pop
	//top
};
typedef struct DataNodeStack DataNodeStack;


void reorder(DataNode* datas)
{
    if(!datas)
    return;

    DataNode* tmp;
    DataNode* half = datas,*last = datas;

    //1 2 3 4
    //      ^  ^

    //1 2 3 4 5
    //get place
    //O(n/2)
    while(last->next&&last->next->next)
    {
    //1 2 3 4 5
    //  ^   ^
    //    ^   ^
    //  half  last

        last = last->next->next;
        half = half->next;
    }

    if(last->next)
        last = last->next;

    tmp = half->next;
    half->next = NULL;
    half = tmp;

    //O(n/2)
    //reverse
    DataNode* prev = NULL;
    //half last reverse
    while(half)
    {
        tmp  = half->next;
        half->next = prev;
        prev =half;
        half = tmp;
    }
    // 1 2 -> NULL
    // 4 3  -> NULL

    //4 3 2 1
    int i=0;
    tmp = datas;
    DataNode* l,*r;
    //O(n/2)
    while(last)
    {
        //first
        //1
        //4
        // 1->4 -> 2 -> 3 ->NULL
        //second
        //2
        //3
        l = datas;
        r = last;
        datas =  datas->next; //2
        last = last->next;

        l->next = r;   //1 ->5 ->2 ->4 -> 3
        r->next = datas; //4->2 //5->2

    }
    datas = tmp;

    //time O(n), space O(1)

}

🧔:那麻煩最後告訴我時間與空間複雜度
🐇:時間複雜度的話是$O(n)$ 空間是$O(1)$

🧔:那最後想給你一個Follow up Question. 麻煩告訴我你的想法，如果現在超過兩筆以上客戶資料被打亂了，那我們又希望你把同客戶的資料先擺在一起，你會用甚麼方式解決呢?
🐇: 意思是每個客戶超過兩筆以上都被打亂了嗎? 如果是這樣的話可能會用客戶資料Unique的ID來用Hash map儲存後再把資料全部串接起來。

🐇:更多解釋...

🧔:OK，這樣的方法的確可行，時間上OK，為了要壓低時間使用O(n)的空間是沒問題的! 今天謝謝! 你有解決我們的問題了!
🐇: 謝謝 88

## 初步自評
### 優點
- 有盡力把REACTO重複，確認想法OK才執行
### 可改進的地方
- 語助詞其實有點多，我都會用OK 或是對來當影片的開頭... 方便結尾，不過我在講話的時候好像都會有這樣的習慣。

## 對其他同學的批評
### [第一簡介](https://hackmd.io/6lFSD9swQKmZm2v1h3yjGg?both)
> 他評02
#### 優點
- 英語能力一定要提升，溝通是最重要的!
#### 反面
- 一定要記得邊寫程式邊與面試官互動，不然會非常尷尬

### [第二簡介](https://hackmd.io/@sysprog/B1_UjB6ya)
> 他評02
#### 優點
- 講話清晰
- 確實執行REACTO的效果能讓面試感覺更好
#### 反面
- 思考一下如何包裝題目
- interviewer若不想要interviewee執行暴力法，應發出質疑，或是打斷interviewee

### [第三簡介](https://hackmd.io/@sysprog/BkRj-LaJa)
> 他評01
#### 優點
- 有做到Follow up
- 讓我知道我C語言能力超差。
#### 反面
- 當面試官聽到做法時，沒有質疑時其實可以盡力想想看，不用在意時間，盡力把時間用光。

### [第四簡介](https://hackmd.io/@sysprog/HkOb6HaJT)
> 他評02
#### 優點
- 有確實給出情境，可以讓 interviewee 更快進入狀況
- 刻意說 $2^{−32}$~$2^{32}$ 之間，試圖測試 interviewee
- 舉例很詳細! 在REACTO的T做得很
#### 反面
- 關於Function return為何 以及 為什麼input是int, 感覺可以說明一下，面試官有用稍微不直覺的方式，是給機會發揮。
- 盡量讓Code的命名方式相同，也許在面試時會忘記

### [第五簡介](https://hackmd.io/@sysprog/HJmI6rpy6)
> 他評03
#### 優點
- 使用小畫家，但我不確定面試時能不能用

#### 反面
- A(Approach)的部分是可以看面試官是否接受你的做法，假設你做的方向不如預期，他可能會就打斷你，或是給方向才進行C(Code)
- 可以重述R的部分，讓自己表達想法之餘，增加思考時間，並且激盪新的解法。
### 整體
- 其實要真的練到面試就是要多思考Follow up
- 以及要能達到70%的表現其實就取決於自己刷題的量
- 在與面試官面試時其實也能感受公司的氣氛，如果都是很嚴肅的說明題目以及要求解決，其實會讓人瞞不開心的
- 在思考解法時不要就單純思考，必須要與面試官互動，讓他能給予提示。