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

貢獻者: 半條悟-satoru
模擬面試錄影-1 (漢)
模擬面試錄影-2 (漢)
模擬面試錄影(英)

1. Two Sum

$i n t e r v i e w e r$

你好，我是今天主持這場面試的人，文遠，那我們就開始面試。
第一題，給予一個內容都是整數integer的vector，以及一個數字以下稱為target，請你印出兩個數字的index，而這兩個數字相加會等於target。
你可以假設在整個vector中只有一組解，印出的index順序不拘，但你不可以使用同個元素兩次。

interviewee

也就是說，比如我有一個vector內含[2,5,7,16,21,10]，如我螢幕上所示，且target = 12，那麼預期得到的結果是[1,2]嗎？

$i n t e r v i e w e r$

是的沒錯。

interviewee

再比如說，我有一個vector內含[2,7,7,8,10,19]，如我螢幕上所示，且target = 14，那麼預期得到的結果是[1,2]嗎？

$i n t e r v i e w e r$

是的，這也正確。

interviewee

感謝，那我首先想到的方法是，以兩個for迴圈，遍歷這個vector，外圈for固定住第1個數，內圈for尋找index在第1個數之後的所有元素，並嘗試找出與他相加等於target的數。在找到配對的時候記錄下兩個for回圈當下的index，立刻return。
(大略說完後，一邊寫扣一邊配合註解並解說)

#include <iostream>
#include <string>
#include <map>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        vector<int> ans;
        int n = nums.size();

        for(int i = 0;i < n-1;i++){
            for(int j = i+1 ; j < n ; j++ ){
                if(nums[i]+nums[j] == target){
                    ans.push_back(i);
                    ans.push_back(j);

                    return ans;
                }
            }  
        }
        return ans;
    }
};

interviewee

我完成了，請問有什麼問題嗎？

$i n t e r v i e w e r$

感覺相當不錯，那你可以分析一下當前這個解法的時間複雜度嗎？

interviewee

第一個迴圈從第0個到n-1，而第二個迴圈會做n-1次、n-2次、n-3次…所以這個方法的時間複雜度為

O (n^{2})

$i n t e r v i e w e r$

那我們是否有方法節省更多時間，讓資料不需要讀那麼多次呢？

interviewee

或許可以用一個map並遍歷一次vector。
每次看到元素的當下先以「target減當前元素值」，作為key來搜尋map是否已出現過與當前元素值可以相加乘target的數。
如果有找到，則將map的index以及當前的index作為結果return，因為可以假設只有一組解。
如果未找到，將當前值作為key、當前的index作為value新增到map中。
(大略說完後，一邊寫扣一邊配合註解並解說)

#include <iostream>
#include <string>
#include <map>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int>::iterator ptr;
        // numlist前者是值作為key，後者是在nums中的index
        map<int,int> numlist;
        vector<int> ans;
        
        for(int i = 0;i < nums.size();i++){
            //先搜尋target減當前的值
            ptr = numlist.find(target-nums[i]);
            //代表找到了
            if(ptr != numlist.end()){
                ans.push_back(ptr->second);
                ans.push_back(i);
                return ans;
            }
            //沒找到則新增元素
            numlist[nums[i]] = i;
         
                 
        }
        return ans;
    }
};

interviewee

我完成了，請問有什麼問題嗎？

$i n t e r v i e w e r$

看起來也不錯，那這個方法為何節省了時間？

interviewee

因為用map的方式，這使得vector內的值只被掃過一次即可明白解出現在何處，不必跑2次迴圈，時間複雜度變成了

O (n)

。

169. Majority Element

$i n t e r v i e w e r$

好，那我們就繼續下一題吧。
給予一個大小為n，僅含整數integer的vector，尋找出在這個vector中是哪個值出現超過n/2次？
你可以假設必定存在一個數字出現超過n/2次。

interviewee

也就是說，比如我有一個vector內含[2,5,7,7,7,7]，如我螢幕上所示，那麼預期得到的結果是7嗎？

$i n t e r v i e w e r$

是的沒錯。

interviewee

再假設我有一個vector內含[2,-9000000,2,25,7,-7,2,48763,2,2,2]，如我螢幕上所示，答案則為2嗎？

$i n t e r v i e w e r$

這也正確，正負數都會出現。

interviewee

感謝，我想可以先對vector做一個排序，使得相同的數字會連續在vector中，又且因為必定有超過n/2個元素是相同的，那我們則可以知道vector[n/2]這位置必定存在答案。

$i n t e r v i e w e r$

聽起來不錯，開始實作吧。

interviewee

(一邊寫扣一邊配合註解並解說)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(),nums.end());
        // because major must appear over n/2 times
        return nums[n/2];
        
    }
};

interviewee

我完成了，請問有什麼問題嗎？

$i n t e r v i e w e r$

那對於本解法，你覺得時間複雜及空間複雜度應該為多少呢？

interviewee

因為一開始就sort過一次，所以至少為

O (n l o g n)

，剩餘的步驟只是遍歷了一次vector，所以是

O (n)

，那麼總結下來，時間複雜度就是

O (n l o g n)

。
空間複雜度則為，額外1個變數、，也就是

O (1)

。

$i n t e r v i e w e r$

好，那麼我們希望在維持空間成本依舊在

O (1)

的狀況下，我們將執行效率再次提升，希望可以達到線性執行時間，你有什麼想法嗎？

interviewee

(做事、想一下)我觀察到，若必定存在最大元素的話，將其稱為A，同時刪除一個非A及一個A的元素似乎不對結果造成影響，同時刪除兩個不同的非A元素也不會對A造成影響。這或許是關鍵。
如果我只遍歷一次vector，並設立一個計數器count及一個紀錄元素值的變數major，
計數器為0的時候，將計數器加1，並將當前的元素放入major。
當major元素與當前遍歷元素一致，則count+1。
當major元素與當前遍歷元素不同，則count-1。
如此一來，遇上不同的元素時，等於同時刪除兩個元素各一次，遇到相同元素時則記錄當下還剩下多少major元素。
最終，遍歷完成後，major變數內必定剩下我們要求的解。
(一邊寫扣一邊配合註解並解說)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        
        int major;
        int count = 0;
        
        for(int i = 0 ;i < nums.size(); i++){
            
            if(count == 0){
                major = nums[i];
                count++;
            }
            else if(major == nums[i])
                count++;
            else
                count--;
        }
        
        return major;
    }
};

interviewee

我完成了，請問有什麼問題嗎？

$i n t e r v i e w e r$

看起來相當好。那我們再進入下一題。

延伸閱讀：
Boyer-Moore Majority Vote Algorithm

36. Valid Sudoku

$i n t e r v i e w e r$

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Only the filled cells need to be validated according to the mentioned rules.
If a place is empty, it will be filled with "."

interviewee

In my first thought,I will loop over the Sudoku board and skip all the place that not filled with number.
When current index is a number,start to check the row,the col and the 3 x 3 box that it belongs to.If once detect the duplicate number, instantly return false
If looping is over,result should get true.

$i n t e r v i e w e r$

ok, that is a solution,but I think this solution pass vector data too many times?Do you have any thought about reducing the data reading times and speed up validating the Sudoku board?

interviewee

Sudoku board have 9 row,9 colunm and 9 sub 3 x 3 box,may I can use 3 vector to record number that already appeared in each row,colunm and sub box.
in the vector store a short and use bit 1 to bit 9 represent whether number 1 to 9 is already appeared or not.
now start looping the board,every time I detect a number,go to check the vector element corresponding to row,colunm and box of current index.
For example,if element in current index is 5, minus it with '0' to get ASCII Difference,then left shift 1 five bits, bitwise and with corresponding row,colunm and box vector element,if true,means number already appeared,just return false.If false,bitwise or with corresponding row,colunm and box vector element to update.
so we can just only read each element on board once,achieving the speeding up.

$i n t e r v i e w e r$

That sounds good,you can start implementing it.

interviewee

(coding while explaing)

class Solution {
public:

    bool isValidSudoku(vector<vector<char>>& board) {
        vector<short> col(9, 0);
        vector<short> block(9, 0);
        vector<short> row(9, 0);
        // use bit to record the 1-9 that already appeared
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int idx = 1 << (board[i][j] - '0');
                    if (row[i] & idx || col[j] & idx || block[i/3 * 3 + j / 3] & idx)
                        return false;
                    
                    row[i] |= idx;
                    col[j] |= idx;
                    block[i/3 * 3 + j/3] |= idx;
                }
            }
        }
        return true;
    }
};

interviewee

OK,finish,Could you have any concern?

$i n t e r v i e w e r$

I think this is the good method,that's today's interview,thanks for your cooperation.

初步檢討

回答問題時停頓太久。
語速稍稍有點慢。
語助詞有點多。
英文真的有夠卡，需要多練口說。
註解幾乎沒有，雖然有以口頭表示配合畫code線，但是還是得有註解，以保證思路清楚。
interviewer、interviewee口條皆不夠清晰。
interviewer需要以線上共用檔案，用文字清楚表示題目。
雖然使用了vscode，但其實這在實際code面試上太理想了，不太可能出現。
承上，也導致了測試資料橋段不切實際。
暱稱有刻意暴雷的嫌疑, 十分不妥
面試官是interviewer不是interviewee
Q1, Q2都已經有exe檔了是怎麼回事

改善方法

下意識控制語助詞一段時間，盡量讓洗鍊的用詞成自然。
可將思考方向先當作註解寫在程式上，減少混淆也能解釋程式，寫清楚才能講明白。
需多練習英文口說。
用word寫，人肉debugger

他評-01

ps :　名字取的不錯

interviewer

優點

7:50: 引導interviewee往特定方想思考

interviewee

優點

程式碼說明很清楚，有條理的敘述這段程式的作用

可改進之處

在coding時，可以將題目寫成function，main只做呼叫及測試

第二次作業 - 他評 02

interviewer

優點

題目陳述清晰

可改進之處

7:09 Interviewer應該避免直接問Interviewee時間(空間)複雜度等，容易流於制式化的問答。如果想考驗相關想法，應該等Interviewee實作完程式碼還是沒有提到時，再以其他方式詢問並啟發思考是否能再更精進。
Interviewer話有點少，也許可以試著加入質疑的地方。例如:Two Sum對方提出使用map實作的想法，可以順便問他map內部是用什麼資料結構實作
延伸閱讀:C/C++ MAP
覺得似乎整體音量偏小

interviewee

優點

針對題目的Repeat和Example很清楚詳細，有確實掌握題意
test和optimize的部分做的很確實
邊寫code邊講解的很清楚
有跟interviwer互動確認題意

可改進之處

應用 Google docs 而不是用編輯器
應該向interviewer確認可以使用的語言
02:10: 建議在講解Approach的時候，可以通過舉例(或是用小畫家?!)，來讓interviewer更清楚你的想法
若有時間可以適當註解
是否可以簡單交代一下時間複雜度

第二次作業 - 他評 03

其它可改進

不應用有intelli sense的編輯器 => 沒auto complete，error detect、warning才是見真章的時候
影片畫質有點感人
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
169-Majority-Element 影片闕失

interviewer

優點

沒有直接給題目，而是使用口述的方式，可以很好的避免刷題怪
有讓interviewer分析時間復雜度

可改進之處

測試資料太少容易有意想不到的bug出現

interviewee

優點

有跟interviewer確定猜想
TwoSum有維持clean code 有把搜尋提出去寫，同時也沒用auto來接可見的對STL type的熟悉

可改進之處

TwoSum那題可以用unordered_map –> O(1)取代map –> O(logn)，測試資料一旦大幅增加則執行時間差異顯著，所以在確定沒有用到map裡的順序iterator情況下可改用unordered_map
英文coding時有一部分沒講解處於沉默狀態

第二次作業 - 他評 04

interviewer

優點

不應該提供具有 auto complete 的 IDE，透過無到有的建構過程也容易看出interviewee對於該語言的熟悉程度。

可改進的地方

英文題在講解的時候沒有任何畫面以及文字，只是單純地一直用口說，過程如果沒有中斷一下並詢問interviewee的狀況的話很容易說完之後還是要重新講解一次。

interviewee

優點

每次寫題目的時候都有一個測試資料顯示在IDE上，並且在建構程式碼的過程中也能夠將滑鼠移動到測試資料上中途講解一下，很容易幫助理解演算法的邏輯。

可改進的地方

寫code的時候要注意排版，不應該有些operand跟operator中間有間隔，但有一些沒有，看了有點強迫症發作。

第二次作業 - 他評05

Interviewer

優點

說話清晰。

可改進之處

Google Meet 帳號會將你的名字顯示在頭貼唷><

Interviewee

優點

有先丟出例子確認問題。
有先說明大概會怎麼實作，並口頭 go through 一遍確認邏輯無誤後才進行實作。
邊實作邊說明程式碼。
有詳細解釋到 code 的邏輯，能從中看到其撰寫程式碼的嚴謹程度。

可改進之處

不需要整個 code 很詳細的寫出來，可以寫個 function 來回答即可

第二次作業 - 他評06

Interviewer

優點

表達相當清楚

可改進之處

若能跟Interviewee有更多互動會更好

Interviewee

優點

REATO做的相當完整
在書寫程式碼的過程中有搭配很詳細的解釋

可改進之處

最後問Interviewer：「有任何問題嗎？」有點奇怪

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

1. Two Sum

interviewer

interviewee

interviewer

interviewee

interviewer

interviewee

interviewee

interviewer

interviewee

interviewer

interviewee

interviewee

interviewer

interviewee

169. Majority Element

interviewer

interviewee

interviewer

interviewee

interviewer

interviewee

interviewer

interviewee

interviewee

interviewer

interviewee

interviewer

interviewee

interviewee

interviewer

36. Valid Sudoku

interviewer

interviewee

interviewer

interviewee

interviewer

interviewee

interviewee

interviewer

初步檢討

改善方法

他評-01

interviewer

interviewee

第二次作業 - 他評 02

interviewer

interviewee

第二次作業 - 他評 03

interviewer

interviewee

第二次作業 - 他評 04

interviewer

interviewee

第二次作業 - 他評05

Interviewer

Interviewee

第二次作業 - 他評06

Interviewer

Interviewee

Read more

運用 Perf 分析程式效能並改善

你所不知道的 C 語言：動態連結器篇

Linux 核心專題: 虛擬無線網路裝置驅動程式

資訊科技詞彙翻譯

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$

$i n t e r v i e w e r$