###### tags: `info2022-homework2`
# 2022 年 <a href = 'https://hackmd.io/@sysprog/info2022/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FBJLSJ3ggi'>「資訊科技產業專案設計」</a>作業二
# 啊啊啊-AAA Homework1 (漢)
## [283. Move Zeroes](https://leetcode.com/problems/move-zeroes/)
### Interviewer優/缺點
- [0:00](https://www.youtube.com/watch?v=OpluD2vgj1w) 首先，可以稍微介紹一下自己，不用這麼急著就開始，可以稍微介紹一下為甚麼要選擇這個題目，還有為甚麼這個題目重要。
另外就是，盡量不要把題目直接放在螢幕上，這樣如果給已經寫過這個題目的人來說，無疑是直接抄答案即可，也許Interviewer可以給圖片，或是其他可以幫助了解題目的東西。
- [0:10](https://www.youtube.com/watch?v=OpluD2vgj1w) Input 最後一個t 必須要發音
- [0:36](https://www.youtube.com/watch?v=OpluD2vgj1w) 在提出說明的時候，可以適時在document上面寫上自己剛剛舉的例子
- [0:46](https://www.youtube.com/watch?v=OpluD2vgj1w) 10的4次方可以改成說10000<一萬>就好。
- [1:00](https://www.youtube.com/watch?v=OpluD2vgj1w) 在討論到不能額外開出空間的時後，可以藉由專有名詞「in place」來帶入
### Interviewee優/缺點
- [1:39](https://www.youtube.com/watch?v=OpluD2vgj1w) 這邊有把例子寫出來，但先前的舉例我覺得應該是要給interviewer出才對。
- [2:04](https://www.youtube.com/watch?v=OpluD2vgj1w) 可以適度跟interviewer 提出In-place 的想法
- [09:55](https://www.youtube.com/watch?v=OpluD2vgj1w) 傳參照進來，好像沒有這種講法，應該要的講法為：傳位址進來
- [10:30](https://www.youtube.com/watch?v=OpluD2vgj1w) 在給予時間複雜度時，可以適度講一下是哪邊造就了這個時間複雜度，並且可以把時間複雜度一併打在程式碼附近
* [10:37](https://youtu.be/OpluD2vgj1w&t=719s) : 可提到為甚麼要move zeros 進而去討論他的時間複雜度以及空間複雜度。
## [120. Triangle](https://leetcode.com/problems/triangle/)
### Interviewer優/缺點
- [12:32](https://www.youtube.com/watch?v=OpluD2vgj1w) 可以解釋一下，到底為何需要尋找三角形的最佳路徑
- [17:00](https://www.youtube.com/watch?v=OpluD2vgj1w) 這邊直接講，把演算法做成程式的時候，我覺得interviewer可以稍微和面試者討論一下此做法的優缺點，而不是講直接請他做出來。
-
### Interviewee優/缺點
- [13:19](https://www.youtube.com/watch?v=OpluD2vgj1w) DP 又稱 Dynamic Programming 不要念成DB 不然這樣聽起來像是分貝 (db)
# 甘應化-Liver Homework1 (漢)
## [1. Two Sum](https://leetcode.com/problems/two-sum/)
### Interviewee 優/缺點
- [0:10](https://www.youtube.com/watch?v=aYB9eOhpXgY) 建議不要直接把原本的題目秀出來，試試看用自己的話講出來，就跟老師說的一樣，有時候秀出題目，沒有任何思考，會導致有一些人直接背答案。
- [4:47](https://www.youtube.com/watch?v=aYB9eOhpXgY) 在解釋時間複雜度的時候，可以在螢幕上面打字，告訴你的interviewer你的時間複雜度是多少。
- [5:22](https://www.youtube.com/watch?v=aYB9eOhpXgY) 同理，在解釋雜湊表的時候，如果沒有圖片解釋，或是例子直接打在上面的話，很難表達出到底要讓interviewer知道甚麼
- [6:00](https://www.youtube.com/watch?v=aYB9eOhpXgY) 一個大問題，把寫好的code移動至下方，如此一來，萬一面試官需要看你之前的works的話，不至於手忙腳亂，另外就是，不要刪掉已經寫好的東西。最後就是，可以在已經寫好部份code的狀況，直接把重點寫出來即可。
### Interviewer 優缺點
- [1:27](https://www.youtube.com/watch?v=aYB9eOhpXgY) 不要一直用滑鼠，可以試試看利用其他方法，比如使用小畫家的方式，可以更進一步的回答問題
# 亞拉岡-Aragorn Homework1 (漢)
## [136. Single Number](https://leetcode.com/problems/single-number/)
### Interviewee 優/缺點
- [00:00](https://www.youtube.com/watch?v=WMcbasFaqVo) 首先，不要用面試[官]，這樣有點給下馬威的感覺
- [03:33](https://www.youtube.com/watch?v=WMcbasFaqVo) 這邊做得非常清楚，美中不足的只有利用滑鼠表達會比較差而已，此時你已經有打出很多相對應的map了，為何不用鍵盤即可
- [08:50](https://www.youtube.com/watch?v=WMcbasFaqVo) 在解釋為甚麼要宣告整數時，打出的卻是迴圈，有點美中不足
### Interviewer 優/缺點
## [11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/)
### Interviewer 優/缺點
- [11:07](https://www.youtube.com/watch?v=WMcbasFaqVo) 10的五次方可以直接講十萬就好，這樣以文字上來講比較清晰
### Interviewee 優/缺點
- [13:27](https://www.youtube.com/watch?v=WMcbasFaqVo) 這邊解釋的非常不清楚，應該可以在文字上面顯示，而不是直接用比手畫腳的方式演給interviewee
# 肉古察-Low Good Homework 1
## 567. Permutation in String
### Interviewer 優/缺點
- [00:30](https://www.youtube.com/watch?v=ufz_Y_RoG1o) 首先，在介紹問題時，可以適時使用圖片或是自己手打example，否則面試者有時候因為完全沒有圖片支援，容易導致在這個區塊的時候就造成很多問題
- [03:26](https://www.youtube.com/watch?v=ufz_Y_RoG1o)interviewer 不應該要講出，這個題目我沒有想過這樣解，這樣對面試者來說，假設面試者很明顯知道這題的正解，那在面試結束之後只會顯得這間公司的interviewer對於這個題目的不熟悉，進而直接不選擇這間公司
### Interviewee 優/缺點
- [00:50](https://www.youtube.com/watch?v=ufz_Y_RoG1o) 在此時不知道為甚麼面試者有完整的題目，interviewer並沒有提起的，這樣有點讓人覺得好像要準備抄答案，而且題目一看就知道是leetcode上面搬下來的，這邊可能需要自己更改
- [04:15](https://www.youtube.com/watch?v=ufz_Y_RoG1o) 因為interviewer 剛剛講了不知道可以用bitwise 解題目，這樣有點導致立場對調。
- [07:50](https://www.youtube.com/watch?v=ufz_Y_RoG1o) 這邊只有講：counting sort 不是利用比較的方法排序，但我覺得這邊應該可以說：「counting sort 是一種利用list中數值特性去衍生的演算法，＜這邊講一下這題資料的特性＞，而這演算法可以在線性時間達成」 然後才接著說你可以怎麼實作演算法。
## 997. Find the Town Judge
### Interviewer 優/缺點
- [10:50](https://www.youtube.com/watch?v=ufz_Y_RoG1o) 你的面試都有一個特點，就是等到後面interviewee出現之後才會把題目放在上面，而不是從一開始interviewer就在上面打
### Interviewee 優/缺點
- [17:05](https://www.youtube.com/watch?v=ufz_Y_RoG1o) 在驗證程式碼的正確性的時候，需要打出例子，以及真實的數字，然後不要用滑鼠晃來晃去
## 136. Single Number (英文)
### Interviewer 優/缺點
### Interviewee 優/缺點
- [17:50](https://www.youtube.com/watch?v=ufz_Y_RoG1o) Language Filler 太多，導致我在聽的時候一直聽到 痾 痾 痾， 這對於英文面試來說是非常致命的
# 畝畸陡-Ivan Homework1 (漢&英)
## [Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/)
### Interviewer 優/缺點
- [0:00](https://www.youtube.com/watch?v=dEeR9h8-XEw) 不要用單聲道，很不舒服
- [0:00](https://www.youtube.com/watch?v=dEeR9h8-XEw) 老問題了，不要講自己是面試官
- [2:10](https://www.youtube.com/watch?v=dEeR9h8-XEw) Interviewer可以提出更多關於constrain 的要求，比如字串大小會多大，但是interviewee也沒有問，所以這邊是一個大敗筆
-
### Interviewee 優/缺點
- [1:19](https://www.youtube.com/watch?v=dEeR9h8-XEw) input 看起來明明像是一個list，其中有可能有不同長度的字串也有不同長度的list，Interviewee竟然沒有先詢問是不是只有像螢幕上一樣只有三個input，這點有非常大的瑕疵
- [2:56](https://www.youtube.com/watch?v=dEeR9h8-XEw) 下面一直有東西在跑來跑去，有點傷眼睛
- [8:36](https://www.youtube.com/watch?v=dEeR9h8-XEw) 明明time complexity 都已經打出來了，為甚麼不把space complexity 也一併打出來呢?
- [13:42](https://www.youtube.com/watch?v=dEeR9h8-XEw) 剪接好像出了一點問題，這邊interviewee 重複講了structure 兩次
- [18:21](https://www.youtube.com/watch?v=dEeR9h8-XEw) 明明前面正確的講出了 null 的音，為何這時候又變成了台灣的版本呢?
- [20:51](https://www.youtube.com/watch?v=dEeR9h8-XEw) 剪接又出問題了，這邊又重複了一次，我還以為我中了伊邪那美
-
## [Longest Mountain in Array](https://leetcode.com/problems/longest-mountain-in-array/)
### Interviewer 優/缺點
### Interviewee 優/缺點
- [26:23](https://www.youtube.com/watch?v=dEeR9h8-XEw) 這也是經典的sliding window 或是DP 的演算法，如果打從一開始就知道這個演算法，可以直接跟interviewer 講，跟他溝通為甚麼要這樣做，如此一來這題目就沒有一定要寫出來的必要了。再加上，在描述你的做法的時候並沒有提到approach是甚麼
-
# 評論心得以及學習心得：
==在評論別人時，總是可以看到自己哪裡做不好，以及別人正在做一件事情時，自己是不是也做了同樣的事情... 諸如此類的縮影。對於我來說，我覺得評論別人比自己錄影學到更多東西，尤其是在錄影的時候，自己先把講稿都大概想好，想要講甚麼事情都想好，但總是會缺乏了一些自己想要的東西。在看亞拉岡-Aragorn Homework1的時候，我看到了他對於面試的理解，不需要把整個code打出來也可以讓別人知道你對於code的理解程度很高。最重要的一點就是，利用鍵盤以及圖像的方法讓雙方都徹底理解想要做的事情是甚麼。==
==這次也讓我徹底理解面試的用意是甚麼，我覺得不是為了要讓別人知道你會打code，因為基本上大部分人都會，所以重點也在於你在面試時如何藉由慢慢地思考以及互相引導，去營造出最完美的面試氛圍，如此一來，雙方都可以知道彼此是值得信賴的人。==
# 自我錄影 ＜全新＞
## [136. Single Number](https://leetcode.com/problems/single-number/)
:8ball: interviewer , :baguette_bread: interviewee, :a: Narriator
對話：
:a: 來到我的面試，今天的面試設定在<藍寶> 要去面試一個伺服器工程師，廢話不多說，接下來就開始吧
:8ball: "哈囉，今天會是我來主持這場面試，讓我們公司同仁來了解一下你在程式開發上的想法以及風格吧！
我想你應該有對我們的職缺稍微了解一下吧，在我們公司需要對硬碟架構以及分割非常熟悉，接下來的題目也會跟此有關連"
:baguette_bread: 你好，我會嘗試全力以赴的。
:8ball: 好的，那我開始解釋今天的題目，今天我想要讓你找出一個陣列中重複的數字
:baguette_bread: 想要請教一下，找出重複的數字是甚麼意思呢?
:8ball: "我將會給定一個整數型態的陣列，而這個串列除了一個特定的數字只有出現一次之外，其他的數字都會剛剛好出現兩次
，而你的工作就是回傳那個陣列中沒有重複的那個數字"
:baguette_bread: 想要請問這個題目的陣列大小以及數字的範圍
:8ball: 陣列的大小會從一個元素到三萬個元素不等，而數字的值也會在正負三萬內
:baguette_bread: 好的，也就是說，當我看見了 [2] 的陣列，我只需要回傳 2 這個整數就好嗎?
:8ball: 沒有錯
:baguette_bread: 所以假設輸入為：[1,2,2,4,1,4,3] 我要回傳在這個陣列中沒有重複過的數值，也就是3對嗎?
:8ball: 沒有錯
:baguette_bread: 我想要請問一下，有沒有可能數字出現三次以上或是沒有單一的數字呢?另外想要請問可不可以更改陣列裡面的數值呢?
:8ball: 沒有這個機會，輸入一定會是和以上的格式一樣，然後你不可以更改陣列中的數值
:baguette_bread: "好的，那我開始介紹我的想法：
```
首先，我覺得可以建立一個雜湊表，先跑一個for 迴圈
1 2 2 4 1 4 3
^
建立出像是下面的表格
1 | 2
2 | 2
4 | 2
3 | 1
```
:baguette_bread: 接下來只需要重新跑過一次剛剛建立好的雜湊表，這樣就可以得到哪個數字只出現了一次，然後回傳那個數字即可
:8ball: 那你可以告訴我一下這個程式的時間複雜度以及空間複雜度嗎?能給出的數字越精準越好。
:baguette_bread: "好的，這個程式的時間複雜度為O( n + 0.5 * n) = O(n) 因為會剛剛好跑過陣列一次，緊接著繼續跑過一個最大為 floog(0.5 * n ) + 1 大小的陣列
最後才會把需要的值還給我們
而這個程式的空間複雜度也因為有一新增一個0.5 * n 大小的陣列，所以空間複雜度為Θ(0.5 * n) "
:8ball: 沒有問題，但是你這個程式不僅是空間還是時間都不是很好，我想要請問你有沒有更好的方法
:baguette_bread: 我想，如果要降低空間複雜度的話，其實可以試試看把這個陣列先做排序，然後每次找兩個數字，如果前後不一樣的話就回傳第一個數字
:8ball: 那你可以多講解一下你這個方法嗎?另外再跟我說說看他的時間複雜度以及空間複雜度
:baguette_bread: "好的，那假設用排序演算法，把剛剛的陣列 [1,2,2,4,1,4,3] 做排序，如此一來，陣列就會變成 [1,1,2,2,3,4,4]
接下來我們可以每次推進兩格，看看 a[i] 跟 a[i+1] 的元素是否相同，如果不一樣的話就直接回傳a[i]
那這個方法的時間複雜度因為被排序演算法的時間綁住，所以最快也只能到O(nlogn)的速度，雖然空間複雜度被降低了，但也因此而變慢許多"
:8ball: 你說的沒有錯，這程式還是有些許問題存在，其中最大的問題就是時間被拉大了。
:baguette_bread: "沒有錯，這個程式有很多問題，而我覺得這個題目的精隨就在於如何利用整數儲存的方法去進行xor比較，其中在
RAID-5 中，Parity disk 的設計就是利用xor 在數學上的特性來建構的"
:8ball: 沒有錯，Xor的數學特性非常好，請問他具體上有那裡可以使用在這題目上呢?
:baguette_bread: "XOR 他具有交換律以及結合律跟分配律，另外就是 0 和 a 進行xor的話，結果會是a，而a 和 a 進行xor 會得到0
也就是說，以這個題目的假設，所有的數字都出現剛剛好兩次，只有其中一個數字出現了一次
那假設這個陣列叫做a
其中我要找到 那個特定的數字，假設叫c"
:baguette_bread: "我們令 a 為 [a1, a2,a3,c,a5]
給定公式為 :
==f = a1 ⊕ a2 ⊕ a3 ⊕ c ⊕ a5==
而我們繼續假設 a1 = a2 且 a3 = a5， 那這個公式就可以利用交換律以及規一律把她重新寫成以下的公式
==(a1 ⊕ a2) ⊕ (a3 ⊕ a5) ⊕ c = 0 ⊕ 0 ⊕ c = c==
也就得到我們需要的結果"
:8ball: 利用xor的數學特性來解題非常好，那接下來能夠請你把程式實作出來嗎?
:baguette_bread:
```
int find(int* nums, int numsSize){
int result = nums[0];
for( int I = 1; I < numsSize; ++I){
result = result ^ nums[I];
}
return result;
}
```
:8ball: 非常好，想要請問你這個程式的時間複雜度以及空間複雜度各為多少，也是越精準越好
:baguette_bread: 那因為這個程式只會跑過一次這個陣列，所以這個程式的時間複雜度為Θ(n) 而空間複雜度也因為只有用到一個變數，所以為 Θ(1)
### Follow up [137. Single Number II](https://leetcode.com/problems/single-number-ii/)
:8ball: 沒錯，這也是答案的正解，那你想想看，當這個陣列中重複的元素變成三個時，你有沒有辦法利用剛剛那些想法做出來呢？
:baguette_bread: 請問你的意思是指原本重複兩個，這次變成三個嗎?
:8ball: 沒有錯
:baguette_bread: 限制都不變嗎?
:8ball: 不，這次陣列中數值的上下限變成 2的補數表示法的所有數。
:baguette_bread: "了解，讓我想一下。。。
我相信一開始提供的兩個解法，也就是雜湊表以及排序的方法都可以更改，這次好像不太是使用xor運算，我想要請問一下能不能夠給一點提示呢?"
:8ball: 好。你想想，2的補數表示法總共有幾個位元
:baguette_bread: 32個
:8ball: 也許你可以從這方面下手
:baguette_bread: "好的，讓我思考看看
啊！ 假設給定一個陣列如下：[2,2,2,5,5,5,4]
每一個整數的位元表示法為
```
2 --> 010
2 --> 010
2 --> 010
5 --> 101
5 --> 101
5 --> 101
4 --> 100
^^^
433
```
我們可以從位元的第一個位置開始看，如果那個數字是1的話，就讓local 變數 sum + 1，如果他不是三的倍數的話，那就代表那一個
位元是要被留下來的，也就是說那一個位元可以在給定的新的數字中存在，在這個例子當中，因為b3 有4個1，代表新的數字中b3
需要被設定為1，只要跑到最後，就可以知道數字為多少了
"
:8ball: 那你可以試試看把你的想法實作出來嗎?
:baguette_bread: "好的：
```
int singleNumber(int* nums, int numsSize){
int ans = 0;
for(int i=0;i<32;i++){
int sum =0;
for(int j=0;j<numsSize;j++){
if((nums[j] >> i) &1 == 1 ){
sum++;
sum %= 3;
}
}
if(sum != 0)
ans |= sum << i;
}
return ans;}
```
如此一來 這個程式的時間複雜度不管如何都會是 O(32 * n)"
:8ball: "這看起來還不錯，如此一來就可以利用bitwise operation 的方式找到沒有重複的數字，不過我想要修正一下剛剛你講不需要用到xor的地方，
其實這一題還是可以用到xor的運算，也許你想要想想看?"
:baguette_bread: 好的我試試…
:8ball: 抱歉我們今天的時間已經差不多了，希望你可以回去想想看如何多利用一種方法解這個問題，納今天到此為止吧，再見。
Sign in with Wallet
Connect another wallet