# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 托爾-Thor
> ==[video1](https://www.youtube.com/watch?v=piYiC67LN0A)==,==[video2](https://www.youtube.com/watch?v=Md_AuglLdas)==, ==[video(英)](https://www.youtube.com/watch?v=XHDRnCmctvw)==
> 🧔：interviewer 👶：interviewee
## [268. Missing number](https://leetcode.com/problems/missing-number/)
> [模擬面試錄影](https://www.youtube.com/watch?v=piYiC67LN0A)
### 題目描述
給定一個陣列nums,有0到n,種共有n+1個數
同時給一個陣列裡面有n個數,找出缺少的那一個數(也就是missing number)
### 程式碼解說
- [ ] 方案一 : ***利用等差,相減,求出missing number***
```cpp
int numssum=0;
int numstotal = 0;
for(i=0;i<nums.size();i++){
//numssum=nussum+nums[i];
}
for(...){
//numstotal=totoalsum+i;
}
return numstotal-numssum;
```
- [ ] 方案一(較優的寫法) : ***利用高斯等差求和公式:n(n+1)/2***
```cpp
int missingnumber(vector<int>& nums){
int sum = 0;
int n=nums.size();
for(auto &a :nums){
sum+ =a;
}//nums累加
return n*(n+1)*0.5-sum;
}
```
- [ ] 方案二 : ***利用邏輯運算XOR特性求解***
XOR真值表
```cpp
int missingnumber(vector<int>& nums){
int res =0;
int n=nums.size();
for(int i=0;i<n;i++){
res ^=(i+1)^nums[i];
}
return res;
}
```
- [ ] 方案三 : ***index sort求解***
```cpp
int missingnumber(vector<int>& nums){
int n=nums.size();
nums.push_back(INT_MAX);
for(int i=0;i<=n;i++){
while(nums[i]!=i && nums[i]<=n){
swap(nums[i],nums[nums[i]]);
}
}
for(int i=0;i<=n;i++){
if(nums[i]!=i)
retur i;
}
}
```
## [9. Palindrome Number](https://leetcode.com/problems/palindrome-number/)
> [模擬面試錄影](https://www.youtube.com/watch?v=Md_AuglLdas)
### 題目描述
### 程式碼解說
- [ ] 方案一 : ***轉換為字串進行比對***
將整數 x 轉換為字串表示形式。
設定一個 for循環，從字串的開頭（索引 0）迭代到字串的中間（長度/2）。
在循環內，將目前位置的字元(number[i]) 與字串末尾對應位置的字元(number[length - i - 1])進行比較。
如果字元不符（即從中心向外不是回文數），則立即傳回false，表示不是回文數。
如果循環 完成後沒有發現任何不匹配（所有數字都匹配），則傳回true，表示該整數是回文。
```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;
}
```
- [ ] 方案二 : ***10進位反轉一半的數字***
以只反轉數字的後半部分，而不是反轉整個數字。這種方法很棘手，因為當我們反轉數字的後半部時，我們不希望中間的數字反轉回其原始值。如果數字的位數為奇數，就會發生這種情況。為了解決這個問題，我們可以將數字的前半部分與相反的後半部分進行比較。
解釋：
我們首先進行初步檢查以處理特殊情況：
在循環內部，我們x使用模運算子提取最後一位數字%，並將其乘以 10 後加到reversed變數中（將現有數字左移）。
// string = 1 2 3 2 1 reverse = 1
mod =1
然後我們除以x10 以刪除最後一位數字並將其移向數字的中心。
循環完成後，我們反轉了後半部的數字。現在，我們將數字的前半部 ( x) 與反轉的後半部 ( reversed) 進行比較，以確定數字是否為回文：
對於偶數位，如果x等於reversed，則該數字是回文數。我們回來了true。
對於奇數個數字，如果x等於reversed / 10（忽略中間數字），則該數字是回文數。我們回來了true。
如果以上條件都不滿足，則表示該數不是回文數，因此傳回false。
程式碼僅比較必要的部分，從而避免了反轉整個數字的需要。這種方法降低了時間複雜度和記憶體使用量，從而產生更有效的解決方案
```cpp
bool isPalindrome(int x) {
if (x < 0 || (x != 0 && x % 10 == 0)) {
return false;
}
int reversed = 0;
while (x > reversed) {
reversed = reversed * 10 + x % 10;
x /= 10;
}
return (x == reversed) || (x == reversed / 10);
}
```
### 對話內容
🧔:好的,托爾,那現在我們進到第二題
我將會給你整數x,想請你判斷是否為回文數,如果是的話回傳true,否則回傳false
而所謂的回文數也就是正著讀跟反著讀會是一樣的,這邊先舉幾個例子
👶：想請問x是否有範圍限制
🧔:有的,我們的x範圍界在-2^31 < X <(2 ^ 31) -1
👶：了解,那我這邊想到可以先將整數 x 轉換為字串表示形式
接著設定for循環從字串的開頭,也就是index為0開始每次都往後一格直到字串的中間(長度/2)的位置
並將目前位置的字元(number[i]),與字串對應位置的字元(number[length - i - 1])進行比較(舉例)
如果數值不同代表不為回文數,(return false)
若逐一比較後皆為相同的代表是回文數,回傳true
👶：(coding ...方案一 : 轉換為字串進行比對)
🧔:那是否可以不藉由轉換成字串的方式也能夠判斷是否為回文數呢??
👶：以整數的型態翻轉其中一半去跟另一半比較,如果一樣那就是回文數
因為無法使用字串的形式所以我想可以使用10進位的規則,如果對input的輸入數值每次都除以十並把餘數留存在進行,進位的排序就可以得到反轉的數值(舉例)
這邊可能得先排除掉幾種特例
首先第一種
avoid
1. x < 0 (x=-123)
reverse x=321-
2. x = 10*n倍 (x=10,20,30....
reverse x=01,02,03
👶：(coding ...方案二 : 10進位反轉一半的數字)
🧔:比較一下兩種方式的哪種比較好以及解釋原因
👶：值觀為第一種,但第二種較優(解釋原因...)
## [189. Rotate Array](https://leetcode.com/problems/rotate-array/)
> [模擬面試錄影](https://www.youtube.com/watch?v=XHDRnCmctvw)
### 題目描述
### 程式碼解說
- [ ] 方案一 : ***以矩陣存儲並使用for迴圈逐一走訪執行翻轉***
```cpp
void rotate(vector<int>& nums,int k){
vector<int> newArray =nums;
for(int i=0;i<nums.size();i++){
nums[(i+k)%nums.size()]=newArray[i];
}
}
```
- [ ] 方案二 : ***以reverse翻轉指定區域***
```cpp
void retate(vector<int>&nums ,int k ){
if (k> nums.size()) k% =nums.size();
reverse(nums.begin(),nums.end());
reverse(nums.begin(),nums.begin()+k);
reverse(nums.begin()+k,nums.end());
}
```
### 對話內容
🧔:hi torr I am todays interviewer
I well give you a question and we are going to discuss how to get the sloution
so if you are already that's getting started
🧔:In this question
first I well given an array.
rotate the array to the right by k steps where k is non-negative for example 1 2 3 4 5 6 7 and K is 3 the final output is 5 6 7 and then 1 2 3 4 because we rotate this array to the right by 3 staps so first rotate one step it becomes 7 1 2 3 4 5 6 because every single number moves towards the right by one step and the last number that on the very right end moves towards the beginning. so that where 7 moves becames to one position and then we continue to do this for the second step. then everything like 1 2 3 4 5 6 7 move towards the right .
so the 6 becomes to 7 position right? so we continue to do that. For the third time all of these move towards the right and then 5 well come to the first position that's how it end.
👶：ok,let me give an example to verify whether my understanding of this question is correct.
so for example,if input is [-1 -100 3 99] and K is 2
that means we rotate this array to the right by 2
so after rotate 2 stepts the output is [3 99 -1 -100] we just shift the array to the right repeate two times right?
🧔:yes
👶：ok,so I think the first we can use the brute-force , ues for loop to rotate every single element out of the n element towards the right one at a time and do this K times ,so the time complexity of that is going to be n times K,in this way not efficient to slove this problem,
to optimize this solution,I think we can
''use an extra array which means we can copy the entire original input array into the second array so basically we put we assign we can pre calculate every single element that should be rotated into its correct position as an extra array so that later on we can just basically copy the actual array into the original array so then every element in the original array is at its final rotated position how can we do that let's take a look at here so 1 2 3 4 5 6 7''
the i equals 0 is move to i equals 3
and i equals 1 is becomes to the index iequals 4
(coding ...)
🧔:sounds a good way ,but could you give me the way ,can reduce the space complexity is O(1)??
👶：let me think,...
the 2 way I well use reverse function to revers the array and restrict the range to reach the same answer
let me take the example
so the code is like (coding ...)
🧔:ok,good I think we are finish ,thank for coming this interview
### 面試過程初步自評
- [ ] 優點
* 再給出想到的做法實作程式碼前有先解釋自己的想法,並舉案例,較易於理解
- [ ] 缺點
* 面試官這個說詞可以改成另一個名稱取代,儘量不要有上對下的關係存在
* 錄製的音訊會有回音需要想辦法避免
* 英文口說需要加強,段句需要清楚,不然會聽不懂
* 可以更深入對演算法的時間複雜度和空間複雜度做討論
---
## 他評01
### interviewer
- [ ] 優點
* 咬字清楚
- [ ] 可改進的地方
* [1:00](https://youtu.be/piYiC67LN0A?feature=shared&t=62): 收音有嚴重的瑕疵
* 語速可以快一點點
* 英文部分文法與用詞有些許錯誤，口說不流利
### interviewee
- [ ] 優點
* 在提出方法與講解code時條理分明
- [ ] 可改進的地方
* REACTO缺少R
* 與interviewer互動可以更多
## 他評02
### interviewer
- [ ] 優點
* 口齒清晰
* 題目講解非常清楚
- [ ] 可改進的地方
* 前面感覺可以加入適當的自我介紹增加互動感
* 感覺題目可以加入情境
## interviewee
- [ ] 優點
* 改進的地方感覺出有用心
* 講解程式讓人非常好理解
* 有特別打註解
- [ ] 可改進的地方
* 感覺語速可以再快一點
## 他評03
### interviewer
- [ ] 優點
* 咬字清晰
* 除了講述題目，還有提供 input 和 output 範例、constraints、甚至是程式預期行為等
- [ ] 可改進的地方
* 避免稱呼自己為面試官，因為可能會讓 interviewee 感覺到君臨天下的感覺，進而緊張不敢跟 interviewer 互動
* 避免中英頻繁呼喚，例如用了英文說了 array 就可能不要再說集合，可能會讓人誤會成是不是 set 資料結構
* 要求 interviewee 提出更多解法的時候，可以用情境的方式提出，例如為什麼要使用其他的解法，是效率不夠好嗎或者是有什麼 constraint 導致別的解法比較好
## interviewee
- [ ] 優點
* REACTO 完整執行
* Approach 有用註解列出解法的 steps，interviewer 後面可以對照著看，以及 code 所代表的意思
* 有主動提出 naive 和比較有效率的解法
- [ ] 可改進的地方
* 避免使用 IDE 介面因為程式提示功能會讓畫面容易變得混亂，最好使用陽春的編輯器，例如 google docs，同時也可以練習自己在沒有提示功能的環境下撰寫程式
* 有些部分會自問自答，應該要切換成 interviewer 的畫面回答
Sign in with Wallet
Connect another wallet