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

貢獻者: 布撥(Pawmi)
影片-1
影片-2
影片-3
🐯: interviewer
🦝 : interviewee

88. Merge Sorted Array

模擬面試過程

🐯: 布撥先生你好，歡迎來到本公司，本次面試為coding interview ，我們有一些問題想與你討論，在過程中如果對問題有任何的疑問，都可以提出。如果你準備好就可以開始了。
🦝 : 好的，我可以開始了。

🐯: 首先是關於數據合併的問題，在處理公司後台系統的客戶數據時，我們經常需要將不同子系統中的相同類型數據進行整併，並希望在整併完成後，數據依然維持順序或逆序排序。假設我們有兩組來自不同子系統的整數陣列 nums1 與 nums2，兩者都為遞增排序，其中nums1有m個整數，而nums2有n個整數，我們需要將兩個陣列進行合併，並維持它們的遞增排序，請問你會如何解決此問題呢。

🐯: 補充說明，我們希望最終合併的結果直接儲存在nums1陣列中，因此我們已經將nums1陣列擴增至能含括所有數據的長度，即 m + n ，擴增的部分由整數0填充。

🦝 : 好的，我想先舉一例子，來確認我對題目的理解。

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

🦝 : 請問我的舉例正確嗎?

🐯: 正確，你可以提出解決方案了。

🦝 : 好，那我會透過python來撰寫我的程式碼。因為num1陣列已經先擴充到目標的長度了，所以我會先將nums2的數據先複製到nums1的後n個索引位置，然後再對整個nums1陣列進行排序，使nums1儲存我們期望的結果。

解法 1

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:

        if n > 0:
            nums1[-n:] = nums2.copy()
            nums1.sort()

🐯: 你的程式碼很精簡，且也能夠正確的達到我們的需求，但一開始我有提到，nums1與nums2兩個陣列在合併前已經完成了遞增排序，你的方案是否能將這個特性進行利用呢?

🦝 : 了解，我先前的方法忽略了這個重要的性質，因為陣列已經排序過了，所以可以透過兩個索引值逐步比對兩陣列中的數值大小，並透過另一個索引值將較大的數值填入num1中正確的位置。

解法 2

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:

        a = m-1
        b = n-1
        l = m + n -1
        while b>= 0 :
            if a >= 0 and nums1[a] > nums2[b]:
                nums1[l] = nums1[a]
                a-= 1
            else :
                nums1[l] = nums2[b]
                b-= 1

            l-= 1

🦝 : 這樣的改進可以避免再次進行排序，原本排序的時間複雜度為O(NlogN)，現在我們只需要對兩陣列逐一進行比對，解決方案的時間複雜度進一步改進到O(N)

初步檢討

電腦老舊導致OBS擷取麥克風音訊會有雜音，需要更新設備。
面試官在面試者完成程式改進後應該要給予一些反饋。
面試官說明題目時過度僵硬，像在念稿。
面試者在撰寫完程式後可以適度透過範例解釋運作流程。
面試者在解說改進解法時說明不清，用詞需要再明確一點。

他評01

優點

撇除雜訊的部分，聲音很清晰。
程式碼簡潔有力。

可改進地方

interviewer可以引導interviewee說明自己要怎麼實作，而不是馬上進入程式碼撰寫的部分。
interviewee撰寫程式碼時，可以邊說自己要做什麼然後編寫，而不是寫好了以後再開始解說做了什麼。
講話有適時的停頓和抑揚頓挫會讓人更清楚想表達的內容與重點。

他評02

優點

咬字清晰，表達也很清楚。
interviewee 再面試過程中沒有甚麼多餘的動作，有助於 interviewer 專注聆聽。

可改進地方

6:51: interviewer 的提示有點太明顯了，感覺可以再間接一點，比如說: 你的程式碼的時間複雜度目前是
$O (N \log N)$ ，如果我想要速度更快，你有甚麼想法嗎?
9:51: interviee 雖然在 coding 前有講過大致的想法了，但距離程式碼撰寫完，時間間格有點久，怕會忘記，建議在講解程式碼前可以再次提及大致的想法，讓人一開始就聽懂為甚麼要設置 a, b, l 這些變數，或是邊 coding 邊講解。

他評03

優點

講話清晰，有語調變化
面試對話完整

可改進地方

雜訊有點多
6:51: 提到題目給定的是sorted array，應該要注意這項資訊，第一次實作就應該以針對sorted array的解法進行
撰寫程式時應適當加入註解與解說

189. Rotate Array

模擬面試過程

🐯 : 接下來同樣是關於陣列數據的處理，假設我們有一個整數陣列nums，要將它向右旋轉k步，請問你會如何設計解決方案呢?

🦝 : 我想先確認一下，向右旋轉的定義是什麼呢?

🐯 : 類似讓數據在固定的資料結構裡循環的概念，假設我想讓陣列向右旋轉1步，完成後陣列中的數值都會向後位移一格，而最後一個數值則會回到陣列的開頭。

🦝 : 我了解了，讓我舉例來說。

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]

🦝 : 我這樣的舉例是正確的嗎?

🐯 : 對的，你可以開始規劃解決方案了。

🦝 : 我想透過複製陣列的方式解決這個問題，首先我先複製nums陣列，將nums陣列長度定義為l ，並將l減掉k個的數值依序append到複製的陣列後面，最終複製陣列的後面l個數值即為我們的目標值，需要特別注意當k等於l時，代表陣列旋轉循環了一圈，因此我們在實際操作時，其實只要旋轉k除以l的餘數即可。

解法 1

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:

        if k > 0 :
            l = len(nums)
            k = k % l
            nums2 = nums.copy()
            for i in range(l-k) :
                nums2.append(nums2[i])
            nums[:] = nums2[-l:]

🐯 : 你可以再提出一組範例來驗證方法的有效性嗎?

🦝 : 好的，我們來測試當旋轉步數多於陣列長度時的狀況。

Input: nums = [1,2], k = 3
Output: [2,1]

🐯 : 的確都能夠正確的達到需求。接下來我們加上一些額外的設定，來進一步討論程式效率改進的可行性；如果我們的解決方案需要佈署在記憶體空間極度有限的裝置上，要求in-place的解決該問題，你會如何改進你的方案呢?

🦝 : 原本的方法中複製了nums陣列並透過append來逐步添加元素，但只要我們事先計算出陣列中的那些元素在旋轉之後會被位移到前半段，那些部分會位移到後半段，我們就能夠透過反轉的方式，得到我們的目標。

解法 2

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:

        l = len(nums)
        if k == l : 
            return 
        k = k % l
        nums.reverse()

        for i in range (k//2):
            nums[i] ,nums[k-1-i] = nums[k-1-i],nums[i]
        for i in range(k,(l+k)//2):
            nums[i] ,nums[l-1-i+k] = nums[l-1-i+k],nums[i]

初步檢討

太常使用"那"等奇怪的贅詞作為語助詞。
在解釋解法一時沒有說清楚何謂"依序"進行Append。
再實作改進的解法二前，或許能先使用例子解釋為何該作法可行，而非先寫完程式再代入數據解釋，很像預先背誦答案，而非思考所得。
面試官應該給予多點不同性質的方案評論，而非只說好或不好、正確與否。

他評01

優點

詢問向右旋轉是什麼來增加互動和深入了解提議很棒。
提出範例驗證程式碼。

可改進地方

解法1如果將nums和nums2串接然後right shift k個後直接回傳nums2，可以降低時間複雜度。因為shift的時間複雜度是O(1)而for loop則是O(n)。
解法2舉例為什麼可用reverse更容易讓人理解。

他評02

優點

6:16, 12:11 interviewee 提出例子並逐步講解，同時將每個階段性的結果 show 出來很讚，清楚表達演算法的運作流程。
8:30 interviewer 帶入的應用情境還不錯。

可改進地方

小小建議，也許可以再改進，不要求 in-place，但求更快的速度。做法直接使用 slice 來取後半段跟前半段並接在一起。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k = k % len(nums)
        nums[:] = nums[-k:] + nums[:-k]

他評03

優點

面試官與受試者互動良好
遵循REACTO
有提出test case，說明清晰

可改進地方

前判斷可以不必使用迴圈，可以直接使用nums[-k:]

108. Convert Sorted Array to Binary Search Tree

模擬面試過程

🐯 : For the next part, I'd like to discuss in English with you.

🐯 : When dealing with data, we often need to transform it into data structures that are more suitable for retrieval. A height-balanced binary search tree is one such structure. Given an integer array nums where the elements are sorted in ascending order, you need to convert it to a height-balanced binary search tree.

🦝 : How should I represent the structure of the tree in my solution?

🐯 : Your function needs to be able to convert the array data into a tree structure and return the root of the tree. The interface for using your designed function will output values using the BFS algorithm.

🐯 : You can use this structure for implementation.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

🦝 : For example:
For this input, I need to create a height-balanced binary search tree like this

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]

🦝 : Is my understanding correct?

🐯 : Correct, you can start designing your solution now.

🦝 : I'd like to solve this problem using recursion. Since the array nums is already sorted, for a height-balanced BST, the value of its root is the median of all the node values. So, we can create a build function that takes the middle index value (half of the array length) of nums as the node value and recursively call it to build the left subtree from the first half of nums and the right subtree from the second half of nums. This recursion continues until the input array length for the build function becomes 0. Now, let's move on to the code implementation.

解法 1

class Solution:
    def build(self, nums):
        l = len(nums)
        if l > 0 : 
            if l%2 != 0:
                idx= int(l/2)
            else:
                idx= int(l/2)-1
            node = TreeNode(nums[idx])
            node.left = self.build(nums[:idx])
            node.right = self.build(nums[idx+1:])
            return node

    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        root = self.build(nums)
        return root

🐯 : Recursion seems to be an intuitive approach. There are quite a few conditional checks in your code that may not be very intuitive for readability. Can you simplify those conditional checks?

🦝 : I see your point. I can calculate the middle index directly using integer division, eliminating the need for even/odd index checks.

解法 2

    
class Solution:
    def build(self, nums):
        l = len(nums)
        if l > 0 : 
            idx = l // 2 
            node = TreeNode(nums[idx])
            node.left = self.build(nums[:idx])
            node.right = self.build(nums[idx+1:])
            return node

    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        root = self.build(nums)
        return root

🐯 : Good. Can you provide a brief efficiency assessment of your approach?

🦝 : In terms of time complexity, with each recursive call, the array is split into two equal halves for the next level of calls, so the time complexity is O(logN). In terms of space complexity, each value in the array is stored in a TreeNode structure, so the space complexity is O(N).

🐯 : Understood. That concludes our interview for today. Thank you for your participation.

🦝 : Thank you very much.

初步檢討

需多注意英文發音與音節問題。
一段內容較長時，經常斷句的不太自然。
在後續討論時，面試者除了評估時間複雜度與空間複雜度外，應可以多說明一些作法，並比較其中的優劣。
面試者應該對自己撰寫的程式進行一些說明，或是代入數值舉例。

他評01

優點

interviewer有提供題目可以看很好。
清楚理解題意。

可改進地方

interviewer引導interviewee想到BFS的方式會比直接說用BFS更好。
interviewer可以讓interviewee解釋什麼是BFS還有DFS來了解interviewee是不是背答案還是真的理解。
和說中文相比時，說英文的音量變得蠻小聲顯得缺乏自信心。

他評02

優點
10:14: 時間跟空間複雜度的分析簡潔又清楚，很讚。
可改進地方

10:14: 時間跟空間複雜度的分析，interviewee 可以在解法 1 寫完就講，先說明完，再進行下一步的討論。

他評03

優點

英文流暢且具有語調變化
題意解釋清楚

可改進地方

程式撰寫時的解釋較少
Optimize的部分較少

他評04

interviewer

優點

開頭的開場很不錯
口齒清晰，聲音自然
題意解釋清楚

interviewee

優點

口齒清晰，聲音自然
和interviewer之間有互動

可改進地方

打程式時比較不說話
Optimize的部分較少

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

88. Merge Sorted Array

模擬面試過程

解法 1

解法 2

初步檢討

他評01

他評02

他評03

189. Rotate Array

模擬面試過程

初步檢討

他評01

他評02

他評03

108. Convert Sorted Array to Binary Search Tree

模擬面試過程

初步檢討

他評01

他評02

他評03

他評04

interviewer

interviewee

Read more

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

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

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

資訊科技詞彙翻譯