---
tags: info2022-homework1
---
# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022)」作業 1
_貢獻者 : 秘客 Cypto_
> [模擬面試錄影(漢)](https://youtu.be/g2HdYJwS0oc)
> [模擬面試錄影(漢)](https://youtu.be/-5HsZK25XIs)
> [模擬面試錄影(英)](https://youtu.be/pt9NQrQoTyE)
:face_with_monocle: : Interviewer
:nerd_face: : Interviewee
## 9. Palindrome Number
### 測驗說明問與答
:face_with_monocle: : 那我想請你實作一個function，輸入是一個整數，回傳此整數是否符==回文==的規定。
:nerd_face: : 好的，所以我需要製作一個function，檢查輸入進來的整數是否頭尾對應的數字相同，如果對應數字都相同就代表是回文數值對嗎?
:face_with_monocle: : 是的。
:nerd_face: : 好，那舉例來說 : 121、2442 ，這些都是符合條件的數字，356，就是不符合回文的。
:nerd_face: : 那就我現在的觀察來說，因為要前後進行比對，所以我先把數字轉變成字串的型態，然後用兩個指標，一個從前面一個從後面，利用迴圈開始進行比對。
:nerd_face: :那我想請問一下題目是否有規定輸入述職的大小範圍。
:face_with_monocle: : 有的，介於 -2^32^ 跟 2^32^ 之間。
:nerd_face: : 好那我就開始進行實作。
```cpp
bool IsPalindrome(int x)
{
char alter[50];
sprintf(alter,"%d",x);
int front = 0 ;
int tail = strlen(alter)-1;
while(front<tail)
{
if (alter[front]!=alter[tail])
return false ;
front ++ ;
tail -- ;
}
return x ;
}
```
:face_with_monocle: : 那你是否有辦法不轉換成字串來進行判斷?
:nerd_face: : 好的，那我這邊的想法是先做出一個反轉過來的數字，再跟原本的數字去進行比對。
```cpp
bool IsPalindrome(int x)
{
int tmp=0;
if(x<0||(x%10 == 0 && x!=0))
return false;
while(x>tmp) {
tmp = tmp * 10 + x%10 ;
x = x/10;
}
if(x != tmp && (tmp/10 != x)) {
return false;
}
else return x;
}
```
:nerd_face: : 這邊就是我利用數值運算所做出的function，想請問對於我的方法有沒有什麼問題。
:face_with_monocle: : 沒有，第一題的面試就到這邊結束。
### 同儕檢討
- [00:03](https://youtu.be/g2HdYJwS0oc?t=3) 不要講第幾第幾道題目
- [00:26](https://youtu.be/g2HdYJwS0oc?t=26) 對稱的數字聽起來不是很直覺(以不知道回文的定義來說)到底是從中間切開用鏡子來看一樣(eg.151不是回文，101是回文)，還是真正回文的定義(151 和 101 都是回文)。
- [00:36](https://youtu.be/g2HdYJwS0oc?t=36) 這邊舉例就可以把上面那一點簡單的的說明一下。
- [01:33](https://youtu.be/g2HdYJwS0oc?t=93) char 宣告大小的取捨。
- [05:39](https://youtu.be/g2HdYJwS0oc?t=339) ```retrun x;``` 這裡沒有考慮到 0 這個整數的問題，會回傳 false 而不是 true 。
- [11:25](https://youtu.be/g2HdYJwS0oc?t=685) 跟上個一樣 ```return x;``` 沒有考慮到 0 的狀況。
- [12:29](https://youtu.be/g2HdYJwS0oc?t=749) 把```if(x<0||(x%10 == 0 && x!=0)) return false;``` 放到 ```int tmp = 0;``` 前面會比較好一點。
- [13:34](https://youtu.be/g2HdYJwS0oc?t=814) 最後面的 ```if``` 可以用以下寫法會比較簡潔。
```cpp
bool IsPalindrome(int x)
{
if(x<0||(x%10 == 0 && x!=0))
return false;
int tmp=0;
while(x > tmp) {
tmp = tmp * 10 + x%10 ;
x = x/10;
}
return x == tmp || x == tmp/10;
}
```
- [13:36](https://youtu.be/g2HdYJwS0oc?t=816) 是不是可以比較一下時間跟空間複雜度之於這兩種不同方法。
針對 interviwer 的檢討:
* 應該要稍微講解回文定義，interviweee才能夠更好理解題目。
* 應該要主動講出給定數值的範圍，這樣對於interviwer會比較好構思。
* 針對 follow-ups，可改為給定數值的二進位型態 (binary representation) 是否為 palindrome，這樣問題不僅更貼合現實應用場景，還能看出 interviewee 的程式設計基本功 (如 bitwise 運算)
針對 interviwee 的檢討:
* 在選擇利用字串進行處理時要考慮到空間複雜度的問題，如果字串設太大會有空間浪費
* 如果限制不能使用乘法和除法運算，那 bitwise 運算就是關鍵，可見以下實作:
```c
bool isPalindrome(int x)
{
if (x < 0) return false;
if (x == 0) return true;
int n = x;
unsigned rev = 0;
do {
unsigned q = (x >> 1) + (x >> 2);
q += q >> 4;
q += q >> 8;
q += q >> 16;
unsigned qq = q;
q >>= 3;
unsigned char rem = x - ((q << 1) + (qq & ~7UL));
if (rem > 9)
q++, rem -= 10;
rev = ((rev << 1) + (rev << 3)) + rem;
x = q;
} while (x);
return n == rev;
}
```
上方程式碼之改進如下：
```diff=
bool isPalindrome(int x)
{
if (x < 0) return false;
if (x == 0) return true;
int n = x;
unsigned rev = 0;
do {
unsigned q = (x >> 1) + (x >> 2);
q += q >> 4;
q += q >> 8;
q += q >> 16;
- unsigned qq = q;
q >>= 3;
- unsigned char rem = x - ((q << 1) + (qq & ~7UL));
+ unsigned char rem = x - ((q << 1) + (q << 3));
if (rem > 9)
q++, rem -= 10;
rev = ((rev << 1) + (rev << 3)) + rem;
x = q;
} while (x);
return n == rev;
}
```
* 第 13 行: q 得到的結果逼近 0.79999999981 倍的 x，約為 0.8x
* 第 15 行: q 除以 8 得到逼近 0.1x (x/10)
* 第 16 行: **`qq & ~7UL` 為將最右邊三個 bits 設為 0，相當於 `q << 3`**
* 第 17 行: x - (0.2x + 0.8x)，x - (x/10)*10 取得最後一個位數
* 第 18 行: 因為此計算方式是模擬除以 10，當 rem > 9 時，代表有誤差存在，q (商) 比預期少 1，故 q += 1、rem -= 10
* 以測資 INT_MAX (2147483647) 進行測試會發現 q 的誤差剛好是 1
* 在第 15 行新增以下程式碼印出 q 值
```c
printf("理想值: %d\n", x / 10);
(x / 10 != q) ? printf("計算值: %d<---不一樣\n\n", q) : printf("計算值: %d\n\n", q);
```
:::spoiler (點擊展開) 得到以下結果:
```
理想值: 214748364
計算值: 214748364
理想值: 21474836
計算值: 21474836
理想值: 2147483
計算值: 2147483
理想值: 214748
計算值: 214748
理想值: 21474
計算值: 21474
理想值: 2147
計算值: 2147
理想值: 214
計算值: 214
理想值: 21
計算值: 21
理想值: 2
計算值: 1<---不一樣
理想值: 0
計算值: 0
```
:::
* 第 20 行: rev = (2 \* rev + 8 \* rev ) + rem = 10 \* rev + rem
---
## 24. Swap Nodes in Pairs
### 測驗說明問與答
:face_with_monocle: : 第二個問題，給定一個linked list，請你寫出一個function將linked list裡面的每兩個node進行互換，且不能夠直接改變node裡面的value。
:nerd_face: : 好的，所以我需要把這個linked list裡面的node兩個為一組進行交換，且不能夠透過直接改值來完成。
:nerd_face: : 舉例來說[1,2,3,4]經過function交換過後應該會變為，[2,1,4,3]。
:nerd_face: : 我的想法是既然不能夠改值，那就是直接對linked list連接的位址去進行變動，利用迴圈兩兩一組進行改動下去。
```cpp
struct ListNode* swapPairs(struct ListNode* head){
struct ListNode *realhead,*current,*previous,*store ;
if(head->next != NULL)
realhead = head->next ;
else
return head;
current = head ;
previous = NULL;
while(current != NULL && current->next != NULL)
{
store = current->next->next ;
current->next->next = current ;
if(previous!=NULL)
previous->next = current->next ;
current->next = store ;
previous = current ;
current = store ;
}
return realhead ;
}
```
### 同儕檢討
- [01:00](https://youtu.be/-5HsZK25XIs?t=60) 我覺得這題的題目沒有敘述得很清楚，到底是 (1,2) 互換 (3,4) 互換還是 (1,2) 先換 (2,3) 再換...以此類推。所以我會問得更詳細一點。
- [03:51](https://youtu.be/-5HsZK25XIs?t=231) NULL 發音問題，而且```if(head->next != NULL)``` 這個部分，如果輸入值為```[]```的時候，會有存取空指標的錯誤產生。
針對 interviwer 的檢討:
* 不能直接改node值，應該要明說不能直接改node裡的value值會比較好。
針對 interviwee 的檢討:
* 在講程式中間的指標變換的時候可以把current等等標記在範例上，會比只用說的更好去理解。
---
## 21. Merge Two Sorted Lists
### 測驗說明問與答
:face_with_monocle: : Ok,next problem. You are given the heads of two sorted linked lists .
:face_with_monocle: : Please Merge the two linked list into one sorted linked list , and return the head of the merged linked list .
:nerd_face: : So i need to merge two linked list and keep the merged linked list be sorted .
:nerd_face: : For example , list1 = [1,3,5] 、 list2 = [2,4,6] , result = [1,2,3,4,5,6] .
:nerd_face: : My ideal is to compare this two's front node , and put the minimum node into new linked list untill all node is finish .
```cpp
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(list1 ==NULL)
return list2;
else if(list2 == NULL)
return list1;
struct ListNode *result ,*tmp ;
if(list1->val < list2->val)
{ result = list1;
list1 = list1->next ;
}
else
{
result = list2 ;
list2 = list2->next ;
}
tmp = result;
while(list1 != NULL && list2 !=NULL)
{
if(list1->val > list2->val)
{
tmp->next = list2;
list2 = list2->next ;
tmp = tmp->next;
tmp->next = NULL;
}
else
{
tmp->next = list1 ;
list1 = list1->next;
tmp = tmp->next ;
tmp->next = NULL;
}
}
if(list1 != NULL)
{
tmp ->next =list1;
}
else if (list2 != NULL)
{
tmp->next = list2;
}
return result;
}
```
針對 interviwer 的檢討:
* 應該要提供linked list的資料結構定義，interviwee會比較方便撰寫程式。
針對 interviwee 的檢討:
* 過程中可以利用範例講解可以讓程式更加易懂。
* 實作的程式碼過於冗長，請參見〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)〉提供的實作:
```c
struct ListNode *mergeTwoLists(struct ListNode *L1, struct ListNode *L2) {
struct ListNode *head = NULL, **ptr = &head, **node;
for (node = NULL; L1 && L2; *node = (*node)->next) {
node = (L1->val < L2->val) ? &L1: &L2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
```
簡潔又看得出實作技巧
Sign in with Wallet
Connect another wallet