2022 年「資訊科技產業專案設計」作業 1

貢獻者 : 秘客 Cypto

模擬面試錄影(漢)
模擬面試錄影(漢)
模擬面試錄影(英)

: Interviewer
: Interviewee

9. Palindrome Number

測驗說明問與答

: 那我想請你實作一個function，輸入是一個整數，回傳此整數是否符回文的規定。
: 好的，所以我需要製作一個function，檢查輸入進來的整數是否頭尾對應的數字相同，如果對應數字都相同就代表是回文數值對嗎?
: 是的。
: 好，那舉例來說 : 121、2442 ，這些都是符合條件的數字，356，就是不符合回文的。
: 那就我現在的觀察來說，因為要前後進行比對，所以我先把數字轉變成字串的型態，然後用兩個指標，一個從前面一個從後面，利用迴圈開始進行比對。
:那我想請問一下題目是否有規定輸入述職的大小範圍。
: 有的，介於 -2³² 跟 2³² 之間。
: 好那我就開始進行實作。

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 ;
}

: 那你是否有辦法不轉換成字串來進行判斷?

: 好的，那我這邊的想法是先做出一個反轉過來的數字，再跟原本的數字去進行比對。

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;
}

: 這邊就是我利用數值運算所做出的function，想請問對於我的方法有沒有什麼問題。
: 沒有，第一題的面試就到這邊結束。

同儕檢討

• 00:03 不要講第幾第幾道題目
• 00:26 對稱的數字聽起來不是很直覺(以不知道回文的定義來說)到底是從中間切開用鏡子來看一樣(eg.151不是回文，101是回文)，還是真正回文的定義(151 和 101 都是回文)。
• 00:36 這邊舉例就可以把上面那一點簡單的的說明一下。
• 01:33 char 宣告大小的取捨。
• 05:39 retrun x; 這裡沒有考慮到 0 這個整數的問題，會回傳 false 而不是 true 。
• 11:25 跟上個一樣 return x; 沒有考慮到 0 的狀況。
• 12:29 把if(x<0||(x%10 == 0 && x!=0)) return false; 放到 int tmp = 0; 前面會比較好一點。
• 13:34 最後面的 if 可以用以下寫法會比較簡潔。

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 是不是可以比較一下時間跟空間複雜度之於這兩種不同方法。

針對 interviwer 的檢討:

• 應該要稍微講解回文定義，interviweee才能夠更好理解題目。
• 應該要主動講出給定數值的範圍，這樣對於interviwer會比較好構思。
• 針對 follow-ups，可改為給定數值的二進位型態 (binary representation) 是否為 palindrome，這樣問題不僅更貼合現實應用場景，還能看出 interviewee 的程式設計基本功 (如 bitwise 運算)

針對 interviwee 的檢討:

• 在選擇利用字串進行處理時要考慮到空間複雜度的問題，如果字串設太大會有空間浪費
• 如果限制不能使用乘法和除法運算，那 bitwise 運算就是關鍵，可見以下實作:

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;
}

上方程式碼之改進如下：

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 值
      ​​​​​​​​​​​​printf("理想值: %d\n",   x / 10);
      ​​​​​​​​​​​​(x / 10 != q) ? printf("計算值: %d<---不一樣\n\n", q) : printf("計算值: %d\n\n", q);
      

      (點擊展開) 得到以下結果:

      ​​​​​​​​​​​​理想值: 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

測驗說明問與答

: 第二個問題，給定一個linked list，請你寫出一個function將linked list裡面的每兩個node進行互換，且不能夠直接改變node裡面的value。
: 好的，所以我需要把這個linked list裡面的node兩個為一組進行交換，且不能夠透過直接改值來完成。
: 舉例來說[1,2,3,4]經過function交換過後應該會變為，[2,1,4,3]。
: 我的想法是既然不能夠改值，那就是直接對linked list連接的位址去進行變動，利用迴圈兩兩一組進行改動下去。

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 我覺得這題的題目沒有敘述得很清楚，到底是 (1,2) 互換 (3,4) 互換還是 (1,2) 先換 (2,3) 再換…以此類推。所以我會問得更詳細一點。
• 03:51 NULL 發音問題，而且if(head->next != NULL) 這個部分，如果輸入值為[]的時候，會有存取空指標的錯誤產生。

針對 interviwer 的檢討:

• 不能直接改node值，應該要明說不能直接改node裡的value值會比較好。

針對 interviwee 的檢討:

• 在講程式中間的指標變換的時候可以把current等等標記在範例上，會比只用說的更好去理解。

---

21. Merge Two Sorted Lists

測驗說明問與答

: Ok,next problem. You are given the heads of two sorted linked lists .
: Please Merge the two linked list into one sorted linked list , and return the head of the merged linked list .

: So i need to merge two linked list and keep the merged linked list be sorted .
: For example , list1 = [1,3,5] 、 list2 = [2,4,6] , result = [1,2,3,4,5,6] .
: My ideal is to compare this two's front node , and put the minimum node into new linked list untill all node is finish .

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 和非連續記憶體〉提供的實作:
  ​​​​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;
  ​​​​}
  

  簡潔又看得出實作技巧