2021 年「資訊科技產業專案設計」課程第 5 次作業

[interviewee] Move Zero To End

Question description

Given a static-sized array of integers arr, move all zeroes in the array to the end of the array. You should preserve the relative order of items in the array.

We should implement a solution that is more efficient than a naive brute force.

Examples:

input:  arr = [1, 10, 0, 2, 8, 3, 0, 0, 6, 4, 0, 5, 7, 0]
output: [1, 10, 2, 8, 3, 6, 4, 5, 7, 0, 0, 0, 0, 0]

Constraints:

• [time limit] 5000ms
• [input] array.integer arr
  • 0 ≤ arr.length ≤ 20
• [output] array.integer

Solution

• p1 指向 0 的位置，為下個應該要被設置非零數值的位置
• p2 指向非 0 的位置，為下個 p1 位置應該要設置的數字

持續交換 p1 及 p2 即可得到答案

vector<int> moveZerosToEnd(const vector<int>& arr)
{
    int p1 = 0;
    vector<int> ans = arr;
    for (int p2 = 0; p2 < arr.size(); ++p2) {
        if (ans[p2] != 0) {
            swap(ans[p1], ans[p2]);
            p1++;
        }
    }
    return ans;
}

Time complexity: array 中每個 index 最多只會看到一次，複雜度為

$O(n)$
Space complexity: 需要記錄回傳的陣列，複雜度為

$O(n)$

Self-Criticism

• 聽不懂 interviewer 想表達的意思
• 急著想把想法寫出來，沒注意到有更簡潔的方法
• 無法把想法準確地用英文表達出來
• 沒注意到題目細節 (arr is const type)
• 聲音太小

Feedback

• 思考的時候一直沉默，讓 interview 不知所措

這題其實很簡單而且以前有做過，但當下太緊張且一直嘗試理解 interviewer 所說的話，應該要與 interviewer 溝通並請她給我點時間思考。

[interviewer] Merging 2 Packages

Question description

Given a package with a weight limit limit and an array arr of item weights, implement a function getIndicesOfItemWeights that finds two items whose sum of weights equals the weight limit limit. Your function should return a pair [i, j] of the indices of the item weights, ordered such that i > j. If such a pair doesn’t exist, return an empty array.

Analyze the time and space complexities of your solution.

Example:

input:  arr = [4, 6, 10, 15, 16],  lim = 21

output: [3, 1] # since these are the indices of the
               # weights 6 and 15 whose sum equals to 21

Constraints:

• [time limit] 5000ms
• [input] array.integer arr
  • 0 ≤ arr.length ≤ 100
• [input] integer limit
• [output] array.integer

Solution

def getIndicesOfItemWeights(arr, limit):
    seen = {}
    for i, val in enumerate(arr):
    if limit - val in seen:
        return [i, seen[limit - val]]
        
    seen[val] = i

    return []

Time complexity: 遍歷整個 array，複雜度為

$O(n)$
Space complexity: 利用 hash map 紀錄每個 index 及 value，複雜度為

$O(n)$

Self-Criticism

• 講的英文有時候讓 interviewee 聽不懂