Try   HackMD

貢獻者: 鞋墊-Shoe
🧔：interviewer 👶：interviewee

模擬面試錄影(漢)
模擬面試錄影(漢)
模擬面試錄影(英)

53. Maximum Subarray

面試過程

🧔：一個array中，有很多個subarray，要你找出最大總和的subarray並return出該subarray的總和
👶：那想先請問這個array的長度範圍，有沒有可能是空的，以及array的element取值範圍
🧔：array長度界在1 ~ 之間，大小界在 -10^4 ~ 10^4
👶：那我會用python去實作想先請問一下，我是否能假設function的輸入為一個list
🧔：可以這樣假設，沒問題
👶：這邊他希望去找出一個total sum最大的subarray，我們想要快速知道這個subarray的"總和"(影片口誤)是多少，我會想到用preSum的方式先去紀錄0~i的總和，就能藉由下式知道subarray的total sum，就能夠將問題轉成找preSum[j] - preSum[i] (j > i)的最大值，這樣就能在固定preSum[j]的情況下去找一個最小的preSum[i] (curMin)，這樣我只需要去loop preSum這個array，並且將每個值當作preSum[j]，在扣掉j前面的最小element "curMin"，就能找出以j結尾的subarray中之最大total sum，接著再將每個位置結尾的total sum取max就能得到我們的答案

preSum[j] - preSum[i] (j > i) => find max

arr    =    [1, 2, 3]
preSum = [0, 1, 3, 6]
curMin

👶：那整體的時間複雜度為O(n)，空間複雜度為O(n)，以上為我的演算法，請問有甚麼問題嗎 ?
🧔：聽起來是沒甚麼問題，你可以開始實作了

Method: preSum

# Time: O(n)
# Space: O(n)

class Solution:
    def maxSubArray(self, arr: List[int]) -> int:
        
        n = len(arr)
        preSum = [0] * (n + 1)
        for i in range(1, n + 1):
            preSum[i] = preSum[i - 1] + arr[i - 1]

        ans = -float("inf")
        curMin =  0
        for j in range(1, n + 1):
            ans = max(ans, preSum[j] -  curMin)
            curMin = min(curMin, preSum[j])

        return ans

👶：以上為我的演算法實作後的code，請問有甚麼問題嗎 ?
🧔：希望你可以在進一步的優化空間，讓空間複雜度優化到O(1)
👶：基本上我每次loop只會用到preSum[j]，所以可將兩個loop合併就不需要使用到preSum的空間

Method: preSum

# Time: O(n)
# Space: O(1)

class Solution:
    def maxSubArray(self, arr: List[int]) -> int:
        
        n = len(arr)

        ans = -float("inf")
        curMin =  0  
        _sum = 0
        for j in range(1, n + 1):
            _sum += arr[j - 1]
            ans = max(ans, _sum  -  curMin)
            curMin = min(curMin, _sum)

        return ans

👶：以上為我的演算法實作後的code，請問這樣有符合你的要求嗎 ?
🧔：大致上是ok，那這邊還有一點時間，給一個follow up，如果用divide and conquer去實作你會怎麼處理這個問題，當然這邊時間複雜度就不一定在O(n)以內
👶：divide and conquer就是把大問題化成子問題，也就是說在index範圍i ~ j的arr中，可以將問題轉成找，i ~ k和k+1 ~ j的maxSubarray以及橫跨k的maxSubarray，那怎麼找這個橫跨k的maxSubarray呢 ? 我只需以k開頭向左邊加總找出一個最大值，在以k+1開頭向右邊加總找出一個最大值，兩值相加最會是橫跨k的maxSubarray，最後在與i ~ k和k+1 ~ j的maxSubarray比較找出最大值，就能夠找出i ~ j的maxSubarray
👶：那整體時間複雜度為O(nlogn)，空間複雜度為O(logn)，以上為我的演算法，請問有甚麼問題嗎 ?
🧔：聽起來是沒甚麼問題，你可以開始實作了

Method: divide and conquer

# Time: O(nlogn)
# Space: O(logn)

class Solution:
    def maxSubArray(self, arr: List[int]) -> int:
        
        def recur(i, j):
            if i == j:
                return arr[i]

            k = i + (j - i) // 2
            maxi = recur(i, k)
            maxj = recur(k + 1, j)

            maxL = -float("inf")
            _sum = 0
            for idx in range(k, i - 1, -1):
                _sum += arr[idx]
                maxL = max(maxL , _sum )

            maxR = -float("inf")
            _sum = 0
            for idx in range(k + 1, j  + 1):
                _sum += arr[idx]
                maxR = max(maxR , _sum )

            maxk = maxL + maxR 

            return max(maxi, maxj, maxk)

        return recur(0, len(arr) - 1)

👶：以上為我的演算法實作後的code，請問這樣有符合你的要求嗎 ?
🧔：大致上是ok，今天的面試就到此結束謝謝

同儕檢討

針對 interviewer 的檢討:

  • 0:00: 不該自稱是「面試官」，這有「上對下」的隱含意思，大家日後可能會是同事，而且說不定應徵者一開始的職等就比自己高台灣很小，你永遠很難想像記仇會多久，interview 是得知「相互」的「觀點」的途徑，不是讓你施展官威的場合。可改說「感謝你的時間，接下來由我主持這場面試」或「你好，從我手上這份簡歷，我感受到您對程式設計的熱情和專業，但在我們談及工作內容前，我想幫公司同仁先認識你在程式開發的想法和風格」
  • 0:05: 避免說「有幾個問題要你回答」，可改說「由於敝公司的產品開發中，不免會用到若干經典演算法，同仁想知道你的想法，因此我嘗試彙整過去的開發經驗，提出一兩個問題，請你稍候討論並在 Google Docs 撰寫程式碼」
  • 0:10: 這問題太經典，可以直接說「考慮 Maximum subarray problem，給定 …(程式開發條件)」，當然，若應徵者一臉茫然，再從頭解釋題目，順便觀察臨場反應
  • 0:16: 用字要精準，不是「sub-array 的總和」，而是「sub-array 元素的數值總和」，減少非必要的中英夾雜，尤其在視訊會議中，可能會不容易識別
  • 0:41: 避免說「10 的 4 次方」，可改說「一萬」，這樣對應徵者更友善，否則一直講「10 的多少次方」，可能會造成非必要的焦慮感。數值範圍很關鍵，在 REACTO 的 Optimization 或變化題階段，就可變更範圍，觀察應徵者如何思考和回應
  • 13:52: 避免說「嗯！聽起來是還可以」，這樣可能讓人誤會你根本沒檢查程式碼是否正確，應該回顧程式碼，看其中哪裡可調整，或者針對程式碼流程/變數命名提出改進
  • 17:51: 避免說「聽起來是沒有問題」這樣的話，會讓人覺得你很敷衍，將心比心，你若你一間知名的科技公司面試，結果 interviewer 跟你沒什麼互動和討論，你會怎麼想？其實最簡單的互動，就是簡述應徵者提出的方法，然後詢問如何驗證結果、程式碼是否可更精簡、特定的邊界條件是否考慮等等。follow-up 的問題不見得要讓應徵者把完整程式碼做出來，關鍵是「認識一個人的技能和面對問題的態度」

針對 interviewee 的檢討:

  • 1:55: 突然提到 "pre-sum"，對於溝通沒有太大幫助，應該依循 REACTO 法則，先充分 Repeat，然後解釋 "pre-sum" 的想法和益處
  • 4:11: 避免頻繁的移動滑鼠游標，不僅在視訊會議可能無法完整展現，也會讓對方感到焦慮，從而影響專注程度
  • 06:21: 面試不是講課，不用把「請問有任何問題嗎？」掛在嘴邊，可適度停頓，等 interviwer 的同時，順便整理 REACTO 的 Approach 內容。也要確認是否可用 Python 撰寫程式碼
  • 06:45: 避免頻繁的低頭，或許你在打字，但可能會有人懷疑你在跟槍手交流，儘量用一致的儀態作答
  • 07:57: 「並且找到它的 curMin 」聽起來像是「找 Kermit」，反而造成誤會。直接說「更新目前的最小值」
  • 08:38: 為何用到 float?
  • 11:30: 既然要討論到空間的使用改進 (即 preSum 佔用的空間)，應當跟 interviewer 確認，並討論這樣改善的效益何在
  • 13:44: 避免說「請問這樣是否符合你的需求？」，這樣不會顯得你有禮貌，反而會讓人誤解是「你剛背完答案，等老師批改」，可改說「我剛才從直觀的想法開始，在實作階段想到可調整空間效率」這類回顧的話語，特別在英語作答時，可引導 interviwer 提出更深入問題並彰顯自己的付出
  • 14:30: Divide-and-Conquer 應展現在 REACTO 的 Approach 中，可回頭看之前分析的過程，而非急著看程式碼，畢竟人家對你有興趣才會 follow-up。如何清楚展現自己的想法，才是面試的關鍵
  • 在定義function的spec時，也應該注意fuction name的意義，不應該只是用"f"代替
  • Kadane's algorithm (一種動態規劃手法) 可以很好的計算maxSubarray

    Method: kadane's algorithm

    ​​​​# Time: O(n)
​​​​# Space: O(1)
​​​​
​​​​class Solution:
​​​​    def maxSubArray(self, nums: List[int]) -> int:

​​​​        '''
​​​​        kadane's algorithm
​​​​            當 sum_ = nums[i: j + 1] < 0 時，會想要從前面的 i 再往前縮，不過不管怎麼縮 sum_ 都會是負的
​​​​            (可以把sum_想成利潤，既然到目前為止錢都被敗光了，那前面的 i 再往前縮，利潤仍然是負的)
​​​​        '''

​​​​        ans = -float("inf")
​​​​        sum_ = 0
​​​​        for num in nums:
​​​​            sum_ += num
​​​​            ans = max(ans, sum_)

​​​​            if sum_ < 0:
​​​​                sum_ = 0

​​​​        return ans

How to pronounce Kadane?

延伸閱讀

50. Pow(x, n)

影片

面試過程

🧔：在數學上經常會計算到 x^n，希望你能夠實作出一個程式計算 x^n，並計算後的回傳數值
👶：那想先請問x、n的範圍，n有沒有可能是負的或是小數之類的
🧔：x的範圍界在-100 ~ 100之間，n的範圍界在-2^31 ~ 2^31-1之間，且n都是整數
👶：還有一個問題是我輸入0^0，會希望我的系統回傳甚麼
🧔：如果是0^0回傳1就可以了
👶：就值觀來說，解這個題目會想將n分成兩種情況處理，n>=0計算x^n，n<0計算1 / x^(-n)，這樣就只需要在乎n>=0的情況來實作我們的演算法，就值觀來說就是乘x n次，也就是loop n次，這樣就能計算x^n 的數值，但是這個n的範圍大於2^31 -1，也就是已經大於10^9，數值非常大複雜度為O(n)，也就是直接loop會耗費很多時間，那這樣子的話…
我想到一個方式就是累乘的方式進行，這樣x的次數會以指數的方式增長，假設需要乘t次，這樣t=2^n，t=logn，時間複雜度大約就會是logn

n >= 0 => x ** n
n < 0 => 1 / x ** (-n)

s = x
s = s * s => x ** 2
s = s * s => x ** 4
s = s * s => x ** 8
….
s = s * s

2 ** t = n => t = logn

👶：可是n不一定是2的冪(power of 2)，所以必須計算

2k 將近n的數值，所以利用recursion計算剩餘的數值，再用相同的方式找到一個2^k將近次數的數值來計算以此類推直到n=0就回傳1

x ** 15 = x ** n

x ** 8 = s
x ** 7 => recur(x, n - 8) = recur(x, 7)
return s * recur(x, n - 8)


x ** 4
x ** 3 => recur(x, 7 - 4) = recur(x, 3)
return s * recur(x, 7 - 4)

👶：那整體時間複雜度為O(logn)，空間複雜度因為recursion需要cache address，所以為O(logn)
👶：那這邊假設function input為浮點數x和整數n，最後回傳x^n的數值，請問這樣假設ok嗎 ?
🧔：這樣子去定義function是可以的
👶：那目前我的演算法大致上長這樣，請問有甚麼問題嗎 ?
🧔：聽起來是沒甚麼問題，你可以開始實作了

Method: recursion























# Time: O(logn)
# Space: O(logn)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # n >= 0
        def pow(x, n):
            if n == 0:
                return 1

            s = x
            times = 1
            while times * 2 <= n:
                s = s * s
                times *= 2

            return s * pow(x, n - times)

        if n >= 0:
            return pow(x, n)
        else:
            return 1 / pow(x, -n)

👶：以上為我的演算法實作後的code，請問這樣有符合你的要求嗎 ?
🧔：大致上是ok，今天的面試就到此結束謝謝

檢討面試

  1. 在定義function的spec時，也應該注意fuction name的意義，不應該只是用"f"代替
  2. 可以利用iteration的方式進行，降低空間複雜度

    Method: binary

    
































    ​​​​# Time: O(logn)
​​​​# Space: O(logn)

​​​​class Solution:
​​​​    def myPow(self, x: float, n: int) -> float:

​​​​        # 2**14 = 2**8 x 2**4 x 2**2 (14 = 0b1110) 

​​​​        def pow2(x, n):
​​​​            if n == 0:
​​​​                return 1
​​​​            elif n == 1:
​​​​                return x

​​​​            ans = x
​​​​            count = 1
​​​​            while count * 2 <= n:
​​​​                ans *= ans
​​​​                count *= 2

​​​​            return ans

​​​​        ans = 1
​​​​        digitVal = 1

​​​​        n_ = abs(n)
​​​​        while n_ > 0:
​​​​            if n_ % 2 == 1:
​​​​                ans *= pow2(x, digitVal)
​​​​            n_ //= 2
​​​​            digitVal *= 2

​​​​        return ans if n >= 0 else 1 / ans

同儕檢討

  • Interviewer

    • 1:00 覺得在聽到範圍後將數字打出來很好,因為可以給interviewer確認,也可以記錄下來

  • 整體檢討：在開始寫code前，做了非常詳細的說明，而且有一邊打字，很好地展現了面試者的思路。

695. Max Area of Island

影片

面試過程

🧔：Hello, I am your interviewer. The first question is we given a grid and value of the grid is one become island, zero become water. An island is a group of 1's connected 4-directionally. And you need to find the max area of an island in the grid.
👶：Ok! We have 2D grid. "m" is grid of height and "n" is grid of width. I want to ask the m、n range. It will become empty or not ?
🧔：The m、n range will become 1~50.
👶：I think I will use the depth-first search to solve the this question. If the grid will become like this one (left grid), we will loop all the position of the grid, and use depth-first search to search the island and calculate the island area. If we start at this position ((i, j) = (1, 1)), we will search this position left, right, up and down, and search connected 4-directionally island's area. And the island area will become 5 (left grid). After we search this area, we will change grid value become zeros (right grid). And if next time loop the position again, we will not depth-first search again the island.
👶：I think I will use for loop to loop all the grid. if we find the grid value is one, we will use the depth-first search to search all area of island, and let island's value become zero like this (right grid).

m = len(grid)
n = len(grid[0])

1 <= m, n <= 50

0 0 0 0      0 0 0 0
0 1 0 1  =>  0 0 0 0
0 1 1 1      0 0 0 0
0 0 0 0      0 0 0 0

area = 5

👶：I think I define the function like this, input is a 2D grid. Could I define the function like this ?
🧔：Ok! You can define function like this
👶：This is my algorithm, could you have any concern ?
🧔：I think I do not have any concern. You can start to implement.
👶：Ok!
























# Time: O(mn)
# Space: O(log(mn))

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        def dfs(i, j):
            if not (0 <= i < m and 0 <= j < n) or grid[i][j] == 0:
                return 0

            grid[i][j] = 0

            return dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1) + 1

        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    ans = max(ans, dfs(i, j))

        return ans

👶：This is my program. Could you have any concern ?
🧔：I think this is the good method, and thank for your repeat.

檢討面試

  1. 在定義function的spec時，也應該注意fuction name的意義，不應該只是用"f"代替
  2. 雖然可以溝通，不過英文語法糟糕
Last changed by 
 
sysprog
System Software Programming
1417
Published on HackMD