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

貢獻者: 查理-Charlie

: 我
: 面試官
影片-1
影片-2
影片-3

704. Binary Search

模擬面試過程

: 題目會給你一組數列，和一個目標數字，希望你能從數列中找 出目標數字並回傳他的索引。若是目標數字不在這組數列中，則回傳-1。

: 請問你對題目有疑問嗎？

: 有，我想請問輸入的數列有經過排序嗎？

: 有的，題目輸入的數列經過升冪排序。

: 好的，爲了確認我對題目的理解，我想用一個例子説明

輸入： [-1,0,3,4,9,10] 目標數 : 9
輸出： 4

: 請問我的理解正確嗎？

: 正確，你可以開始寫你的程式了。

: 在寫程式之前，我想先講一下我的想法。

: 這題最直觀的作法是從第一個數開始遍歷整個數列，找到目標值或者大於目標值時停止。

int search(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size();i++){
        if (nums[i] == target){
            return i;
        }
        else if (nums[i]> target){
            return -1;
        }
    } 
    return -1;
}

: 這個方法很直觀，但是當資料很多筆時，因為時間複雜度是O(n)可能會造成運算時間太長。

: 沒錯，那若是時間複雜度限制為O(log n)，你會如何優化?

: 若是有時間複雜度的限制條件下，我會使用二分搜尋法做這道題，在左右各設一個邊界，將邊界值相加除以二後的中間值和目標做比較，若中間值大於目標值則將右邊界往內，若中間值小於目標值則將左邊界往內，反覆測試得到和目標相同的數值。

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size()-1;
    while(left <=right){
        int mid = (left + right)/2;
        if (nums[mid] > target){
            right = mid-1;
        }
        else if (nums[mid] < target ){
            left = mid+1;
        }  
        else {
        return mid;}
    }
    return -1; 
}

---

11. Container With Most Water

模擬面試過程

: 題目給你一組整數數列，有 n 條垂直線被繪製，每條線的兩個端點分別是 (i, 0) 和 (i, height[i])。找到兩條線使其與x軸形成的面積最大。

: 請問你對題目有疑問嗎？

: 有，我想請問輸入的數列有經過排序嗎？

: 沒有，題目預設輸入的數列為隨機分配。

: 好的，爲了確認我對題目的理解，我想用一個例子説明

輸入 : [1,8,6,2,5,4,8,3,7]
輸出 : 49

: 請問我的理解正確嗎？

: 正確，你可以開始寫你的程式了。

: 在寫程式之前，我想先講一下我的想法。

: 這題最直觀的作法是窮舉法，列舉出所有的面積，再比較出最大的面積。我會使用兩個迴圈來做。

int maxArea(vector<int>& height) {
    int res = 0;
    int n = height.size();

    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            int tmp = (j-i)*min(height[i], height[j]);
            res = max(res, tmp);
        }
    }

    return res;
}

:這麼做雖然能達成題目要求，但是有很大的改進空間，你能使用其他方法優化嗎?

: 另一種方法我會使用two pointer 的方法來做。在寫程式之前，我想先講一下我的想法。首先在頭尾各放一個指標，指標指著兩個最高的柱子有可能形成更大的面積，然而將指標內縮時可能會造成面積變小，因此我們期待內縮後的柱子是更高的，才能機會得到更大的面積，所以我會移動高度較小的一邊。

int maxArea(vector<int>& height) {
    int i = 0;
    int j = height.size() - 1;
    int max_area = 0;

    while (i < j) {
        int cur_area = min(height[i], height[j]) * (j - i);
        max_area = max(max_area, cur_area);

        if (height[i] < height[j]) {
            i++;
        } 
        else {
            j--;
        }
    }

    return max_area;   
}

:這麼做的時間複雜度為O(n)，運行效率比第一種方法好很多。

---

136. Single Number

模擬面試過程

: In this question, you are given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

: Do you have any questions ?

: Yes. Has the array been sorted?

: No,they aren’t. Is there any questions?

: I think no. I would like to use one example to check my understanding about this question.

input ： [3,1,5,5,3]
output ： 1

: Am I correct about this question?

: Yes. You can start codding now.

: I want to explain my thoughts about this problem first.

: I will start at organize the array into a ascending series, then I'll compare the first and the second numbers. If they're not equal then it means the first number is single, s I find the single number.

: If they're equal then I'll skip to the fourth number and compare it to the third. This is because the numbers either appear twice or once. If all the elements except the last one are pairs, then the single number is the last one.

int singleNumber(vector<int>& nums) {
	sort(nums.begin(),nums.end());
	for(int i =1;i<nums.size();i+=2){
		if (nums[i]!= nums[i-1])
			return nums[i-1];
	}
	return nums[(nums.size()-1)];
}

: So your first approach is to compare all the numbers in the array. Can you use more effective methods?

:Yes, I can use bit operator to solve this question.

: We all know that XOR comply with commutative laws and distributive law. And most importantly ,any number XOR with 0 will become itself. So by the very nature of XOR, I can solve the problem quickly.

int singleNumber(vector<int>& nums) {
    int A = nums[0]; 
    for(int i =1;i<nums.size();i++){
	    A = nums[i] ^ A;
    }
    return A;
}

---

模擬面試檢討

自評 704. Binary Saerch

interviewer:

1. 0:34 可以加入一些肢體動作，不應該只是呆坐著。
2. 5:07 不該直接問「時間複雜度為…的時候該怎麼做」，避免interviewee背誦或猜測。
3. 沒有後續的問題和程式碼討論，interviewer 沒有表現出有鑑別interviewee能力的行為。

interviewee:

1. 整體口齒可以更清晰。
2. 一邊打程式一邊解說時，聲音會越來越小。
3. 2:58 打程式時發生打錯字，或者漏打，應該多練習打程式的速度和正確率
4. 5:58 說話聲音有時會忽大忽小。

---

自評 11. Container With Most Water

interviewer:

1. 0:49 interviewer應該清楚說明關於輸入的數值範圍等等限制，過多的停頓顯得沒有自信。

interviewee:

1. 1:25 拿滑鼠的聲音太大聲了。
2. 整體口齒可以更清晰。
3. 3:30 多練習打程式的正確率，避免在小地方發生錯誤。
4. 4:26 說話聲音有時會忽大忽小。
5. 5:10 8:32 不該太依賴手勢去解釋思路。
6. 一邊打程式一邊解說時，聲音會越來越小。

---

自評 136. Single Number

interviewer:

1. 0:05 array 念錯了
2. 聲音太小

interviewee:

1. 1:05 避免不必要的手勢。
2. 1:45 聲音太小，而且講話不清楚。
3. 2:20 不應該只是唸出程式碼。
4. 2:50 程式碼打錯，要多練習正確率。

第二次作業-他評01

關於interviewer

可改進之處

• 1:34: 我猜應該是口誤，面試官應該要先了解受試者會以什麼方式去解題後再請受試者開始撰寫程式碼。
• 5:07: 這邊我覺得不應該直接問說有沒有 O(logn) 時間複雜度的解法，而是要問說有沒有更快的解法呢？ 因為直接說明有某種時間複雜度是多少的解法可能提示的太多了。
• Single Number 問題當中第一種解法有用到sort()，可以問問看受試者C++程式庫中sort()函式的時間複雜度是多少，或是有沒有更快的sorting方法，來考驗受試者對於程式庫的了解。

interviewee

優點

• 0:54: 受試者有針對題目說明不清楚的點提出疑問 👏
• 在講解程式碼時有加入動作讓想法更形象化

可改進之處

• 沒有在影片當中做 Test

第二次作業-他評02

interviewer

優點

• 題目解釋的很清楚，而且一開始就有出現在上面了，方便面試者閱讀。

可改進之處

• 在出題時的語調感覺可以再更自然一些。

interviewee

優點

• 可以邊寫程式邊解釋目前做到哪裡，很厲害!

可改進之處

• 01:54: 在描述想法時可以把它打出來，可以讓面試官更理解。

第二次作業-他評03

關於 interviewer

• 優點

• 0:09 題目太過於明顯直接抄leetcode的，應該做適當的包裝。

• 可改進的地方

• 咬字可以清楚一點，尾音的字都會不見。

關於 interviewee

• 優點

• 5:21 有做題目的延伸探討並且回答詳細，很棒。

• 可改進的地方

• 4:48 我覺得還是稍微縮排一下。
• 9:13 可以舉例trace一下程式稍微驗證一下正確性。

第二次作業-他評04

Interviewer

• 優點
  • 說明清晰
• 缺點
  • 面試官很冰冷，感覺比電我的教授還兇，我老師電我幾句還會說點好話或著笑一下安慰之類的。

Interviewee

• 優點
  • 有落實"確認，舉例，說明方案，撰寫程式，驗證程式"
  • 咬字很乾淨，可用2倍速聽
  • 邊coding有編說明，不會尷尬
• 缺點
  • 聲音有點小，我得用外掛軟體放大音量才聽得道(600%音量欸)
  • 驗證程式可能要更確實

第二次作業-他評04

關於 interviewer

• 優點

• 題目表達清楚明瞭。

• 可改進的地方

• 0:42 不過有時候語速會瞬間加快，有小部分不容易聽出你說了甚麼。

關於 interviewee

• 優點

• 口齒很清晰，相較於 interviewer，這邊語速控制得很均衡。
• REACTO 中 E 的部分清晰有條理。

• 可改進的地方

• 如同其他同學所說，驗證不夠確實。