>包拯-Moon
>:ice_cube: : Interviewer :fire:: Interviewee

# 2025 年「資訊科技產業專案設計」課程作業 1
## [283. Move Zeroes](https://leetcode.com/problems/move-zeroes)
>[影片連結](https://youtu.be/RY5ohOEEK8k)
### 模擬面試過程
:ice_cube: : 題目給你一個陣列，你要將陣列中所有的0都移動到最後，並且保持其他非零元素的相對順序。
:fire:: 好。比如輸入是[0, 1, 0, 3, 2]的話，最後的輸出就要是[1, 3, 2, 0, 0]。
我的想法是去不斷地檢查陣列，如果遇到0，而且他後面有非0的數字，就把兩個元素交換，這樣所有非零元素會慢慢被往前推，而零同時就會被推到陣列後面，然後使用一個while迴圈搭配計數器，一直重複這個過程，直到整個陣列再也沒出現需要交換的情況，就結束。
:ice_cube: 聽起來是個很直觀的方法，你要試著寫出來看看嗎？
:fire: : 當然。
### Bubble-Like Shifting Method

void moveZeroes(int* nums, int numsSize) {
    while (true){
        int count = 0;
        for (int i = 0; i < numsSize - 1; i++){
            if(nums[i]==0 && nums[i+1]!=0){    
            count++;
            nums[i] = nums[i+1];
            nums[i+1] = 0;
            }
        }
            if(count==0){
                break;
            }
    }   
}

:fire: : 這個方法每次回全要掃整個陣列一次，最糟的情況會需要重複大概n輪，所以整體的時間複雜度是$O(n^{2})$
:ice_cube: : 好。但這個方法用了多輪迴圈，你也清楚他的時間複雜度不佳。有沒有方法可以讓他快一點？
:fire: : 我想到可以用雙指標的方式來優化。
### Two-Pointer Method

void moveZeroes(int* nums, int numsSize) {
    int j = 0;
    for (int i = 0 ; i < numsSize ; i++){
        if (nums[i] != 0){
            nums[j++] = nums[i];
        }
    }
    while (j < numsSize){
        nums[j++] = 0;
    }
}

:fire: : 這樣就可以將時間複雜度降到$O(n)$, 而且一樣只使用到兩個變數i和j，所以空間複雜度是$O(1)$。

##

## [357. Count Numbers with Unique Digits](https://leetcode.com/problems/count-numbers-with-unique-digits)
>[影片連結](https://youtu.be/r1FEfGy4LXI)

### 模擬面試過程
:ice_cube: : 題目給你一個非負整數n，你要計算出在0到$10^{n}$的範圍內，有多少個數字是「各位數不重複」的。
:fire: : 好，首先題目的範圍是$0$到$10^{n}-1$，也就是要找出n位數以內所有每個位數不重複的數字，我這樣理解是正確的嗎?
:ice_cube: : 沒錯。
:fire: : 好的。那面對這題我會先考慮到兩個比較簡單的狀況。如果n等於0，那就只有0這個數字，所以會回傳1。
:fire: : 如果n等於1，範圍就是0~9，所以答案會是10。
:fire: : 再來就是對於n等於2以上的情況，讓我想到可以用排列組合去計算有幾個沒有重複數字的數字。在兩位數的情況，十位數不能是0，所以有1~9，9種選擇，個位數的話就不能跟十位數重複，但可以是0，所以一樣剩下9種，所以如果是兩位數的話就有$9*9$，81種可能，n更大的狀況就以此類推。
:ice_cube: : 這個方法聽起來很不錯，那你能用程式實現出來嗎?
:fire: : 沒問題。
### Combinatorial Approach

int countNumbersWithUniqueDigits(int n) {
    if (n == 0) return 1;
    if (n == 1) return 10;
    int ans = 10, first = 9, last = 9;
    for (int i = 2 ; i <= n && last > 0 ; i++){
        first *= last;
        ans += first;
        last--;
    }
    return ans;
}

:fire: : 這段程式的時間複雜度是$O(n)$，他的for迴圈最多會執行n-1次。
:fire: : 但是因為數學上的限制，我們只有10個不同的數字，所以迴圈會在last這個變數遞減到等於0的時候停止，代表不管n多大迴圈最多只會執行9次，所以其實也可以說他的時間複雜度是$O(1)$，但$O(n)$是比較直接的分析方法。
##
## [35. Search Insert Position](https://leetcode.com/problems/search-insert-position)
>[影片連結](https://youtu.be/Xt06UCwkOek)

### 模擬面試過程
:ice_cube: : Let's move on to the next question. You're given a sorted array of integers and a target value.
:ice_cube: : You need to return the index if the target is found.
:ice_cube: : If not, return the index where it should be inserted in order.
:ice_cube: : Do you have any question about this question?
:fire:: Ok. The array is already sorted and I need to return the index of the target if it exists.
:fire:: If not, I should return the index where the target should be inserted to keep the array sorted.
:fire:: Let me check with an example to make sure I understand correctly.
:fire:: If the input is [1, 3, 5, 6] and the target is 2, the output should be 1 because it is larger than 1 but smaller than 3. Is that correct?
:ice_cube: : Great. So, what approach comes to your mind first?
:fire:: The first idea I had was linear search. I think I could iterate from the start and return the first index where the number is greater than or equal to the target. If I reach the end without finding such a number, I'll return the length of the array.
:ice_cube: : Ok. That's a pretty straightforward approach. Can you analyze the time complexity?
:fire: : The time complexity is $O(n)$ because in the worst case, which means the target greater than all elements in the array, I need to traverse the entire array.
### Linear Search

int searchInsert(int* nums, int numsSize, int target) {
    for (int i = 0 ; i < numsSize ; i++){
        if (nums[i] >= target) return i;
    }
    return numsSize;
}

:ice_cube: : Good analysis. But I think ... $O(n)$ is kind of slow.
:ice_cube: : The proplem mentions the array is sorted. Do you see any room for optimization ?
:fire: : Oh right. I overlooked this important condition. Since the array is already sorted, I can use binary search to optimize the time complexity.
:ice_cube: : Can you explain it ?
:fire: : The core idea of binary search is to reduce the search space by half each time.
:fire: : I maintain two pointers ***left*** and ***right***, and caculate the midpoint.
:fire: : If the midpoint equals to the target, return midpoint directly.
:fire: : If the midpoint is smaller than the target, it means the target is in the right half, so move the left pointer to the midpoint plus one.
:fire: : If the midpoint is greater than the target, means the target is in the left half, so we move the right pointer to midpoint minus one.
:ice_cube: : Yep. That sounds like a better plan. But the special case for this problem is the target value might not exist, and you need to return the insertion position. How do you handle that?
:fire: : Well. I think when the search ends, the left pointer will point to the position of the first element greater than the target, which is exactly the insertion position.
:ice_cube: : Sounds nice. Could you code it up ?
:fire: Sure. No problem.
### Binary Search

int searchInsert(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;

    while (left <= right){
        int mid = left + (right - left)/ 2;

        if (nums[mid] == target){
            return mid;
        }else if (nums[mid] < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return left;
}

## 整體初步自評：
#### For Interviewer
1. 深度不足：因為自己本身對於C沒有到專精，所以可以提出的意見很有限
2. 也因為這方面的knowledge還有要加強的地方，所以可以提出的追問也比較少，顯得這個模擬面試比較古板不活潑
3. 比較少去追問空間複雜度
4. 要把題目用較容易理解的方式提出比較不會讓面試者產生額外的疑慮
5. 表情控管
6. 題目會有一些條件，要在一開始或是在面試者確認題目是否有理解正確的時候講清楚

#### For Interviewee
1. Basic Knowledge：在講解細節的部分還需要再補充，避免產生背標準解的感覺
2. 組織語言：放慢語速卻順暢地講可能會比講快而口吃來的好
3. 邊打程式邊講解的能力需要再加強
4. 有時會為了打字追求快速而錯字增多，浪費時間，要取得平衡點
5. 在**排列組合**的講解要更嚴謹，避免使用一些似是而非的用語例如：以此類推
6. 在變數名稱的定義可以更直觀一些，主要是讓大家一目了然
7. 忽略了**邊界狀況**，在某些題型下可能會因沒顧慮到一些細節而落入陷阱
8. 在解釋**Binary Search**的敘述比較冗長，有些簡單幾句話可以解釋的要儘量精簡
9. 用Google Docs所以可能有時候會少打一些符號像是分號或括號，縮排方面也是不好顧慮
10. 有些太簡單的地方不需要解釋，因為面試官並不是編譯器，講重點
11. 在提到一個新的方法時要講解「為何這個方法可以優化」等等關於這個方法的細節

##