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

作者: 詮贏慕 fullscreen

Interviewee
Interviewer

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

268. Missing Number

: Hi my name is fullscreen.
: Hi fullscreen, I'm your interviewer. Here is your questions.

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Here are some constrains:
n is euqal to the length of nums.
1 <= n <=

${10}^4$
0 <= nums[i] <= n
All the numbers are unique.

: Will all the number be integers?
: Yes they are.

: So the I will be given n distinct numbers in the range from 0 to n, which the range contains n+1 numbers. My job is to find the missing number that is in the range.
: You are right.

: For example, given input [2, 3, 1, 4], I should output 0. Given input [0], I should output 1.
: Yes!

: Ok, I think I can use an naive iterative approach. I iterate over

$nums$ and keep the record of the value I've seen. Finally return unseen value. Which will be

$O(n)$ time complexity and

$O(n)$ space complexity because I need an array to keep track of what numbers I've seen.
: Sounds straight forward for me. Can you code it out?

: Oh, wait. I actually have an better solution. I sum all the numbers in

$nums$ and store it in a variable

$A$. And sum all the number from 0 to

$n$ and store it in variable

$B$. Then I just need to subtract

$B$ from

$A$ to get the missing numbers!! In this approach I'll have a time complexity of

$O(n)$ but a much less space complexity of

$O(1)$.
: Can you show me why this method works?
: Sure. Here is the proof.

B: Sum([0, n])
A: Sum(nums) =  Sum([0, n] - missing_number) = Sum([0, n]) - missing number
B - A = missing_number

: Great now let's see how you will implement this.
: Ok. First, let's define a function that accept a vector<int> as the input and returns an int.

int missingNumber(vector<int>& nums) {

}

: Next, we want to get sum of

$[0,n]$ and sum of

$nums$ and subtract the two to get the missing number.

int missingNumber(vector<int>& nums) {
    int n = nums.size();
    
    // Get the sum of range [0, n]
    int sum_of_range_n = get_sum_of_range(n);
    // Get sum of nums.
    int sum_of_nums = get_sum_of_vector(nums);
    
    return sum_of_range_n - sum_of_nums;
}

: Now, let's implement get_sum_of_range. We can use the mathematical formula.

$1+2+...+n=n(n+1)/2$

int get_sum_of_range(int n) {
    return (n+1) * n / 2;
}

: And get the sum of nums by iterating through the nums.

int get_sum_of_vector(vector<int>& nums) {
    int sum = 0;
    for (const auto i : nums) {
        sum += i;
    } 
    return sum;
}

: So we will have the final code like this.

int get_sum_of_range(int n) {
    return (n+1) * n / 2;
}

int get_sum_of_vector(vector<int>& nums) {
    int sum = 0;
    for (const auto i : nums) {
        sum += i;
    } 
    return sum;
}

int missingNumber(vector<int>& nums) {
    int n = nums.size();
    
    // Get the sum of range [0, n]
    int sum_of_range_n = get_sum_of_range(n);
    // Get sum of nums.
    int sum_of_nums = get_sum_of_vector(nums);
    
    return sum_of_range_n - sum_of_nums;
}

: Let's plug-in some test case to see if the code work.

input: [2, 3, 1, 4]
output: 
    - n = nums.size() = 4
    - get_sum_of_range(4) = 4(4+1)/2 = 10
    - get_sum_of_vector([2, 3, 1, 4]) = 10
    - missing number = get_sum_of_range(4) - get_sum_of_vector([2, 3, 1, 4]) = 10 - 10 = 0
    
input: [0]
output: 
    - n = nums.size() = 1
    - get_sum_of_range(1) = 1(1+1)/2 = 1
    - get_sum_of_vector([0]) = 0
    - missing number = get_sum_of_range(1) - get_sum_of_vector([0]) = 1 - 0 = 1

: Greate can you tell me what's the time and space complexity of your implementation?
: Sure. Let's talk about time complexity first. I iterated through the whole array to get its sum, so get_sum_of_vector is

$O(n)$. I use the math formula to calculate sum of range, so get_sum_of_range is

$O(1)$. So the total time complexity is

$O(n)+O(1)=O(n)$.
: Ok~ What about space complexity?
: Because I did not use any data structure with size that is related to the input array's length so this implementation have a space complexity of

$O(1)$.

: Okay let's spice thing up a little bit. What if the

$nums$ have

$n+1$ integers. And all the element is between

$[1,n]$ inclusive. And there is only one number that is repeated at least twice. Can you find a way to get this reapeated number? Try to solve it without modifying the

$nums$ and use only constant extra space. (287. Find the Duplicate Number)

Given an array of integers nums 
containing n + 1 integers where each 
integer is in the range [1, n] inclusive.

There is only one repeated number 
in nums, return this repeated number.

You must solve the problem without 
modifying the array nums and uses 
only constant extra space.

Constraints:

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except 
for precisely one integer which appears two or more times.

: So now I have an array of

$n+1$ interger. All of the integer a in the range of

$[1,n]$. And there is only one number that is repeated. And the number of time of the repetition is at least twice. My job is to find the repeated number is that correct?
: You are right.

: For example

input: [1, 3, 2, 4, 4]
output: 4

input: [2, 2, 2, 2, 2]
output: 2

input: [1, 1]
output: 1

: You are right. What approache are you going to use?
: The first things that comes to mind is a brute force solution. I keep a array of counter of each number in the range of

$[1,n]$. And I iterate over the array to count the occurance of each number. If any counter reach 2 then I return the number. This solution runs

$O(n)$ and did not modify the array but use

$O(n)$ space.
: If I can sort the array the problem will be easy. I just need to iterate over the arrary once and check if any neighborhood number are the same. But I'll either have to copy or modify the array if I want to sort the array. But either of them is allowed. This one is hard.

: Ok, I'll give you a hint if you can prove that there is at least one duplicate number in

$nums$.
: Because all the numbers have to be in the range of

$[1,n]$ but there are

$n+1$ numbers in the arrary. By pigeonhole principle there must be at least one number that is duplicated.

: Ok, here is your hint. This problem can be solved using binary search in

$O(nlog(n))$ time complexity and constant space complexity without modifying the arrary.
: Umm, interesting. To my understanding, usually we will apply binary search on list that is sorted. But in this problem I'm not allowed to modify the array. And usually you will have a

$O(log(n))$ time complexity if you are using binary search.
: Seems like I will have to apply binary search

$n$ times. Maybe it is like iterate over the array every time I do a binary search.
: You are very close.

: The array is not sorted. But the range of interger

$[1,n]$ is like a sorted array. Maybe you want me to do a binary search in

$[1,n]$?
: Yes your are very very close.

: Ah ha! I think I got a solution. If every element in the arrary is unique. And we only have n elements in the array. And the elements are all in the range of

$[1,n]$. Then each number in

$[1,n]$ actually represent the number of elements in the arrary that is smaller or equal to the number. For example 2 means there are 2 number (1, 2) that is smaller or equal to the number.

Unique array: [4, 2, 3, 1] 
- 3 means there are 3 numbers less or equal to 3.

: But if there are duplications in the array, then this balance will be broken. Or we should say that if the equation holds that means the duplicate number is not below the number we are checking.

array with duplication: [2, 2, 3, 1]
    - there are 4 numbers that are less or equal to 3(the duplicate number 2 is below or equal to 3).
    - there are 3 numbers that are less or equal to 2 (the duplicate number 2 is below or equal to 2).
    - there are 1 numbers that are less or equal to 1 (the duplicate number 2 is above 1)

: Interesting, can you implement your idea?

: Sure! First we need a function that take an array as input and output an interger.

int findDuplicate(vector<int>& nums) {

}

: Let's type out some comment to show my thoughts.

int findDuplicate(vector<int>& nums) {

    // Loop untile binary search is done.
    
        // Get the middle: we want to do binary search.
    
        // Iterate over the arrary and count the number
        // that is less or equal to the middle.
    
        // If the count is smaller or equal to middle,
        // we check the numbers above middle.
        // Otherwise, we check the number below the middle (including middle).

}

: Let's implement it.

int findDuplicate(vector<int>& nums) {

    auto low = 1;
    auto high = nums.size()-1;
    // Loop untile binary search is done.
    while(low != high) {
    
        // Get the middle: we want to do binary search.
        int mid = (low + high)/2;
    
        // Iterate over the arrary and count the number
        // that is less or equal to the middle.
        auto counter = 0;
        for (const auto& num : nums) {
            if (num <= mid) {
                counter++;
            }
        }
    
        // If the count is smaller or equal to middle,
        // we check the numbers above middle.
        if (counter <= mid) {
            low = mid + 1;
        } else {
            // Otherwise, we check the number below the middle (including middle).
            high = mid;  
        }
    }
    
    return low;       
}

: And let's plug in some examples.

input: [1, 3, 4, 2, 2]
expect: 2

iterations:
1. low = 1, high = 4, mid = 2, counter = 3
2. low = 1, high = 2, mid = 1, counter = 1
3. low = 2, high = 2, get out of the loop, return 2

: Great, I think you did a great job. Thank you for participate in our interview today.
: Thankyou!

同儕互評 - 01

Interviewee

• 優點
  • 05:48 : interviewee 主動提出更好的做法，掌握主導權，藉此吸引 interviewer 的目光，有助於增加面試的互動性。
  • 撰寫程式碼時的思考流程很有條理，看起來不像是死背答案的 interviewee
• 缺點
  • 程式碼的行距可以小一點， 可以看到比較多行，畫面也不會一直上下滾動。

Interveiwer

• 優點
  • 20:40 : Interviewer 沒有直接給提示，而是引導 interviewee 思考，順便可以檢驗 interviewee 的數學能力，讓整個面試增加更多互動。
• 缺點
  • 13:30 : Interviewer 還是可以說明題目，增加互動機會，不要讓 interviewee 自己去讀。
  • 30:06 : 可以針對 interviewee 的想法提出問題，增加互動性
  • 37:40 : 沒有針對 interviewee 的程式碼做提問，也沒有針對此問題的後續應用做出更多討論，錯失驗證 interviewee 能力的機會。

---

55. Jump Game

: Here is another problem for you, fullscreen.

You are given an integer array nums. 
You are initially positioned at the array's 
first index, and each element in the array
represents your maximum jump length at that position.

Return true if you can reach the last index, 
or false otherwise.

Constraints:

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5

: So I will be given an integer array with integer greater or equal to 0 and less or equal to

${10}^5$. Each element in the array represent the maximum jump I can make. And I'm initially at index 0 of the array. I need to decide wheather I can reach the last index. Return true if I can, otherwise return false.
: For example:

1. input: [1, 2, 1, 0]
    output: true
2. output: [1, 0, 2, 1]
    output: false
3. input: [0]
    output: true

: You are correct. Do you have any other questions?
: Yes, I do. Am I allow to make backward jump and wrapping around when exceed the boarder? For example if the input is [1, 0, 0], can I jump from index 0 to the last index?
: Good question, jump does not wrap around when you exceed the boarder.
: Ok, I think I understand the question fully. What I have in mind right now is recursion. Starting from the last index I check which index are able to lead me to the last index. I'll then check if any of these indexes is 0. If there is, then I return true. Otherwise, I will push those candidates in a queue. And pop the next item in the queue to perform the check again.
: Sounds good, can you show me the code?

: Ok, so I need a function which take a integer array as input and return a boolean.

bool canJump(vector<int>& nums) {

}

: Let's write some comments to illustate what I mean.

bool canJump(vector<int>& nums) {
    // A stack that stores the candidate index.
    
    // Initilize: push the last index into the stack.
    
    // While the stack is not empty do:
    // pop a candidate from the stack.
    // Retrieve all the index that can reach current candidate.
    // Iterate over the indexes, if any of them is 0
    // return true, otherwise push them to the stack.
    
    // The stack is empty and we did not find index 0 as our candidate. return false.
}

: Let's write some code.

bool canJump(vector<int>& nums) {
    // A stack that stores the candidate index.
    stack<int> candidates;
    
    // Initilize: push the last index into the stack.
    candidates.push(nums.size() - 1);
    
    // While the stack is not empty do:
    while (!candidates.empty()) {
        // pop a candidate from the stack.
        int candidate = candidates.top();
        candidates.pop();
        
        // Retrieve all the index that can reach current candidate.
        vector<int> reachables = get_reachables(nums, candidate);
        
        // Iterate over the indexes, if any of them is 0
        // return true, otherwise push them to the stack.
        for (int i = 0; i < reachables.size(); i++) {
            if (reachables[i] == 0) {
                return true;
            } else {
                candidate.push(reachables[i]);
            }
        }
    
    }
    
    // The stack is empty and we did not find index 0 as our candidate. return false.
    return false;
}

: The get_reachables function will take an array of integer and a integer (represent the current index) as input. And it will return an array of integers as output.

vector<int> get_reachables(vector<int>& nums, int index) {

}

: Starting from the index before the current index. We check the index backward until we reach index 0. Let the current index is

$e$ and the index we are checking is

$d$, and

$nums[d]>=(d-e)$, we push index

$d$ into the output array.

vector<int> get_reachables(vector<int>& nums, int index) {
    vector<int> reachables;
    for (int i = index - 1; i >= 0; i--) {
        if (nums[i] >= index - i) {
            reachables.push_back(i);
        }
    }
    
    return reachables;
}

: So the overall code looks like this.

vector<int> get_reachables(vector<int>& nums, int index) {
    vector<int> reachables;
    for (int i = index - 1; i >= 0; i--) {
        if (nums[i] >= index - i) {
            reachables.push_back(i);
        }
    }
    
    return reachables;
}

bool canJump(vector<int>& nums) {
    // A stack that stores the candidate index.
    stack<int> candidates;
    
    // Initilize: push the last index into the stack.
    candidates.push(nums.size() - 1);
    
    // While the stack is not empty do:
    while (!candidates.empty()) {
        // pop a candidate from the stack.
        int candidate = candidates.top();
        candidates.pop();
        
        // Retrieve all the index that can reach current candidate.
        vector<int> reachables = get_reachables(nums, candidate);
        
        // Iterate over the indexes, if any of them is 0
        // return true, otherwise push them to the stack.
        for (int i = 0; i < reachables.size(); i++) {
            if (reachables[i] == 0) {
                return true;
            } else {
                candidate.push(reachables[i]);
            }
        }
    
    }
    
    // The stack is empty and we did not find index 0 as our candidate. return false.
    return false;
}

: Let's plugin some test case to see if the algorithm is correct.

input: [1, 2, 0, 1]
round 1:
    - current index 3
    - get reachable:
        - check index 2: nums[2] = 0 < 3-2 = 1 (does not store this)
        - check index 1: nums[1] = 2 >= 3-1 = 2 (store this)
        - check index 0: nums[0] = 1 < 3-0 = 3 (does not store this)
        - return [1]
    - 1 is not 0, push 1 to stack
round 2:
    - current index 1
    - get reachable:
        - check index 0: nums[0] = 1 >= 1 - 0 = 1 (store this)
        - return [0]
    - we get index 0, return true.

: Greate, what is the space and time complexity of this algorithm?
: The time complexity is

$O(n^2)$ because for each element we will need to check at most n-1. And the space complexity is

$O(n^2)$ because we could have push n-1 candidate to the stack at each check.
Can you think of a better solution?
If we don't check the element we already check then we can reduce our time complexity to

$O(n)$. We can use a vector to store the index we have check. And this modification will give us a space complexity of

$O(n)$.
: Can you do it better? Like time complexity

$O(n)$ and space complexity

$O(1)$?
: I think I can modify the solution. I iterate through the

$nums$ and record the farest index I can reach. If the farest index I can reach is the last index, then I return true. Otherwise, return false.

bool canJump(vector<int>& nums) {
    int i = 0;
    for (int reach = 0; i < nums.size() && i <= reach; i++) {
        reach = max(i + nums[i], reach);
        if (reach == nums.size() - 1) {
            return true;
        }
    }
    return i == nums.size();
}

: This method have an time complexity

$O(n)$ and a space complexity

$O(1)$.
: Very good. I think that is it for today. Thank you for your participation.

同儕互評 - 01

Interviewer

• 優點
• 缺點
  • 01:03 : 與其照唸題目，不如多舉些例子，讓 interviewee 更了解題目需求
  • 06:14 : 這邊不應該對 interviewee 的想法照單全收，要適時的針對 interviewee 的想法提出問題 (例如：為什麼用 stack 比用 queue 好？有什麼好處？)，與其讓 interviewee 盡快寫程式(讓死背考題的 interviewee 有機可趁)，不如先檢驗 interviewee 解決問題的能力以及相關程式能力。
  • 16:22 : 從 16:22- 21:11 interviewee 花了將近5分鐘在代數字測試， 也許 interviewer 可以適時的打斷，直接問更深入的問題(例如：應用場景、如何優化…等)，畢竟 interviewer 看完程式碼就應該知道 interviewee 的思路是否正確，不需要再浪費時間代數字。
  • 25:40 : 與其直接問 interviewee 「有沒有更好的解法」，不如用討論的方式對 interviewee 的程式碼做優化，畢竟這些 interviewee 將來可能會是你的同事，不如藉此機會來測試 interviewee 的溝通與合作能力。

Interviewee

• 優點
  • 撰寫程式碼時的思考流程很有條理，看起來不像是死背答案的 interviewee
• 缺點

同儕互評 - 02

• 面試者

  • 01:30追問題目細節、主動給予範例、討論 edge-case，都很流暢
  • 05:49 講完 brute-force 就直接講能不能做得更好，自問自答雖然很積極，但也可以考慮先暫停一下，讓面試官有機會插嘴問一些問題。
  • 11:11 把測資帶進寫好的程式碼驗證也很棒
  • 20:15 在做完一定分析後，勇敢要提示，很棒 (而不是什麼都沒講就要提示)

• 面試官

  • 00:02 確認面試者名字時，講"是吧?" 有可能挑起對方一點不舒服的情緒
  • 01:25 面試官也許可以一開始講解題目時就給一些範例
  • 13:24 變化版的題目，可以嘗試由面試官直接講解，而不是讓面試者自己看，因為面試時間通常不會太長，除非就是要考驗面試者閱讀問題的能力，不然建議可以由面試官簡潔的講完問題並強調重點後，留更多的時間讓面試者闡述想法
  • 20:17 在面試者請求提示時，先問他一些問題來引導，我覺得是很棒的互動
  • 37:35 可以問問看，什麼時候、或在什麼應用中，會需要用到你們今天討論到的內容

初步檢討

• interviewer 照著題目念，並沒有把題目稍微修改，這樣遇到死背解法的就無法發現
• interviewee 可以舉一些該演算法或是問題在日常生活的應用，趁機展現自己的知識
• binary search 的時間複雜度一般來說是
  $O(log(n))$，影片裡有講錯