---
tags: info2022-homework1
---
> 貢獻者: 鞋墊-Shoe
> 🧔：interviewer 👶：interviewee
> [模擬面試錄影(漢)](https://youtu.be/FBT4lqwDxB4)
> [模擬面試錄影(漢)](https://youtu.be/q6PqC0Kv_NY)
> [模擬面試錄影(英)](https://youtu.be/O9-SUY2eu20)
## [53. Maximum Subarray](https://leetcode.com/problems/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
```python
# 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
```python
# 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
```python
# 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](https://youtu.be/FBT4lqwDxB4): 不該自稱是「面試官」，這有「上對下」的隱含意思，大家日後可能會是同事，而且說不定應徵者一開始的職等就比自己高^台灣很小，你永遠很難想像記仇會多久^，interview 是得知「相互」的「觀點」的途徑，不是讓你施展官威的場合。可改說「感謝你的時間，接下來由我主持這場面試」或「你好，從我手上這份簡歷，我感受到您對程式設計的熱情和專業，但在我們談及工作內容前，我想幫公司同仁先認識你在程式開發的想法和風格」
* [0:05](https://youtu.be/FBT4lqwDxB4?t=5): 避免說「有幾個問題要你回答」，可改說「由於敝公司的產品開發中，不免會用到若干經典演算法，同仁想知道你的想法，因此我嘗試彙整過去的開發經驗，提出一兩個問題，請你稍候討論並在 Google Docs 撰寫程式碼」
* [0:10](https://youtu.be/FBT4lqwDxB4?t=10): 這問題太經典，可以直接說「考慮 [Maximum subarray problem](https://en.wikipedia.org/wiki/Maximum_subarray_problem)，給定 ...(程式開發條件)」，當然，若應徵者一臉茫然，再從頭解釋題目，順便觀察臨場反應
* [0:16](https://youtu.be/FBT4lqwDxB4?t=16): 用字要精準，不是「sub-array 的總和」，而是「sub-[array 元素](https://terms.naer.edu.tw/detail/1272416/)的數值總和」，減少非必要的中英夾雜，尤其在視訊會議中，可能會不容易識別
* [0:41](https://youtu.be/FBT4lqwDxB4?t=41): 避免說「10 的 4 次方」，可改說「一萬」，這樣對應徵者更友善，否則一直講「10 的多少次方」，可能會造成非必要的焦慮感。數值範圍很關鍵，在 REACTO 的 Optimization 或變化題階段，就可變更範圍，觀察應徵者如何思考和回應
* [13:52](https://youtu.be/FBT4lqwDxB4?t=832): 避免說「嗯！聽起來是還可以」，這樣可能讓人誤會你根本沒檢查程式碼是否正確，應該回顧程式碼，看其中哪裡可調整，或者針對程式碼流程/變數命名提出改進
* [17:51](https://youtu.be/FBT4lqwDxB4?t=1071): 避免說「聽起來是沒有問題」這樣的話，會讓人覺得你很敷衍，將心比心，你若你一間知名的科技公司面試，結果 interviewer 跟你沒什麼互動和討論，你會怎麼想？其實最簡單的互動，就是簡述應徵者提出的方法，然後詢問如何驗證結果、程式碼是否可更精簡、特定的邊界條件是否考慮等等。follow-up 的問題不見得要讓應徵者把完整程式碼做出來，關鍵是「認識一個人的技能和面對問題的態度」
針對 interviewee 的檢討:
* [1:55](https://youtu.be/FBT4lqwDxB4?t=115): 突然提到 "pre-sum"，對於溝通沒有太大幫助，應該依循 REACTO 法則，先充分 Repeat，然後解釋 "pre-sum" 的想法和益處
* [4:11](https://youtu.be/FBT4lqwDxB4?t=251): 避免頻繁的移動滑鼠游標，不僅在視訊會議可能無法完整展現，也會讓對方感到焦慮，從而影響專注程度
* [06:21](https://youtu.be/FBT4lqwDxB4?t=381): 面試不是講課，不用把「請問有任何問題嗎？」掛在嘴邊，可適度停頓，等 interviwer 的同時，順便整理 REACTO 的 Approach 內容。也要確認是否可用 Python 撰寫程式碼
* [06:45](https://youtu.be/FBT4lqwDxB4?t=405): 避免頻繁的低頭，或許你在打字，但可能會有人懷疑你在跟槍手交流，儘量用一致的儀態作答
* [07:57](https://youtu.be/FBT4lqwDxB4?t=477): 「並且找到它的 `curMin` 」聽起來像是「找 [Kermit](http://www.columbia.edu/kermit/)」，反而造成誤會。直接說「更新目前的最小值」
* [08:38](https://youtu.be/FBT4lqwDxB4?t=518): 為何用到 `float`?
* [11:30](https://youtu.be/FBT4lqwDxB4?t=690): 既然要討論到空間的使用改進 (即 `preSum` 佔用的空間)，應當跟 interviewer 確認，並討論這樣改善的效益何在
* [13:44](https://youtu.be/FBT4lqwDxB4?t=824): 避免說「請問這樣是否符合你的需求？」，這樣不會顯得你有禮貌，反而會讓人誤解是「你剛背完答案，等老師批改」，可改說「我剛才從直觀的想法開始，在實作階段想到可調整空間效率」這類回顧的話語，特別在英語作答時，可引導 interviwer 提出更深入問題並彰顯自己的付出
* [14:30](https://youtu.be/FBT4lqwDxB4?t=870): Divide-and-Conquer 應展現在 REACTO 的 Approach 中，可回頭看之前分析的過程，而非急著看程式碼，畢竟人家對你有興趣才會 follow-up。如何清楚展現自己的想法，才是面試的關鍵
* 在定義function的spec時，也應該注意fuction name的意義，不應該只是用"f"代替
* [Kadane's algorithm](https://en.wikipedia.org/wiki/Maximum_subarray_problem) (一種動態規劃手法) 可以很好的計算maxSubarray
#### Method: [kadane's algorithm](https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/)
```python
# 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
```
:::success
[How to pronounce Kadane?](https://www.howtopronounce.com/kadane)
:::
延伸閱讀
* [Maximum subarray problem](https://en.wikipedia.org/wiki/Maximum_subarray_problem)
* [Kadane's algorithm](https://zhuanlan.zhihu.com/p/96014673)
---
## [50. Pow(x, n)](https://leetcode.com/problems/powx-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)，所以必須計算$2^k$ 將近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
```python=
# 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
```python=
# 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](https://youtu.be/q6PqC0Kv_NY?t=60) 覺得在聽到範圍後將數字打出來很好,因為可以給interviewer確認,也可以記錄下來
- 整體檢討：在開始寫code前，做了非常詳細的說明，而且有一邊打字，很好地展現了面試者的思路。
---
## [695. Max Area of Island](https://leetcode.com/problems/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!
#### Method: depth-first search
```python=
# 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. 雖然可以溝通，不過英文語法糟糕
Sign in with Wallet
Connect another wallet