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

貢獻者: 奧黛麗-Audrey
video:
模擬面試影片(漢)
模擬面試影片(英)
R: Interviewer
E: Interviewee

1. Two Sum

測驗說明與問答

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

R: 在第一道題目中，會給你一個整數陣列以及一個目標值。請你在這個整數陣列中，找出兩個整數相加要等於題目給定的目標值，而答案就是要以陣列的形式，回傳你找到這兩個整數的索引值。你可以假設一組輸入就恰好會有一組答案，而且陣列裡的元素不會重複使用。

E: 想請問這個陣列是排序過的嗎？

R: 不是。

E: 我想我沒有問題了。但為了確認我對題目的理解是不是正確的，我想舉個例子。假設題目輸入的陣列是 [2,13,9,1]，目標值是3，這樣要回傳的答案就 [0,3] 對嗎？

R: 沒錯。

E: 我目前比較直覺的想法是用雙層的for迴圈來實作。第一層迴圈是找第一個數字，第二層迴圈去找要相加的第二個數字，最後把整個陣列走過一次，就可以得到所有相加的可能組合，在過程中只要得到答案就直接回傳。

• With nested loop

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

R: 程式是沒有問題，但很明顯，雙層迴圈對於時間複雜度而言，並不是很有效的做法，針對這點你有什麼想法嗎？

E: 如果是要降低時間複雜度的話，我想可以用hash table來實作，針對每一個元素建立一個hash table，去存他們的index，之後再用一個for迴圈去算目標值和原本陣列的每一個元素相減得到的差，如果存在於這個hash table中，就代表找到解了；這個方法實作起來就是兩個單層的for迴圈，將時間複雜度從原本的

$O(n^2)$ 降低到

$O(n)$。

• With hash table

vector<int> twoSum(vector<int> &nums, int target)
{
    vector<int> ans;
    unordered_map<int, int> mp; // (element:index)

    for (int i = 0; i < nums.size(); i++)
        mp[nums[i]] = i;

    for (int i = 0; i < nums.size(); i++)
    {
        int left = target - nums[i];
        if (mp.count(left))
        {
            ans.push_back(i);
            ans.push_back(mp[left]);
            return ans;
        }
    }
    return ans;
}

48. Rotate Image

測驗說明與問答

R: 因為我們公司有做一些影像處理的案子，所以這題是關於影像的應用。我自己很常在拍一些證件或文件的時候，忘記把手機轉正，之後的後製就需要來旋轉拍好的照片。所以接下來的題目主要就是想模擬一下旋轉影像的過程，我剛有把示意圖放在google文件的第二頁，我們會給你一個matrix，希望你能將這個用來模擬影像旋轉180度。

E: 根據我的觀察，若是要做180度的旋轉，其實只要針對column跟row都各做一次反轉就好。像是先在每一個row做反轉的話，就會變成[[3,2,1],[6,5,4],[9,8,7]]，之後再對column做反轉就會達到題目要求的[[9,8,7],[6,5,4],[3,2,1]]

• 旋轉180度

void rotate(vector<vector<int>> &matrix) // 180 
{
    for (int i = 0; i < matrix.size(); i++)
        reverse(matrix[i].begin(), matrix[i].end());
    reverse(matrix.begin(), matrix.end());
}

R: 如果是要將影像順時針轉90度的話，你會怎麼做呢？

E: 先將矩陣轉置，之後針對每一個row裡面的元素reverse，就能達到順時針旋轉90度。以原圖為例，原本的[[1,2,3],[4,5,6],[7,8,9]]經轉置後會變成[[1,4,7],[2,5,8],[3,6,9]]，之後在每個row做reverse，得[[7,4,1],[8,5,2],[9,6,3]]。

• 旋轉90度

void rotate(vector<vector<int>> &matrix)
{
    for (int i = 0; i < matrix.size(); i++) // transpose
    {
        for (int j = 0; j <= i; j++)
            swap(matrix[i][j], matrix[j][i]);
    }

    for (int i = 0; i < matrix.size(); i++) // reverse in each row
        reverse(matrix[i].begin(), matrix[i].end());
}

R: 恭喜你完成今天的面試，後續有任何消息，我們同仁會再通知你，期待下次再見。

169. Majority Element

測驗說明與問答

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

R: Any questions?

E: Is the array sorted?

R: No.

E: My initial approach is to use hash table to record the number of times of each element appears.

• With hash table

int majorityElement(vector<int> &nums)
{
    int n = nums.size();
    unordered_map<int, int> mp;
    int ans, cnt = 0; // ans: majority element

    for (int i = 0; i < n; i++)
    {
        mp[nums[i]]++;

        if (mp[nums[i]] > cnt)
        {
            cnt = mp[nums[i]];
            ans = nums[i];
        }
    }
    cout << ans << endl;
    return ans;
}

R: It's a nice solution. However, I hope you can reduce the space complexity. Could you solve the problem in O(1) space?

E: To reduce space complexity, I will sort the array first. Since the majority element always exists, and according to the definition, it appears more than the floor of (n/2) times, the middle of the sorted array must be the majority element. In this solution, the space complextity will be O(1).

R: Good, it fulfills the requirement. However, it seems like a trade-off between space complexity and time complexity. Do you have another solution to keep the time complexity in linear time when you reduce the space complexity?

E: I have come up with the concept of Moore Voting. In this solution, two variables, candidate and count, are required. First, choose the first element as candidate and iterate through the list. For each item, check if it's the same as the current candidate. If it is, increment the count; if not, decrement the count. When the count reaches zero, just update the candidate to the current item. After iterating through the entire list, the candidate will hold the majority element if it exists.

• Moore Voting

int majorityElement(vector<int> &nums)
{
    int candidate, cnt = 0;
    for (int num : nums)
    {
        if (cnt == 0)
            candidate = num;
        if (num == candidate)
            cnt++;
        else
            cnt--;
    }
    return candidate;
}

R: Good job! I think we have finished our interview today. Thanks for your time and hope to see you again!

初步檢討

• 連接詞有太多「那」
• 題目沒有善加包裝，太容易讓interviewee猜到想要幹嘛（我只知道要包裝但不知道怎麼包裝QAQ）
• 寫程式的時候講話會弱掉、變模糊
• 習慣中英混用（如索引值/index）
• 打字速度太慢又太容易打錯
• 英文2:40的錯到3:58才發現，應該要打完一小段就檢查一下

---

第二次作業-他評01

interviewer

• 優點

• 能藉由公司所面對的問題延伸至面試的提問

• 可改進的地方

• interviewer可以將公司遇到的問題帶入題目來敘述會更好
• 考驗其他做法時應該先描述更改後會帶來的結果
• 少了test的部分

interviewee

• 優點

• 解釋approach的方式很有條理，讓人很好理解
• 英文的部分很流利

• 可改進的地方

• 09:41: 若有能夠適用旋轉各種角度的方式可能會更方便實作

他評02

• 優點

• 第二題有用情境題
• 英文好聽
• 文件有用粗體標註重點我覺得很棒🤣

• 可改進的地方

• 第一題可以用情境帶入
• 第二題舉出任意角度(90, 180, 270, …)的旋轉會更好。
• 第三題interviewer可以質疑interviewee為什麼要用hash table
• 第三題可以再延伸如果majority number不是每次都會存在那要怎麼解決。

他評 03

關於 interviewer

• 優點

• 有重複確認面試者有無問題，問答過程舒服會讓人沒那麼有壓力。
• 英文好好聽!
• 9:00: 有帶入情境題來問問題。

• 可改進的地方

• 第一題可以用情境帶入的方式來提問。
• 3:58: 除了時間複雜度，面試官可以請面試者用除了hash table之外的方式解此題。

關於 interviewee

• 優點

• 畫面清晰明瞭。
• 講解時語速也不會忽快忽慢的。

• 可改進的地方

• 沒有做REACTO中的testing部分。

他評 04

interviewer

• 開始時有詢問是否成功打開連接，很有臨場感
• 有在引導interviewee如何改進

interviewee

• 優點

• 舉例易懂

• 可改進之處

• 有時聲音會變小

他評 05

• 針對 169. Majority Element，這題目暗示可用投票法 (過半元素出現的次數比其他所有元素的次數之和還多，所以最後保留下來的候選元素必定是過半元素)，這只能用於確保陣列 majority element 一定超過陣列大小的一半，如果是要找出現次數最多的則不適合。
• 0:40: 這裡的 "Other questions?" 太突兀，應該先舉例說明，而且 "other" 暗示之前已有問題，但顯然在這場景不存在。
• 0:47: 當 interviewee 提問 "Is the array sorted?"，除了回覆 "No, it is not sorted."，可帶入實際場景來說明，例如 "You can think of the data distribution as an election, where some people vote for the majority candidate, and others don't. The array represents the original voting data."
• 3:58: 不該急著說 "It's a nice solution"，畢竟你沒說到底好在哪裡。

他評 06

interviewer

• 有認真引導 interviewee

interviewee

• 優點

• 與 interviewer 有良好的對話互動。
• 英文講得很好，不太需要看翻譯都能聽懂。
• 語速均衡，講話起伏也很讚，給人有精神的感覺。

• 可改進之處

• 忽然會變小聲。