# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS11ooE4Rh)」作業 2 #
My name：火箭-Raccoon
🧔：interviewer 🦝：interviewee
>[video](https://youtu.be/Zq3J2o5s7Dk)
- - -
## [118. Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/description/)
### 面試過程
🧔：你好火箭，我是xyz的軟體工程師，這次是由我來主持這場面試。請你稍微介紹自己的背景。
🦝：我是火箭，對數學和資訊工程領域有著深厚的熱忱，我想成為一個軟體工程師，因為它將我對數學的熱情與創建實際軟體產品的能力結合在一起。
🧔：哦！既然你對數學有興趣，我就跟你說一個關於數學的故事。
:::info
「有一個有趣的數學挑戰，古老的希臘數學家們曾經嘗試解答。他們試圖找到一種方式，通過逐行建構數字，使每一行的數字都是根據上一行的規則生成的。這種問題的關鍵是要找到一種有效的算法，以自動構建這個數字結構，無論它有多少行。」
:::
🧔：有人認為這個數學挑戰在現代科技和數據分析中有一定的應用價值。你是否願意試試看，看看你是否能夠建立一個程式，根據這個規則構建這種數字結構呢？
🦝：我先稍微理解一下剛剛的資訊，這個數學挑戰涉及到利用程式生成一個數字結構，並且該結構是根據上一行的數字生成的，我要找到一種有效的算法去自動建構這個數字結構。
🦝：請問我有理解錯誤嗎?
🧔：沒有，那麼你可以開始寫你的程式，請利用google document作答。
🦝：好的，那麼我先闡述我的做法，新的一行數字是根據上一行的規則生成，因此我先將第一行的數字初始化為1，從第二行開始照著同樣規則開始建構這個結構，由於有一個固定的規律，所以可以用遞迴法。
**遞迴法：**
🦝：稍微測試一下程式是否正確。
```
假設輸入n為5
n=5，generate(4)
n=4，generate(3)
n=3，generate(2)
n=2，generate(1)
n=1，return [[1]]
n=2，return [[1],[1,1]]
n=3，跑for迴圈一次，nowRows[1]=1+1=2
---> return[[1],[1,1],[1,2,1]]
n=4，跑for迴圈兩次，nowRows[1]=1+2=3、nowRows[2]=2+1=3
---> return[[1],[1,1],[1,2,1],[1,3,3,1]]
n=5，跑for迴圈三次，nowRows[1]=1+3=4、nowRows[2]=3+3=6、nowRows[3]=3+1=4
---> return[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
```
🧔：用遞迴的方法建構這個結構確實不錯，你能不能用其他方法來解決這個問題，尤其是用"數學方法"來做，畢竟這是一個數學挑戰。
🦝：嗯...(思考片刻)，我想到一種數學的方法叫做二項式定理，亦可以建構出這種有規律的結構，利用兩個for迴圈，外層跑要求的行數，內層則依照規則建構出每層的數字。
**二項式定理:**
🦝：稍微測試一下程式是否正確。
```
假設輸入n為4
i=0,j=1
---> result=[[1]]
i=1,j=1
---> result=[[1],[1,1]]
i=2,j=1 => row[1]=1+1=2
---> result=[[1],[1,1],[1,2,1]]
i=3,j=1 => row[1]=1+2=3
i=3,j=2 => row[2]=2+1=3
---> result=[[1],[1,1],[1,2,1],[1,3,3,1]]
i=4 達終止條件
```
🦝：和遞迴法的測試答案是一樣的，兩個方法的時間複雜度皆是***O($N^2$)***，空間複雜度亦是***O($N^2$)***。
🧔：不錯!確實是用"數學方法"來解決這個問題，那我想問你既然你都說時間複雜度及空間複雜度都是***O($N^2$)***，那你能夠改善你建構的方法，使得時間複雜度及空間複雜度之一或是兩者都得到改善嗎？
🦝：嗯...(思考片刻)，空間複雜度的部分，儲存結果的陣列如果用動態規劃來宣告，會縮減空間，但還是需要1+2+...+n個空間，大約等於$n^2/2$，因此空間複雜度為***O($N^2$)***，和直接宣告二維陣列所需要的空間相同。
🦝：至於時間複雜度的部分，我想亦沒辦法改善，因為建造這個數字結構必須要跑1+2+...+n次，大於總共是$n^2/2$，因此時間複雜度***O($N^2$)*** 也是無法避免的。
🧔：不錯，你將兩者都分析得很好，你應該很早就知道這種數字結構就是帕斯卡三角形，那你覺得可以應用在哪些實際方面？
🦝：主要可以應用在教育，因為涉及組合數學、概率等等，亦可以用在圖學中處理曲線，例如:貝茲曲線
🧔：不錯，我很喜歡你的表現，那今天的面試就到這邊，後續會再做相關通知。
- - -
## 第二次作業-評論他人(總和)
### interviewer
#### 優點
- 面試官都會大致上引導方向。
- 沒有直接稱自己是面試官。
- 講解題目很仔細
#### 可改進的地方
- 互動稍微少。
- 聲音有點小。
### interviewee
#### 優點
- 說話的語速剛好。
- 邊寫程式邊解釋自己正在寫的部分，視覺跟聽覺都有顧慮到。
- REACTO執行的很好。
- 利用畫圖來表達自己想法。
- 在對話的時候有利用手勢來讓人更加理解
#### 可改進的地方
- REACTO的部分可以做更好，即使題目很簡單。
- 聲音有點小，有些字會聽不太清楚。
- 英文發音怪怪的
- - -
## 從中學到什麼
- 如何更巧妙的對話，例如不會這道題目，要怎麼做才能夠委婉地講而不是單純的說 "我不會" 。
- 有些人有用不同的方法來表達自己的意思，例如畫圖及手勢，在線上面試的時候，圖像跟肢體動作可以很好表達自己。
- 當用一種方法寫出題目的時候，都要思考是否有其他的方法，雖然聽起來很基本，但是當題目很簡單的時候，常常就會忽略這種激盪思考的行為。
Sign in with Wallet
Connect another wallet