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

貢獻者: 美生菜-Murphy
🧔：interviewer
👶：interviewee

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

9. Palindrome Number

面試過程

🧔：第一題呢我會給你一個整數那你要去判斷這個整數是否為palindrome，也就是迴文，那如果判斷為是的話回傳一個True，反之的話就回傳false，那你先試試看
👶：好的那在這邊判斷的方式，我會先將這個數字轉換成字串，並且利用for迴圈，去比對第一個數字與最後一個數字是否相同，以此類推，來判定這個數字是否為迴文

bool isPalindrome(int x){
    char str[20];
    sprintf(str, "%d", x);
    int lenth = strlen(str);
    for(int i = 0; i < lenth / 2; i++){
        if(str[i] != str[lenth-i-1]) {
            return false;
        }
    }
    return true;
}

88. Merge Sorted Array

面試過程

🧔：You have two integer arrays, nums1 and nums2. Both arrays are sorted in non-decreasing order. You're also given two integers, m and n, which represent the actual number of elements in nums1 and nums2, respectively.

Your task is to merge nums1 and nums2 into a single array that remains sorted in a non-decreasing order. Here's the catch: you need to merge the values directly inside the nums1 array, and you should not return anything.

To make this feasible, the array nums1 has a total length of m + n. It consists of the first m elements that you'll need to merge, followed by n slots, all set to zero, which you can use to accommodate the elements from nums2. On the other hand, nums2 simply contains n elements.
👶：I approach this problem by starting from the end of both arrays.

Initialize three pointers:

ns1 pointing to the last element in nums1 that has an actual value (index m-1).
ns2 pointing to the last element in nums2 (index n-1).
lens pointing to the last position of nums1 (index m+n-1).
Use a loop to iterate as long as both ns1 and ns2 have not reached the beginning of their respective arrays:

If the element at nums1[ns1] is greater than nums2[ns2], place nums1[ns1] at the position indicated by lens and decrement ns1.
Otherwise, place nums2[ns2] at the position indicated by lens and decrement ns2.
In each iteration, decrement lens.
If there are still elements left in nums2 (i.e., ns2 hasn't reached the start), copy them into the remaining positions of nums1.

This solution efficiently merges the two arrays in-place without using any additional space.

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int ns1 = m-1;
    int ns2 = n-1;
    int lens = m+n-1;
    
    while(ns1 >= 0 && ns2 >= 0){
        if (nums1[ns1]>nums2[ns2]){
            nums1[lens] = nums1[ns1];
            ns1--;
        }
        else{
            nums1[lens] = nums2[ns2];
            ns2--;
        }
        lens--;
    }
    while(ns2 >= 0){
        nums1[lens] = nums2[ns2];
        ns2--;
        lens--;
    }
    return;
}

494. Target Sum

面試過程

🧔：給你一個與數組相關的問題，這也是考驗你在動態規劃上的能力。先讓我描述一下問題背景。

假設你有一個整數數組，你可以在這些數字前放置 '+' 或 '-' 符號，目的是要使這些數字的和達到某個特定目標值。

例如，給定數組 [2,1] 和目標值 1，你可以有以下組合：

+2 -1 = 1
所以答案是1。
現在的問題是，給定一個數組和一個目標值，你能計算出有多少種方法可以達到這個目標值嗎？
👶：好的，這段程式的主要目的是計算有多少種方法可以使得一組數字透過加或減得到特定的目標值。

初始化：我定義了一個偏移量offset，使得在計算時，所有可能的和都會正向偏移，從而避免使用負數索引。

動態規劃：我使用了dp這個二維數組，其中dp[i][j]代表前i個數字可以達到和為j - offset的方法數。初始化時，沒有使用任何數字時，和為0的方法是唯一的。

更新策略：對於nums中的每個數字，我都嘗試了加或減的選擇，並相應地更新dp數組。

結果：最後，我查詢dp[numsSize][target + offset]，即得到了使用所有數字，達到目標和的方法數。

這種方法之所以有效，是因為它利用了動態規劃來避免重複的計算，同時能確保所有可能的組合都被考慮到。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int findTargetSumWays(int* nums, int numsSize, int target) {
    int offset = 1000;
    int dp[numsSize + 1][2 * offset + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][offset] = 1;

    for (int i = 0; i < numsSize; i++) {
        for (int j = -offset; j <= offset; j++) {
            if (dp[i][j + offset] > 0) {
                dp[i + 1][j + nums[i] + offset] += dp[i][j + offset];
                dp[i + 1][j - nums[i] + offset] += dp[i][j + offset];
            }
        }
    }
    if (target > offset) {
        return 0;
    }
    return dp[numsSize][target + offset];
}

初步檢討

• 程式的撰寫過程應該更流暢一點，並且應該想好完整的解題思路之後再進行說明
• 英文口說應該再多加練習
• 可以增加註解來讓interviewer更加了解程式運作原理
• 避免冗言贅字和過多的語助詞
• 等到interviwer確實了解interviwee的解題方法後再開始撰寫程式
• 使用的引數、陣列、變數等等的功能應該要更清楚地解釋給interviwer
• interviwer的問題太少，應該要多增加與interviewee的互動
• leetcode練習的太少，在解題的時候花太多時間

改善方法

• 先將思考過程告知interviwer再開始撰寫程式
• 盡量在說明過程時以Top-Down的方式解釋解題思路
• 語助詞可以適度使用以爭取思考時間，但不宜太頻繁出現
• 多練習英文聽力及口說
• 增加與interviwer交流確認題意，並解釋程式的功能、使用的變數等等
• 多加練習leetcode

---

第二次作業-他評 01

關於 interviewer

• 優點

• 語速適中
• 說話清晰

• 可改進的地方

• 0:06: 不須強調題目總共有幾題
• 06:35: 題目都講得很直白，沒有經過包裝讓interviewee可以馬上辨識出關鍵字進而解題
• 07:08: interviewer問題目時可以再多點變形題以考驗interviewer，不然每一題都沒有再多延伸答題的空間

關於 interviewee

• 優點

• 語速適中
• 說話清晰
• 有完整說出解題思路
• 有做到repeat

• 可改進的地方

• 0:38: 螢幕畫面過小導致程式碼難以辨認，整部影片都有該問題
• 0:49: 感覺像是在介紹題目而不是在跟interviewer確認題意

英文題目

• 0:00: 開頭的"OK,excellent"有些突兀

第二次作業-他評 02

關於 interviewer

可改進的地方

• 可對 interviewee 目前寫好的 code 作出提問
• 題目可以包裝一下

關於 interviewee

優點

• 說話清晰

可改進的地方

• 沒有做到 REACTO 的 E，若能針對題目條件，舉出符合的案例會更好
• 先對 interviewer 說明解題方法再開始撰寫 code

其他建議

影片的畫面內容字太小，看不清楚程式碼的部分

第二次作業-他評 03

關於 interviewer

• 優點

• 題目描述清楚

• 可改進的地方

• 題目未附上實際案例以及邊界條件

關於 interviewee

• 優點

• 有提出完整解法並提供多種方法

• 可改進的地方

• REATCO的E可以打在文件上面試官比較好理解在表達的意思
• 實做完未進行Test

第二次作業-他評 04

關於 interviewer

• 優點

• 英文對答流暢，有在 Coding 的同時講說現在在幹嘛。
• 咬字清楚。

• 可改進的地方

• Palindrome Number 可以用別的方式，像是用數字計算的方式去優化原本的程式碼，面試官可以朝著這個可能性去引導面試者去改良內容，最後提到並比較時間複雜度與空間複雜度等等。
• Merge Sort 那邊好像可以再對程式做簡化，面試官在那個時間點可以再跟對方互動一下。