# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS11ooE4Rh)」作業 2
>[模擬面試影片(漢)](https://youtu.be/ElSse721QWM)
>🍔：interviewer 🍤：interviewee
## [287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)
🍔:你好，我是XXX公司的工程師，今天由我來主持這場面試。我們先簡單測試一下你的程式邏輯吧！架設現在有一場藝術品拍賣會，其中，最著名的一幅畫作被稱為「星空之夜」。
然而，在拍賣進行之前，藝術品專家們發現了一個問題。「星空之夜」畫作由於地下組織的干擾，出現了未知數量的複製品，唯一的區別是，這些畫作的拍賣編號相同。
為了確保拍賣的公平性和透明性，拍賣會需要一個方法來識別這些重複的拍賣編號。請問這種情況你會怎麼做呢？
***Repeat***
🍤:好的，您的意思是希望我找出這些編號中重複的編號，請問我的理解正確嗎？
🍔:是的，你的理解沒錯。
***Example***
🍤:好的，在我之前的工作中，我也解決過類似的問題，當時是有不少表單透過人工的方式蒐集，在歸檔的時候同樣出現了重複編號的錯誤。那麼接下來請讓我舉個例子來驗證我的理解是否符合您的需求，我先分享一下螢幕畫面，請稍等。假設現在有一個儲存編號的陣列，其內容是[3,1,3,4,2]，我必須要找出重複的那個編號，也就是3；如果陣列內容是[2,1,3,4,2,2]，我需要找出2。請問我的理解是否正確？
```python
[3,1,3,4,2] --> 3
[2,1,3,4,2,2] --> 2
```
🍔:是的，你的理解沒錯。
***Approach***
🍤:好的，我大致理解您的需求了。針對這種情況，我選擇使用2個迴圈:
- 外迴圈:使用i控制，依序遍歷整個陣列，array[i]是我們要檢查是否重複的目標
- 內迴圈:使用j控制，j會等於i+1，這樣就不會檢查自己以及檢查過的
🍔:了解，這個方法聽起來可行。
***Coding***
🍤:好的，那我就開始撰寫我的程式碼。我選擇使用Python撰寫。
```python
def findDuplicate(self, nums):
for i in range((len(nums))):
for j in range(i+1,len(nums)):
if nums[i]==nums[j]:
return nums[i]
return -1
```
***Test***
🍤:程式碼到這就完成了，時間複雜度是$O(n^2)$，空間複雜度是$O(1)$。那麼接下來我想測試這個程式的輸出。假設現在所有畫作的編號是[1,2,3,2]。
1. `i==0`, `num[i]==1`
- `j==1`, `num[j]==2`
- `j==2`, `num[j]==3`
- `j==3`, `num[j]==2`
>一開始i=0的時候，我們check的目標num[i]是`1`，接著進入內迴圈，j從i+1開始遍歷陣列，也就是`2,3,2`中是否存在`1`，而不會check自己。
2. 在check完`1`之後發現`1`沒有重複，i就會+1，使得當前check的目標變為`2`。
3. `i==1`, `num[i]==2`
- `j==2`, `num[j]==3`
- `j==3`, `num[j]==2`
>`num[i]==2`時會分別check剩下的陣列`3,2`中是否存在`2`，不會check自己也不會check已check過的`1`。`j==3`時發現`2`有重複，就會回傳`2`。
***Optimization***
🍔: 謝謝你，可行性看起來是沒問題的，但是我們這個拍賣會的商品非常多，這樣的程式碼效能明顯還有改進的空間。請問你能想出更好的解決方式嗎？
🍤:好的，我想到了另一種解法。當遍歷nums列表時，或許我可以將元素添加到字典中，如果發現已經存在，就可以立即返回該元素，而不需要進一步遍歷。
🍔:聽起來是個不錯的想法，那請你開始撰寫code吧!
🍤:
```python
def findDuplicate(self, nums):
dic = {}
for n in nums:
if n in dic:
return n
else:
dic[n] = 1
return -1
```
好的，一開始先宣告一個空的字典，接著遍歷整個陣列，如果當前數字有出現在字典key中，就回傳這個數字；否則就將這個數字作為是字典中的key，並賦值1。跟剛才一樣，如果都沒重複的數字就會return -1。
接下來讓我測試這個程式是否可行。
```python
[3,1,3,4,2]
3 : 1
1 : 1
3 : exist -->return
[1,2,3,2]
1 : 1
2 : 1
3 : 1
2 : exist -->return
```
## [442. Find All Duplicates in an Array](https://leetcode.com/problems/find-all-duplicates-in-an-array/)
🍔:好的，謝謝。那假設今天不只有一幅畫是複製品，很多畫作都會有複製品，而你必須將所有有重複的編號整理給我，你會怎麼做呢？
🍤:我認為會需要一個陣列來儲存所有重複的數字。我的想法是，在剛才的程式碼中檢查此數字是否已存在的地方使用append將此數字加入到這個陣列中，最後輸出這個陣列就可以了。
🍔:好，聽起來沒什麼問題，請開始coding吧!
🍤:
```python
def findDuplicates(self, nums):
dic = {}
ans=[]
for n in nums:
if n in dic:
ans.append(n)
else:
dic[n] = 1
return ans
```
🍤:程式這樣就完成了，現在我想測試這個程式碼結果。
```python
[4,3,2,7,8,2,3,1]
4 : 1
3 : 1
2 : 1
7 : 1
8 : 1
2 -->ans.append, ans[2]
3 -->ans.append, ans[2,3]
1 : 1
return ans --> output:[2,3]
```
🍔:好的，感謝你今天參與這場面試，面試結果後續我們會再用email通知，請留意信箱，謝謝!
---
## 互評心得
在評其他同學作業的時候，我給予的正面評價有口齒清晰，表達得很完整，有些同學甚至不需要字幕也能聽懂，然後做了很多我沒想到的方面，比如說會在優化後驗證、複雜度分析等等。改進空間的部分則是有英文容易有語法錯誤、沉默時間太長並給出可以說甚麼的建議、驗證過於瑣碎導致花費很多時以及標註出一些沒有講清楚的地方。
在觀看其他同學的錄製的影片時，我發現有些同學講解程式碼講得很清楚，我聽一次就能聽懂，也從中學到了沒有看過的題型的解題方法和思路。有些同學編寫程式邊說明仍然可以說得很明瞭，不怎麼停頓，我覺得這是我還需要加強的地方，因為我很常卡住然後為了不那麼安靜就會說一些沒有意義的語助詞，如「呃」、「對」、「嗯」……等等。然後其他同學有的英文說的很好很自然，但我就會很常不知道一些英文單字的發音，以及如何組織一個句子，需要用翻譯軟體才知道自己怎麼說才正確。因為平常跟別的同學接觸也不太常用到英文，感謝這個作業讓我有看到別人的機會、知道自己不足的地方。
而在這份作業中，我也同時可以看到別人給我的評價，讓我可以看到自己平常不會注意到的方面。尤其是當我看到別人給我的肯定時非常開心，可能是因為平常真的很少聽到這方面的誇獎吧！所以就算下面馬上就看到自己的缺點，也會十分的有信心自己在之後的作業可以將這些優點全部改進。我認為此次作業互評帶給我非常正面的影響~
## 第四次作業-他評01
### 優點
* 面試全程咬字清晰，表達清楚，超讚
* [5:24](https://youtu.be/ElSse721QWM?t=324) 測試方式非常詳細，逐步解說讓人容易理解
### 可改進的地方
* [7:58](https://youtu.be/ElSse721QWM) interviewer 可以明確點出目前程式碼的缺點，但不提供作法，這樣可以與 interviewee 有很多互動，但又不會過度引導 (e.g. 雙層迴圈看起來有許多冗餘的步驟，同一個元素通常要被拜訪很多遍，你是否能夠讓程式更有效率?)
* [13:53](https://youtu.be/ElSse721QWM?t=833) 針對多幅畫作複製品的解法有 bug，如果今天的 input 為`[4,3,2,7,8,2,3,1,2]`，output 應該要是`[2,3]`，但程式碼的 output 是 `[2,3,2]`
* **建議 1**: interviewer 要補充 「一幅畫只會有一個複製品這個條件」
* **建議 2**: interviewer 要找出 bug 並提醒 interviewee 改進
Sign in with Wallet
Connect another wallet