# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 竹間-Maggie
> [模擬面試影片(中+英)](https://www.youtube.com/watch?v=Il3nIsxQWTM&feature=youtu.be)
> 👨⚖️ : interviewer
> 👩 : interviewee
## [35. Search Insert Position](https://leetcode.com/problems/search-insert-position/)
> Simple
👨⚖️ :
你好，如果沒問題的話我們就開始這次的面試，我這邊有一道題目，題目是這樣的，給你一個已經排序過且升冪的數列，而且這個數列的每個數字都不相同，然後再給你一個目標數。如果目標數在此數列中，請回傳此數字的位置；但如果目標數不在數列中，請回傳目標數應該要插入的位置。
👩 :
***Repeat :***
所以是我會拿到一個陣列裡面存有升冪的數，另外還有一個目標數，我必須先確認此目標數有沒有在這個已知的數列中，若有，就回傳此數所在的陣列位置，若沒有，則回傳他應該安插在此數列的陣列位置，對嗎？
👨⚖️ :
是的沒有錯。
👩 :
***Examples :***
好的那我來舉個例子，假如我拿到
```
input: nums = [1,3,5,6], target = 5
Output: 2
```
若是target改成2，因為2介於1~3之間，所以要安插在1後面的位置，output就會是1，請問這樣理解是正確的嗎?
👨⚖️ :
是的。
👩 :
***Approach :***
好的，我會採取的作法是用count去計算位置，然後用一個for迴圈去把數列中每個數字都去跟目標數做比較，若是比對到一樣的數字就更新count並且離開迴圈，否則count+1，最後回傳count即為所求。
👨⚖️ :
OK，那你可以開始coding了。
👩 :
***Code :***
```cpp
int searchInsert(vector<int>& nums, int target) {
int count=0;
for(int i=0;i<nums.size();i++)
{
if(nums[i]<target){
count++;
}
if(nums[i]==target){
count=i;
break;
}
}
return count;
}
```
👩 :
***Test :***
舉例來說，若我今天有一個陣列是
```
1,3,5,6,8 target = 9
```
則我會需要跑完整個陣列才能得知target要放在最後一個位置，因為nums[4] < 9 ，所以count+1後變為5，而此時for也完全跑完跳出迴圈，得出所求為5。
👨⚖️ :
看起來是沒什麼問題，那現在希望你可以再進一步的優化時間複雜度，讓時間複雜度可以來到*O(log n)*。
👩 :
***Optimize :***
好的，目前的時間複雜度是*O(n)*，若要希望時間複雜度可以降到*O(log n)* 的話，我想到的是可以使用binary search 去搜尋此目標數，這樣用樹的結構來看的話，時間複雜度即會等同於樹的高度，就可以把時間降到*O(log n)*
👨⚖️ :
OK，那你可以開始coding了。
👩 :
***Code :***
```cpp
int searchInsert(vector<int>& nums, int target) {
int low=0,mid;
int high=nums.size();
if(target>nums[high-1]){
return high;
}
while(low<=high)
{
mid=(low+high)/2;
if(nums[mid]==target){
return mid;
}
if(target<nums[mid]){
high=mid-1;
}
else{
low=mid+1;
}
}
return low;
}
```
👩 :
以上為我的演算法實作後的code，請問這樣有符合你的要求嗎 ?
👨⚖️ :
看起來是可以，那我們進到下一題題目。
### 自評
針對 interviewer 的檢討 :
* 時間複雜度的專有名詞要講對 — big-O
* 回覆過於簡短，應該可以對interviewee提出多一些問題。
針對 interviewee 的檢討 :
* 語助詞太多（一直然後）
* 講話太緊張卡詞講錯
* 第二個程式碼沒有測試給interviewer看
* 鏡頭應該再往下一點並且照到一點身體的地方比較好
* 手機應該要關靜音
## [9. Palindrome Number](https://leetcode.com/problems/palindrome-number/)
> Simple
👨⚖️ :
那第二題題目敘述是這樣的，給你一個整數x，若x的形式是回文的話就回傳True，否則回傳False。
👩 :
***Repeat :***
所以我會拿到一個整數x，若前面看過去跟倒過來看都一樣的話，就回傳True對嗎?
👨⚖️ :
是的，而且這個x也可以是負數。
👩 :
***Examples :***
好的那我來舉個例子，假如我拿到
```
input: -121
Output: False
```
若是input改成正數的121，output就會是True，請問這樣理解是正確的嗎?
👨⚖️ :
是的。
👩 :
***Approach :***
好的，我會採取的作法是用一個while迴圈去跑x>0的情況，因為若x<0，那就一定不可能是回文，又若是x=0，就可以直接回傳True，所以在迴圈裡面只需要考慮x>0的狀況。然後我的想法是每一輪都將x的最後一位數去掉並加到新的變數reversed裡面，每一輪一開始將變數reversed乘以10，所以這樣加上來的x尾數就會是在變數reversed的尾數，直到我把x的每一個位數都跑過一遍即可跳出迴圈，然後若此變數reversed等於原本的input，就回傳True，否則回傳False。
👨⚖️ :
OK，那你可以開始coding了。
👩 :
***Code :***
```cpp
bool isPalindrome(int x) {
int num=x; //num用來暫存x
int reversed=0; //之後用來存取回文後的數
if(x<0){
return False; //如果是負數就不可能是回文
}
while(x!=0) //若x>0的話
{
reversed=reversed*10; //把reversed加一位數以存取x尾端的數
reversed=reversed+(x%10); //把x的最後一位數存取到reserved
x=x/10; //把x的最後一位數砍掉
}
if(reversed==num){
return True; //把x等於0也考慮進去了
}
return False;
}
```
👩 :
***Test :***
舉例來說，若我今天有一個x是121，進入迴圈之後，第一次迴圈完成時reversed會變1，x變12，第二次迴圈完成後reversed會變12，x變1，最後一次迴圈結束後reversed會變121，x變0，然後因為x=0所以會跳出迴圈，比對reversed等於num，所以回傳True。
👨⚖️ :
看起來是沒什麼問題，那現在希望你可以改用string來解這道題目，並且分析一下你的時間及空間複雜度。
👩 :
***Optimize :***
好的，若要希望用string來解題，因為字串是每個字元所組成的陣列，所以我需要先用to_string()函式去把每個數字存到陣列中，然後再用一個for迴圈來將頭尾相比對，若遇到不一樣的數即回傳False，反之若迴圈跑完皆一樣則回傳True。
👨⚖️ :
那你的時間以及空間複雜度呢?
👩 :
因為每個字元都會存入陣列中，所以我們會開一個跟字串一樣大小的陣列，所以空間複雜度是*O(n)*，又我們迴圈最多需要跑n/2個數，所以時間複雜度也是*O(n)*。
👨⚖️ :
OK，那你可以開始coding了。
👩 :
***Code :***
```cpp
bool isPalindrome(int x) {
string number=to_string(x) ;
int length=number.size() ;
for(int i=0; i < length/2; i++){
if(number[i] != number[length-i-1])
return false ;
}
return true;
}
```
👩 :
以上為我的演算法實作後的code，請問這樣有符合你的要求嗎 ?
👨⚖️ :
看起來是可以的，那我們進到下一題題目。
### 自評
針對 interviewer 的檢討:
* 盡量避免說"看起來是沒有問題"這種話，聽起來有點敷衍
針對 interviewee 的檢討:
* 說話的語速忽快忽慢的
* 說明想法的時候可以搭配動作會更加生動
* 有時會打code到一半忘記剛剛在講什麼，講解可以再流暢一點
* 不應該問面試官說"這樣對嗎?"
## [11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/)
> Medium
👨⚖️ :
Before moving on to the final question, I would like the rest of our conversation to be in English. Alright, let's begin with the third question.You are given an integer array height of length n. Just like this picture, there are n vertical lines drawn such that the two endpoints of the ith line on the coordinate plane are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store.
👩 :
***Repeat :***
So I'll be given an integer array height of length n. All I need to do is to find the maximum area that any two of the vertical lines create. Am I understanding the problem correctly?
👨⚖️ :
Yes,and notice that you are not allow to slant the container.
👩 :
***Examples :***
Ok,so base on this picture, the above vertical lines are represented by array [1, 8, 6, 2, 5, 4, 8, 3, 7]. In this case, the max area of water (blue section) the container can contain is 7*7,that is equivalent to 49. Am I understanding correctly?
```
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
```
👨⚖️ :
Yes. You can start to implement.
👩 :
***Code :***
```cpp
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int maxArea = 0;
int currentArea = 0;
while (left < right) {
currentArea = min(height[left], height[right]) * (right - left);
maxArea = max(maxArea, currentArea);
if (height[left] < height[right]) {
left++;
}
else {
right--;
}
}
return maxArea;
}
```
👩 :
This is my program. Could you have any concern ?
👨⚖️ :
I think this is the good method, Thank you and the interview for today concludes here. Bye~
### 自評
針對 interviewer 的檢討:
* 英語口說待加強
* 有些專有名詞英文會念錯
* 應該要針對某些面試者講解不清楚的地方追問
針對 interviewee 的檢討:
* 英語口說待加強
* 沒有說明程式測試的部分
* 邊講話邊打字太慢，空拍太多
* 是 my ans 而不是 our ans
---
## 第二次作業-他評01
### interviewer
- [ ] 優點
* 會去引導interviewee對程式做優化
- [ ] 可改進的地方
* interviewer可以將公司遇到的問題帶入題目來敘述會更好
* 考驗其他做法時應該先描述更改後會帶來的結果
### interviewee
- [ ] 優點
* REACTO的部分都有cover到
- [ ] 可改進的地方
* 盡量避免重複的語助詞(e.g.,然後)的出現，以增進通順度
* approach的講解應該可以更詳細
## 第二次作業-他評02
### interviewer
- [ ] 優點
* 流程清晰，且三題連貫
- [ ] 可改進的地方
* 建議以情境題帶入題目，也可以跟面試者討論題目進而引導出想要解決的問題
* 雙向溝通的占比比較少，建議多加一些互動
### interviewee
- [ ] 優點
* 一步一步地講解程式碼，可以讓面試官帶入思考面試者的想法
* REACTO都有涵蓋在裡面並且流程明確
- [ ] 可改進的地方
* 如果可以，建議討論時間複雜度與空間複雜度之間的比較與取捨，並與面試官溝通是要使用哪一種導向的演算法進行實作
* 建議在撰寫程式碼時減少中間沉默的時間，在這期間可以嘗試與面試官互動或者重複表達你的想法，讓注意力不容易散掉
* 建議在理解題目時多詢問題目變數的限制與範圍，這樣可以多將一些邊界條件納入思考
## 第二次作業-他評03:
### Interviewer
- [ ] 優點
* 流程清晰
* 會一步一步引導Interviewee
- [ ] 可改進的地方
* 聲音有點小聲，可以再大聲一點
### Interviewee
- [ ] 優點
* 三題連貫剪在一起
* 有把REACTO執行的很好
* 程式解釋清楚
- [ ] 可改進的地方
* 旁邊的廣告可以關閉，不然廣告一直動會不自覺的受影響
* [24:12](https://youtu.be/Il3nIsxQWTM?si=grWS6faK-TxFceEn&t=24m12s): 對比前面中文部份都會有比較長一段的沉默
## 第二次作業-他評04:
### interviewer
- [ ] 優點
* 表達清楚
* 有適時的引導interviewee
- [ ] 可改進的地方:
* 在講述題目時，可以把題目包裝成另一情境，否則會出現背答案導致鑑別度不足，也可以考驗interviewee的理解能力和應變能力。
### interviewee
- [ ] 優點:
* 有完整使用REACTO的步驟
* 解釋做法時很清楚
* 有邊寫程式邊講解
- [ ] 可改善的地方
* 避免過多的冗詞贅字
* 在講解時可搭配多一點肢體語言，讓整個過程不會太過死板。
* 打字速度可以再加快
## 第二次作業-他評05:
### interviewer
- [ ] 優點:
* 面試官友善的引導
- [ ] 可改進的地方:
* 聲音有點小
### interviewee
- [ ] 優點:
* REACTO 執行的很好
* 邊寫程式邊講解
- [ ] 可改善的地方:
* 有些地方聲音有點小，字會聽不太清楚
## 第二次作業-他評06:
### interviewer
- [ ] 優點:
* 題目描述的很清楚
- [ ] 可改進的地方:
* 可以將題目做一些包裝，讓面試者去思考怎麼將包裝過後的問題，簡化成為包裝前的樣子
### interviewee
- [ ] 優點:
* 在面試官的引導下提出了更好的做法
* REACTO有徹底的執行
- [ ] 可改善的地方:
* 音量的部分可以更一致
Sign in with Wallet
Connect another wallet