# 2024 年「資訊科技產業專案設計」課程第 2 次作業
> 貢獻者 : 西格瑪-GigaChad , 派中星-Patrick
> [面試錄影-1](https://youtu.be/ZnDru0LCt1c?si=lLII1mrXow9v26sV)
> [面試錄影-2](https://youtu.be/RB74B5jd3wY)

## [49. Group Anagrams](https://leetcode.com/problems/group-anagrams/description/)
> :man: interviewer : 西格瑪-GigaChad
> :baby: interviewee : 派中星-Patrick

:man:: 你好，派中星，我今天要面試給你的題目是Group Anagrams，給定一個string的array叫做strs，要你把array中不同的Anagrams區分出來後放進同一個group，答案不用經過排序。

:baby:: 請問他不用經過排序的意思是?

:man:: 同一個group內不同順序

:baby:: 我想要先確認一下我的理解，我的理解是這個題目是要把字串中所有字母的集合相同的放在同一個群裡面

:man:: 對

:baby:: 我現在直覺想到的方法是使用hashtable，因為同一群的字母都一樣，如果經過排序的話，同一個group的字串排序後的結果都是相同的，所以排序完的結果把他當成hashtable的key作為一種辨識的標籤，表示字串中只要字母的集合(字母可重複)是相同的話就是屬於這個標籤，那麼他就是屬於這個group內，那麼就把他放進此key對應的value，所以key是string，value是vector

:man:: 好，那你可以開始把他實作出來了

:baby:: 那我現在使用C++實現，並且會用到STL

**程式碼(C++)-hash table實作**

vector<vector<string>> groupAnagrams(vector<string>& strs) 
{
//排序後放入hashTable
unordered_map<string,vector<string>>    hashTable;
for(string s:strs)
{
    string temp=s;
    sort(temp.begin(),temp.end());
    hashTable[temp].push_back(s);
}
//取出放入ans
vector<vector<string>> ans;
for(auto keyValue:hashTable)
{
    ans.push_back(keyValue.second);
}
return ans;
}

:baby:: 接下來我使用剛剛的例子來進行測試

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

ans={{eat,tea,ate},{tan,nat},{bat}}

由ans和Output對照的結果是符合的，所以經過測試是沒問題的

:man:: 為甚麼你會採用這種方式實作，有甚麼優點嗎?

:baby:: 因為就題目敘述的話，同一個group的字串排序完是相同的，然後hashtable這種key和value的方式，就很適合當作此狀況的對應，而且hashtable的時間也蠻快的，加入的時間為O(1)

:man:: 所以總共的時間複雜度是多少

:baby:: 總共的時間會主要是這兩個for迴圈，上層的for迴圈是O(n``*``klogk)，下層的for迴圈是O(n)，所以時間複雜度為O(n``*``klogk)

for(string s:strs)    
{
    string temp=s;                
    sort(temp.begin(),temp.end());
    hashTable[temp].push_back(s);
}

for(auto keyValue:hashTable)
{
    ans.push_back(keyValue.second);
}

:man:: 那如果現在output要按照每個group的大小由小到大輸出，那要怎麼做?

:baby:: 我現在的想法會是把hashtable每個取出來放到一個暫存的地方，把每個group的長度取出，放到一個vector，作排序，在依照此長度對應的group把他還原

:man:: 你可以實作看看嗎

:baby:: 定義一個group的class，變數有長度和存放group的vector，依照每一個group在ans中的長度去排序

class group
{
	int   length; 
	vector stringGroup;
}

for(string s:ans)	
{
	for(string t:ans)	
    {
      	if(t.length<s.length)    swap(t,s);
    }
}

:man:: 好，那我們現在如果不用額外空間的話，時間複雜度最低可以多少

:baby:: 時間複雜度可以在針對sort的部份去優化，因為sort是排序字母，字母只有常數個，那麼counting sort在排序常數種情況下可以到O(n)，那這樣時間複雜度可以優化到O(n``*``k)

:man:: 好，謝謝你，我們今天面試就到這邊

## [1. Two Sum](https://leetcode.com/problems/two-sum/description/) >> [15. 3Sum](https://leetcode.com/problems/3sum/description/)

> interviewer:🥵 派中星-Patrick
> interviewee:😈 西格瑪-GigaChad
>
🥵: 我們要設計一個遊戲，遊戲中會出現很多數字，玩家要找到兩個數字和等於唯一解。
比如說唯一解是3，玩家選到2和1就會答對。
😈: 玩家直接選3可以嗎?
🥵: 不行，需要選兩個數字，你會怎麼設計這個演算法來判斷找出的解有沒有符合要求?
😈: 我的想法是先把全部數字排序，再掃描一次陣列就能找出唯一解。
例如說我排序完後有1 2 3 4 5 6 7 8 9，我就用1個指標i從頭開始掃描，1個指標j從尾開始
掃描。
若i+j>3，就代表右邊太大了要縮小一點，j要往左移；反之就是i要往右移。這樣最後一定
找到i+j=3。

1 2 3 4 5 6 7 8 9
i               j

😈: 我用c++來實作，先定義arr[n]，i=0，j=n-1。
**雙指標求數字和(two sum)**

//將arr排序
bubbleSort(arr);

//掃描陣列arr
while(arr[i]+arr[j]!=target){
    if(arr[i]+arr[j]>target)
        j--;
    else if(arr[i]+arr[j]<target)
        i++;
}
return arr[i], arr[j]

😈: 最後補上bubbleSort的程式碼。
掃描一次陣列花O(n)，用bubble sort做排序花O(nlogn)，總共的時間複雜度是O(nlogn)。
我還可以把bubble sort換成radix sort，這樣還可以讓程式的時間複雜度進一步降低。
🥵: 好，那現在有更進階的問題。遊戲設計成找到3個數字相加等於唯一解，且答案不只有一組。
這樣你會怎麼設計呢?
😈: 如果答案不只有一組，而且有相同數字，那我要回傳幾組答案呢?
例如唯一解是6，給定1 2 3 3，我要回傳兩次1 2 3嗎?
🥵: 只要回傳其中一組就可以，不用重複。
😈: 所以我的輸出結果會是一個2維陣列，並且陣列內的元素是3個數字，
3個相加起來會等於唯一解是嗎?
🥵: 對，收集所有的可能數字，相加起來會等於唯一解。
😈: 好，首先我一樣要把input array排序，再定義一個回傳的二維陣列。
作法和剛剛類似，以這個example為例。
我會先固定一個數字1，再看剩下的數字加起來能不能等於target-1。

**雙指標求數字和(three sum)**

//將arr排序
bubbleSort(arr);

//掃描陣列arr共n次，找出答案
for(int k=0; k<n-1; k++){    //O(n)
	i = k; j = n-1;
	while(i<j){	      //O(n)
        if(arr[i] + arr[j] > target-arr[k])
            j--;
        else if(arr[i] + arr[j] <   target-arr[k])
            i++;
        else {	
            tmp[0] = arr[k];
            tmp[1] = arr[i];
            tmp[2] = arr[j];
            sort(tmp[0] ,tmp[1], tmp[2])
            for(int l=0; l<=ansIndex; l++){ 
                if(ans[ansIndex][0]==tmp[0] && ans[ansIndex][1]==tmp[1] &&
                    ans[ansIndex][2] == tmp[2])
                    break;
                if(l==ansIndex){
                    ans[ansIndex][0] = tmp[0] ;
                    ans[ansIndex][1] = tmp[1];
                    ans[ansIndex][2] = tmp[2];
                    ansIndex+=1;
                }
            }
        }
    }
}
return ans;

😈: 如果現在掃描到3，就會要找target-3是嗎?
🥵: 是，不過我現在想到我可能會重複計算。
解決這問題一個很簡單的方式是: 在加入答案前先把3個數字排序，跟目前已知所有的答案相比，
確認沒有跟之前的答案重複，才能把3個數字加入答案中。
😈: 這個方式是很詳細，但是速度非常慢，請你描述一下要如何優化速度非常慢的問題。
🥵: 要優化的話，我想到的是在最開始時先把一些用不到的數字剔除。
😈: 你表達清楚，可以符合我們的需求，那我們今天就到這裡，後續會再通知你。

## 檢討自己至今的表現(派中星-Patrick)
第一次作業發現很多自己不太熟的部份，除了發現自己邊打程式邊講解會很卡之外，還發現自己說話也很不清楚，會碎碎念，表達的也不好，需要加強自己的表達能力。
刷完leetcode後總覺得好像已經會了，但之後說出自己的解題思維，才發現自己還沒有完全理解透徹，沒辦法很順的講解，找出很多不了解的部份，之後刷leetcode時，也需要再加上講出自己的解題思維，講出為甚麼用這個方法,整個架構的流程等等。

打程式的速度也不快，需要訓練。

第二次作業與另一位夥伴進行模擬面試，發現自己在臨場反應很不好，除了沒辦法很順利表達自己的想法外，問題卡住時，也沒辦法想清楚，要訓練自己在緊張時的穩定性

在上課時也發現自己的domain knowledge不足，在老師跟學員互動時，那些問題問我我好像也很難表達出來

## 檢討(西格瑪-GigaChad)
### 本次面試的表現
* 01:34 等面試官講完話再問問題，盡量不要打斷他。
* 42:03 不應該把程式碼完整地寫出來。
面試官只是問了我一個問題，我卻直接打了一大堆程式，讓面試官完全不想看。
要搞清楚面試官的要求。
* 01:01:13 面試官問我的問題可以在30秒內想到最優解。
比起用不好的解法蝦打一堆程式碼，不如扛下壓力，慢慢思考想出解答。
### 至今為止的表現
* 在寫程式前先列出程式結構(哪一段要做什麼)是個好方法，幫助面試官理解。
例如two sum的問題先列出//陣列排序和//雙指標掃描一次陣列。
若是在寫之前對程式結構不清楚，無法列出來，也要在寫完一段後補上註解，
大略說明這段在做什麼。
* 在REACTO的T時要確實帶入每行程式碼，不然會很容易有盲區。
* 相比第一次作業，我第二次講得更好。
因為我在說話之前會先花幾秒大略想過，比較不會講的斷斷續續且錯誤百出。
寧願沉默10秒思考後再講清楚，也不要一直無腦說話。
* 在面試官問問題的時候，多用example來弄清楚問題。
並且說example時也能有時間可以偷想解法。