# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者：火箭-Raccoon
> 🧔‍：interviewer
> 🦝：interviewee
>
> [錄影: 漢語](https://www.youtube.com/watch?v=Rbvoz5JheGc) - 34.Find first and last position of element in sorted array.
> [錄影: 漢語](https://www.youtube.com/watch?v=7Atfr12kwtk) - 141.Linked list cycle.
> [錄影: 英語](https://www.youtube.com/watch?v=mpWFVjCKZmo) - 70.Climb stairs.

## [34. Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/)
### 面試過程
🧔‍：你好火箭，我是xyz的工程師，我這裡有一道題目，敘述如下，給你一個已經從小排序到大的整數陣列以及一個變數target，你要在這個陣列當中找出target最先出現以及最後出現的位置，如果targe不存在於這個陣列當中，便要回傳[-1,-1]。

🦝：我先理解一遍，一開始我會拿到一個已經從小排序到大的整數陣列以及一個變數target，我需要在陣列中尋找target最先出現以及最後出現的位置，如果target不存在陣列當中便回傳[-1,-1]，請問我有理解錯誤嗎?

🧔‍：沒有，還有其他問題嗎?

🦝：為了更加確認我對題目的理解，這裡我舉幾個例子

1. array=[5,7,7,8,8,10], target=8，則我要輸出[3,4]。
2. array=[5,7,7,8,8,10], target=5，則我要輸出[0,0]。
3. array=[5,7,7,8,8,10], target=17，則我要輸出[-1,-1]。

🦝：請問我有理解錯題目嗎?

🧔‍：沒有，那麼請你利用google document作答。

🦝：好的，那我先闡述我的做法，最直觀的寫法我會用暴力法解決，一開始先把要找的兩個位置變數值都設為-1,再利用for迴圈從頭到尾檢查一遍，如果有找到target值再去更改位置變數的值。

**暴力法：**

🦝：稍微做個測試。
* array=[2,3,4,5,5,5,11]，target=5。
...
當i=3時，pos1=3,pos2=3
當i=4時，pos2=4
當i=5時，pos2=5
...
最終得到[3,5]。

🧔‍：用暴力法的確可以解決，不過你的程式的時間複雜度是***O(N)***，你能否將時間複雜度降成***O(logN)***?

🦝：恩...(過了一會)，因為已經排序好了，所以我可以用binary search來檢查，會先用binary search找出左半邊變數target最先出現的位置，再用一次binary search找出右半邊變數target最後出現的位置，這樣在搜尋的時間複雜度就變成***O(logN)***。

**二元搜尋法：**

🧔‍：不錯，那今天的面試就到這邊，後續會再做相關通知。

## [141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/description/)
### 面試過程
🧔‍：你好火箭，這次的題目如下，給你一個Linked list的開頭head,我們要確認這個Linked list 是否有 Linked list cycle，cycle的定義為Linked list當中有一點可以回到之前的位置，這個位置我們用變數pos表示，但是題目並不會給你pos的值，pos=-1表示不存在cycle，Linked list的長度大於0小於10000，元素的值則在+-10^5內。

🦝：我先理解一遍題目，輸入為一個Linked list的head，回傳值為布林值，也就是是否有cycle存在於Linked list當中，這裡我舉幾個例子當作範例，以驗證我的理解。

1. head=[3,2,0,-4], pos=1，則要回傳true。
2. head=[7,5,8], pos=-1，則要回傳false。

🦝：請問我有理解錯題目嗎?

🧔‍：沒有，那麼請你利用google document作答。

🦝：好的，那我先闡述我的做法，我會使用兩個指標去搜尋是否有cycle，其中一個跑比較快，一個比較慢，當較快的指標跟較慢的指標相等時，便能得知有cycle。

**快慢指標：**

🦝：稍微做個測試。

* head=[4,5,6,8,9,2,7], pos=3
1.slow=4,fast=4
2.slow=5,fast=6
3.slow=6,fast=9
4.slow=8,fast=7
5.slow=9,fast=9
=>有cycle存在，回傳true。
* head=[4,5,6,8,9], pos=-1
1.slow=4,fast=4
2.slow=5,fast=6
3.slow=6,fast=9
4.slow=8,fast=nullptr
=>沒有cycle存在，回傳false。

🦝：因為一定要跑完整個Linked list才知道是否有cycle，時間複雜度就會是***O(N)***。

🧔‍：想問你還有別種解決方法嗎?

🦝：恩...(一會兒)，可以利用hash table來儲存已經拜訪過的點，如果有linked list cycle則會經過已經拜訪過的點。

***Hash table***

🦝：利用hash table的時間複雜度一樣是***O(N)***，但是以空間複雜度來看，快慢指標的空間複雜度為***O(1)***，而hash table的空間複雜度為***O(N)***，因為需要存N個值。

🧔‍：不錯，那今天的面試就到這邊，後續會再做相關通知。

## [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/description/)
### 面試過程
🧔‍：Hello! Raccoon, The problem is a classic one, often referred to as the "climbing stairs" problem. Given an integer n, where you can only climb either one or two steps at a time, you need to return the number of distinct ways to climb n steps of stairs. The value of n falls in the range [1, 45].

🦝：I'll first understand the question, the input is a value 'n' and the task is to return the total number of methods. Here, I'll provide a few examples to verify my understanding.

1. n=0 =>回傳 1
2. n=3 =>回傳 3
3. n=4 =>回傳 5

🦝：Have I misunderstood the question?

🧔‍：No, please use Google Documents for your response。

🦝：Okay, let me explain my approach. The most straightforward idea I have is to use an iterative method. I would use a for loop to find the required 'n' value and rely on a vector to store the number of methods before the 'n' value.

**Iterative：**

🦝：Let's run a quick test.

* n=4
1.ans[4]=ans[3]+ans[2]
2.ans[4]=ans[2]+ans[1]+ans[1]+ans[0]
3.ans[4]=ans[1]+ans[0]+ans[1]+ans[1]+ans[0]=5

🧔‍：Can you solve this problem using a recursive approach

🦝：Yes, the recursive approach may appear shorter when visualized.

**Recursive：**

🧔‍：Sure, can you provide a brief analysis of the time complexity?"

🦝：From a recursive perspective, the time complexity would be $O(2^N)$, while from an iterative standpoint, the time complexity would be $O(N)$. However, the iterative approach would incur an additional $O(N)$ space complexity.

🧔‍：Oh, can you find a way to reduce the space complexity?

🦝：Sure...(after a moment), you can use just two variables for iterative storage of the 'n' values. Since we only need to return the number of ways to climb 'n' stairs in the end, there's no need to store all the methods for values less than 'n' in an array.

**Iterative (space optimization).：**

🦝：In this way, the space complexity can be reduced to $O(1)$.

🧔‍：Great, the interview for today ends here. We will inform you about any further updates in the future.

## 初步(自我)檢討
* 避免直接給題目和講關鍵字，多用故事去包裝題目。
* 影片的剪輯把太多的留白剪掉，整個感覺很像背答案。
* 面試官的問題有點少，應該多點互動，感覺很像面試官很笨。
* 英文的發音不夠清楚，收音亦是一個問題。
* ...(還在想)

---

## 第二次作業-他評01:
### interviewer
- [ ] 優點
* interviewer比較沒有表現到，不太好提出

- [ ] 可改進
* 第一題前面，interviewer接話太快了，聽起來怪怪的
* 和interviewee互動較少

### interviewee
- [ ] 優點
* 咬字太清楚害我以為是電腦配音
* REACTO 有做到
* 程式解釋清楚

## 第二次作業-他評02:
### Interviewer
- [ ] 優點
- Interviewer話有點少的，也許可以讓面試官試著加入質疑的地方。
- 第二部 [0:35](https://youtu.be/7Atfr12kwtk?si=H4VBBYylUhAV3EhY&t=35): 也許不要直接把完整題目貼出來，可以口頭告訴，這樣也方便讓interviewee問問題，以此增加互動。

- [ ]可改進的地方
* [2:28](https://youtu.be/Rbvoz5JheGc?si=868Lm_Hvnc9_hxzN&t=149): interviewer若不想要interviewee執行暴力法，應發出質疑，或是打斷interviewee。
* [7:05](https://youtu.be/Rbvoz5JheGc?si=AoBwJsIZMkzDoCFt&t=425): 也許應該詢問interviewee時間複雜度，而不是interviewer來回答
* [10:59](https://youtu.be/Rbvoz5JheGc?si=it5e5cLXrhdMEWWk&t=659): 也許起始點不用初始化為0?，可以要求interviewee不為0開始。
* [第二題](https://www.youtube.com/watch?v=7Atfr12kwtk)也許可以思考一下如何包裝題目，但我也不太知道有甚麼情形會出現這種情況，可能是檢查資料毀損，或是錯誤之類的? 這我不確定XD

### Interviewee
- [ ] 優點
* 講話很清楚
* 有確實執行REACTO

- [ ] 可改進的地方
- [2:30](https://youtu.be/Rbvoz5JheGc?si=aS8HOh1MFXNRPhbk&t=150): 可以問Interviewer是否能用C++。經老師過往的評論，可以詢問面試官要使用的程式語言，是否可以使用STL。
- [8:02](https://youtu.be/Rbvoz5JheGc?si=0mnsADUefaSAS1uK&t=482): 這邊其實可以提到Binary search應該要稍微提到Mid的搜尋結果，中間有可能砍半後就遇到了，但必須要確保是最左側或是最右側的Target。

## 第二次作業-他評03:
### Interviewer
- [ ] 優點
* 口條清晰

- [ ] 可改進的地方
* interviewer可以跟interviewee有更多的互動
* interviewer接話可以先稍微停頓一下

### Interviewee
- [ ] 優點
* 有把REACTO執行的很清楚
* 口條清晰，每個地方都解釋蠻清楚

- [ ] 可改進的地方
* 整個影片看下來，interviewee都解釋的很詳細，也徹底執行REACTO覺得沒特別需要挑剔的地方

## 第二次作業-他評04:
### Interviewer
- [ ] 優點
* 口齒清晰
- [ ] 可改進的地方
* 說話太過字正腔圓，陰陽頓挫和日常說話習慣有差距，聽起來不太自然，讓人懷疑是否在唸稿
* 較少與面試者互動，應該與面試者有更多溝通
* 如果可以針對題目有更多延伸的問題或是真實情境的描述會更好

### Interviewee
- [ ] 優點
* 解釋非常詳細清楚，尤其是在程式碼撰寫時的講解比很多人都清楚很多
* 有活用 REACTO 框架，每個環節都有確實做到
- [ ] 可改進的地方
* 說話太過字正腔圓，陰陽頓挫和日常說話習慣有差距，聽起來不太自然，讓人懷疑是否在唸稿
* [2:11](https://youtu.be/mpWFVjCKZmo?si=0pWRMzLlxnJC-p4Q&t=131) 面試者在這邊說「I will declare the **vector space** ...」，或許改講 vector size 會比較好
* [2:48](https://youtu.be/mpWFVjCKZmo?si=FYeOPPPTf9pELNhd&t=168) 面試者在這邊說「**The end condition** is i <= n ...」應該不太對，for loop 小括號裡面的第二個 statement 放的是繼續的條件而非終止條件
*
## 第二次作業-他評05:
### Interviewer
- [ ] 優點
* 題目的講解很清楚
- [ ] 可改進的地方
* 針對複雜度的分析可以去細問，以確認interviewee 是不是只是單純寫過而背過時空間複雜度

### Interviewee
- [ ] 優點
* 暴力解跟最佳解都有明確寫出跟講解。尤其是暴力解有稍微在最後聊一下解法
* 快慢指標跟Hashmap方法的複雜度都有提出解釋，而且還比較各自優缺點
- [ ] 可改進的地方
- 可以透過畫圖來強化解題的思路