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

貢獻者: 追光者-Aegleseeker
video:
模擬面試影片(英)
模擬面試影片(漢)

圖示 :
: interviewer
: interviewee

2605. Form Smallest Number From Two Digit Arrays

: Hello, I'm a senior engineer in this company. I'll just share a doc for you, then we can get started.

: In this problem, you have been given two arrays of unique digits nums1 and nums2, and you are required to return the smallest number that contains at least one digit from each array.

For instance, assume the input of both arrays nums1 and nums2 be:

nums1 = [4,1,3], nums2 = [5,7]

Then, the output should be 15, since it contains the digit 1 from nums1 and the digit 5 from nums2, and its a smallest number for all combinations.

: That's all the problems about. You can start your work.

: To fully understand the problem, I'll want to ask a question. The problem state that the digits in both arrays are unique, so the arrays wouldn't contain duplicate elements, respectively ?

: Indeed.

: I see.

: I'll want to ask another question.

Assume the input to be

nums1 = [2,3,4], nums2 = [1,2,3,4,5,6]

Then, the output should be 2, since it's both in nums1 and nums2, and its the smallest number for all combination. Am I correct ?

: Yeah, I beleive that your assumption is right.

: All right. Before starting to code, I'll first share my thoughts on it with you.

: For this problem, my initial thought is to use hash maps to save the digits exist in both arrays. Using C++ as example, I'll declare two vectors with 10 usable spaces to save the digits in both arrays, respectively, for the sake of checking if there's any digits contain in both arrays. On top of that, I'll declare three integer variables to represents the minimun numbers in both arrays, and the minimum numbers in both arrays if it exists while saving the digits in both arrays in to hash maps.

: Sounds good, can you change your thoughts into code ?

: Sure.

int minNumber(vector<int>& nums1, vector<int>& nums2) {
    vector<int> hash1(10, 0), hash2(10, 0); 
    int min1 = INT_MAX, min2 = INT_MAX, min_all = INT_MAX;

    for (auto &i: nums1) 
    {
        hash1[i]++;

        if (min1 > i)
            min1 = i;
    }


    for (auto &i: nums2)
    {
        if (hash1[i] && min_all > i)
            min_all = i;

        hash2[i]++;

        if (min2 > i)
            min2 = i;
    }

    if (min_all < 10)
        return min_all;
    else if (min1 > min2)
        return (min2 * 10) + min1;
    return (min1 * 10) + min2;
}

: To test the correcness of this piece of code, taking the I/O that I mentioned before as example, the output of these two arrays will be 2. Moreover, since I use hash map to implement it, it only costs linear time to process the datas.

: Despite the fact that it is efficiency in times complexity, in reality, if we want to process large amount of datas, we might not have that much of memory spaces for you to implement multiple hash maps. Can you try to reduce its memory usage ?

: Well, you're right. I should try to reduce the memory usage of it.

: I come up with an idea to implement it with one hash map.

int minNumber(vector<int>& nums1, vector<int>& nums2) {
        vector<int> hashMap(10, 0); 
        int min1 = INT_MAX, min2 = INT_MAX, min_all = INT_MAX;

        for (auto &i: nums1) 
        {
            hashMap[i]++;
            
            if (min1 > i)
                min1 = i;
        }
            
        
        for (auto &i: nums2)
        {
            if (hashMap[i] && min_all > i)
                min_all = i;
            
            hashMap[i]++;

            if (min2 > i)
                min2 = i;
        }

        if (min_all < 10)
            return min_all;
        else if (min1 > min2)
            return (min2 * 10) + min1;
        return (min1 * 10) + min2;
    }

: If the size of data will cost much space in this program, this implementation would turn out to be like half of memory usage of the first implmentation.

1827. Minimum Operations to Make the Array Increasing

: 您好，我是這間公司的工程師，接下來的時間由我來幫公司的同事來面試您的能力是否為我司所需要。

: 我已經將測試題貼在了共享文件中。在這個情境中，您會被給予一組整數型態的一維陣列。在每一次的操作中，您可以選擇一個陣列中的元素將其加一。舉例來說的話，如果有一組陣列 nums 為 [1, 2, 3]，您可以選擇將 nums[1] + 1，使得陣列 nums 變為 [1, 3, 3]。您在這個情境的最終目的是：求出一個能將輸入的陣列元素變成嚴格遞增的最小操作數。

: 舉個例子來說，我們假設輸入的陣列為

nums = [1,1,1]

您的答案應該要是

3

因為您可以做以下操作：

將 nums[2] 加一
將 nums[1] 加一
將 nums[2] 加一

: 以上就是這次測試您的情境說明。接下來就交給您發揮了。

: 我想先問一個問題，請問陣列裡面的元素會有負數嗎 ？

: 就這題而言的話，沒有。

: 在開始之前，我想先舉一個例子，來確認我對題目的理解。

假設陣列 nums 為

nums = [1,5,2,4,1]

那就我的理解來說，我得到的結果應該是

14

: 嗯，以您的例子來說，結果確實會是 14。

: 我大概了解了。那接下來我先闡述一下我預計的作法。在這題中，我會使用貪婪法的來實做它。具體的流程是對每個陣列中的元素做迭代，且在每一次的迭代中，我會將其和後一位的元素做比對。如果後一位的元素比現在迭代到的元素來的小或相同的話，我將它和現在的元素做相減並加一，得到這次迭代中，將後一位元素的數值超越現在的元素的數值所要做的最小操作次數。而這些每次迭代中所計算出來的最小操作次數，我會用一個整數變數 result 來去儲存並總合它。在迭代完所有陣列的元素後，就可以將 result 回傳出去。此方法做出來的話是常數時間的複雜度，且空間複雜度為 O(1)。

: 聽起來不錯，你可以將它轉換成程式碼並驗證正確性嗎 ？

: 沒問題，在這裡我會用 C++ 去實作它。

int minOperations(vector<int>& nums) {
    int result = 0;

    for (int i = 0 ; i < nums.size() - 1 ; i++)
    {
        if (nums[i] >= nums[i + 1])
        {
            result += (nums[i] + 1) - nums[i + 1];
            nums[i + 1] = nums[i] + 1;
        }
    }

    return result;
}

此方法做出來的話是常數時間的複雜度，且空間複雜度為 O(1)。

1658. Minimum Operations to Reduce X to Zero

: 剛才您的做法確實蠻有效率，且沒佔用到神空間，很好。還有點時間，那麼接下來，這裡還有另一個測試要您完成。

: 在我們公司中，我們有一個蠻重要的服務。該服務的大致內容是：我們的產品用戶會給我們一組他們需要的商品組合，而我們的系統會從資料庫中選出一組符合客戶需求的最低價組合，以提供用戶高 CP 值的選擇。因此，下一個測試會跟該服務的實作有點關聯。

我們把問題簡化一下，你會被給予一組整數型態的一維陣列和一個整數 x。

我們定義程式操作一次為：取除一個能夠將 x 削減，且為此陣列中最左或最右的元素。

你的最終目的是：回傳一個能夠將 x 削減為零的最小操作次數。如果這個操作不存在，回傳 -1。

: 舉例來說，我們假設輸入的陣列和整數值 x 為

nums = [1,1,4,2,3], x = 5

你的答案應該要是

2

因為你可以直接削掉陣列中最後兩個元素，使得 x 為 0。

: 以上就是這次測試題的說明。接下來把時間交給您了。

: 為了驗證我是否知道這個題目在講什麼，我舉一個例子來問您我的想法是否正確，假設一個輸入的陣列和變數 x 為

nums = [3,2,20,1,1,3], x = 10

我所得到的答案應該要是

5

也就是削掉最左的兩個元素以及最右的三個元素，使得 x 為 0。

: 是的，你應該有抓到他的意思。

: 我還要額外再提一個問題，請問輸入的陣列的長度大概範圍是在哪？

: 以現實情況來算，通常都會超過 10⁵ 或以上。

: 好…。喔，我有一個想法，在這個情況下，我會想使用 prefix sum 和 suffix sum 來總和出每個最左和最右的元素集合，並配合 hash map 存儲每次 prefix sum 和 suffix sum 得來的總和的方式來完成。

: 具體實作起來會變成以下模樣:

int minOperations(vector<int>& nums, int x) {
    int n = nums.size(), prefix = nums[0], ans = INT_MAX;
    unordered_map<int, int> hash_map = {{prefix, 0}};

    /* prefix sum */
    for (int i = 1 ; i < n ; i++) 
    {
        prefix += nums[i];

        if (prefix > x)
            break;

        /* insert the result of every prefix sum*/
        hash_map[prefix] = i;
    }

    if (hash_map.count(x))
        ans = hash_map[x] + 1;
    
    /* suffix sum */
    for (int i = n - 1 ; i >= 0 ; i--)
    {
        x -= nums[i];

        if (x < 0)
            break;

        if (x == 0)
            ans = min(ans, (n - i));

        int index = hash_map[x];
        if (hash_map.count(x) && (index = hash_map[x]) < i)
            ans = min(ans, index + 1 + (n - i));
    }

    if (ans < INT_MAX)
        return ans;
    return -1;
}

這樣的話，我們的時間複雜度會是 O(n)，因為我們只有做兩個一層迴圈的關係。除此之外，由於要構建 hash map 的關係，所以空間複雜度為 O(n)。

: 您的這個方法的時間效率是還不錯啦。但是我更希望您能把空間的使用效率增加到 O(1)，因為不是我們每次都有這個空間給您建立 hash map。

: 縮小空間複雜度嘛，能給點提示嗎。

: 您使用 prefix sum 和 suffix sum 的想法其實已經沾到邊了，但我不覺的您需要記住所有的總和。請記住，您只要削掉最左或最右的元素就好。

喔，這倒是讓我想起了一種方法，這個方法有點類似快慢指標的實作方案。具體還說就是宣告兩個左右指標，而這兩個左右指標會藉由對每個陣列元素迭代的方式向右移動，到最後會形成一個 window。而這個 window 就是我們要留下的陣列元素，剩下的都要被削掉。

我用程式碼來將它具象化：

int minOperations(vector<int>& nums, int x) {
    int total = 0;

    for (int n: nums)
        total += n;

    int ans = -1, curr = 0, n = nums.size();
    for (int left = 0, right = 0 ; right < n ; right++ )
    {
        curr += nums[right];
        while (left <= right && curr > total - x)
            curr -= nums[left++];

        if (curr == total - x)
            ans = max(ans, right - left + 1);
    }

    if (ans != -1)
        return n - ans;
    return -1;
}

從程式碼中您可以發現，時間複雜度和我的上一個方法一樣，依舊是 O(n)。但是，由於我沒有在這函式中新增陣列或 hash map 等其他資料結構，因此空間複雜度也被優化到了趨近於 O(1)。

: 這新的方法確實有好很多。好了，時間也差不多了，這場面試就到這裡吧，感謝您的參與。

他評01

優點

• 英語口說超讚，抑揚頓挫和清楚的咬字讓人容易聽懂。
• 邊撰寫程式邊解說，沒有冷場，good！
• interviewee 有清楚確認提議後，再開始實作。
• interviewee 會主動跑 testcase 做驗證。
• 中文面試 19:52 interviewer 提出的應用場景還不錯。

可改進的部分

• 英文面試 7:37 interviewee 在相同位置重複點滑鼠、反白的次數應減少，反白一次就可以了，不然有點小煩躁。
• 英文面試 17:12 敲鍵盤的聲音有點大。
• 英文面試 20:08 建議 interviewee 在跑 testcase 時, 如果有多個步驟需要逐一講解，可以將每個步驟的結果都留著，參數寫清楚，不要覆蓋掉，避免太多的指標移動或反白，interviewer 才不會頭暈 XD
• 中文面試 7:02 interviwee 提到使用迭代去比較每個元素，那時間複雜度應該要是
  $O(N)$，而不是常數時間複雜度 (
  $O(1)$)
• 中文面試 40:19 interviewer 說 "您剛才的做法有點沾到題目的邊了"，比較有考官、只有一種答案是正解、上對下的感覺，建議可以用相互討論的方式，比較部會給 interviewee 壓力，可以改成說 "我想要在 XX 方面多做改進，你有什麼想法嗎?"

他評02

優點

interviewer

• 講話清楚，速度適中
• 19:15 說"還有一點時間"，很有臨場感，並有代入公司實際案例

interviewee

• 2:24 有確認題意，並完整的描述預計使用的方案
• 8:15 coding的過程有清楚表達程式碼的意義
• 13:40 提出例子，並代入程式碼驗證

可改進的部分

• 18:00在敘述時手部的動作有點多，線上會議上用手來輔助也很難讓別人更好的理解你表達的東西