---
###### tags: `資訊科技產業專案設計` `hw`
---
# info2022-homework1
> 貢獻者: 霸佛羅｜Buffalo
> ==[1-1(漢)](https://youtu.be/Cd0_n5GaHXw)== ==[1-2(漢)](https://youtu.be/2fT76EK9Ilw)== ==[1-3(英)](https://youtu.be/eKaWpFNK0To)==
:man:： interviewer :baby:：interviewee
## [LeetCode#1 Two Sum (easy)](https://leetcode.com/problems/two-sum/)
> 影片連結：[1-1(漢)](https://youtu.be/Cd0_n5GaHXw)
#### 模擬面試過程的討論
:man:：我是你這一輪的面試官，這一輪的題目是給你一個整數陣列還有一個目標值，那你要 return 出哪兩個數字加起來會等於目標值，以這個範例舉例
```
input: [1, 2, 3] 4
output: [0, 2]
```
如果整數陣列為 1, 2, 3，因為 1 加 3 會等於目標值 4，所以要 return 第 0 及第 2 個 index，請問你有甚麼不清楚的地方嗎?
:baby:：面試官好，我想請教兩個問題，第一個問題是這個陣列是會從小排到大的嗎，第二個問題是這個陣列有沒有可能有重複的 index 加起來會等於 target 值?
:man:：第一個回答是這個陣列是沒有排序隨機的，第二個回答是你可以假定一定會有一組解，且該組解 index 不會有重複的
:baby:：我的想法是如果我們把所以數字都跟別的數字配對的話，如果等於目標值我們將他輸出出來
:man:：這聽起來是可行的，你可以開始寫寫看
##### 雙層迴圈(bruteforce)
```python=
class Solution(object):
def twoSum(self, nums, target):
# 用索引值進行兩個迴圈的迭代
for i in range(len(nums)):
for j in range(i+1, len(nums)):
# 如果相加等於目標數時回傳答案
if nums[i] + nums[j] == target:
return [i, j]
```
:baby:：以這個解法來說，因為有兩個 for 迴圈，所以時間複雜度是$O(n^2)$，空間複雜度因為沒創建新的值，所以是 constant
:man:：因為時間複雜度目前是 $O(n^2)$，有更佳的解法嗎?
:baby:：可以試試看如果用兩個 pointers，一個指向第一個數字，一個指向最後一個數字，把他們相加並與 target 比，如果比較大，就把指向比較大的 pointer 往左邊移動一個，反之如果比較小，把左邊的 pointer 往右移一個，用類似夾擠定理的方式慢慢找出我們的 target 值。雖然在找 target 的時候只用到 linear 的時間複雜度，不過因為一開始需要先排序過，因此需要用到 $O($n$logn$)。
或許我們可以試試看裡用 hashmap，用另一種想法
```
# 題目要求
a + b = target
# 可以想成
b = target - a
```
再解釋更清楚一點，每次 run through 到 a，就可以將 b = target - a，看 hashmap 裡面有沒有 b，這樣或許可以找到更加解
:man:：這聽起來也是合理的，那你要不要試著寫寫看
:baby:：好的沒問題
##### Hash Table
```python=
class Solution(object):
def twoSum(self, nums, target):
# 創建一個 dictionary 來記錄 num, index
d = {}
# 並從第 0 個 index 開始跌帶
for i in range(len(nums)):
# num1 為該 index 的值
num1 = nums[i]
# 定義一個 num2 儲存所要找的值
num2 = target - num1
# 重覆檢查已經存過的 num1 是否等於現在所需要的 num2
if num2 in d:
return [d[num2], i]
# 如果沒有則將該 value 及 index 存下來，因為需要 num1、num2 的索引值
d[num1] = i
```
:baby:：以這解法來說的話，因為他在 dictionary 尋找的時間只有 $O(1)$，所以只會 run through 一次 for 迴圈，因此時間複雜度及空間複雜度皆是 linear 的，這就是剛剛想到較佳的解法
:man:：好的沒問題，我們這輪的面試就先到這邊，謝謝！
:::info
如排序過後的話，可以利用兩個指標的移動，計算兩個元素和，不符合則往中間移動直到滿足題目要求，這樣時間複雜度為 $O(n)$，空間複雜度為 $O(1)$
##### Two Pointers
```python=
class Solution(object):
def twoSum(self, nums, target):
# 初始將定義的位置指向頭和尾
i = 0
j = len(nums) - 1
while (nums[i] + nums[j] != target):
# 如果相加比目標值大，則將指向較大 index 的 pointer 往左移一格
if (nums[i] + nums[j] > target):
j = j - 1
# 如果相加比目標值小，則將指向較小 index 的 pointer 往右移一格
else:
i = i + 1
return [i, j]
```
:::
---
### 延伸閱讀
1. [3Sum](https://leetcode.com/problems/3sum/)
2. [4Sum](https://leetcode.com/problems/4sum/)
3. [Two Sum II - Input Array Is Sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)
4. [Two Sum III - Data structure design](https://www.lintcode.com/problem/two-sum-iii-data-structure-design/my-submissions)
5. [Two Sum IV - Input is a BST](https://leetcode.com/problems/two-sum-iv-input-is-a-bst/)
6. [Two Sum Less Than K](https://leetcode.com/problems/two-sum-less-than-k/)
## 初步檢討
#### 針對影片呈現檢討
- 錄完影才發現可以用 OBS 開視訊鏡頭，下次改進
#### 針對 interviewer 檢討
- 討論可以更多面向，不是只局限於複雜度
- 討論時可以更多變化，像是融合 three sum 等等
#### 針對 interviewee 檢討
- 模擬時照著平常打程式的節奏就行，避免一些疏漏打錯
- 打字如果在快一點可以更加順暢
## [LeetCode#11 Container With Most Water (medium)](https://leetcode.com/problems/container-with-most-water/)
> 影片連結：[1-2(漢)](https://youtu.be/2fT76EK9Ilw)
#### 模擬面試過程的討論
:man:：你好，我是你這一輪的面試官，那這一輪的題目是 Container With Most Water，那這題會給你一個整數的 list，這個整數的 list 的數值分別代表每個座標的高度，以這張圖為例比較清楚
我們所要求的是哪兩個柱子所裝的水的面積會是最多的，想請問你對於這題有甚麼問題嗎?
:baby:：面試官好，所以這題的 input 會給你一個裝著高度的 list，那你要 output 出最大可以裝的面積，在過程中也都不會有任何傾斜及其他因素，請問是這樣嗎?
:man:：是的沒有錯！
:baby:：最初我想到的想法是如果把每一對所為出來的面積都找出來，再從中找到最大值
:man:：聽起來是可行的方法，那可以請你試試看嗎?
:baby:：好的沒問題
##### 雙層迴圈(bruteforce)
嘗試全部兩兩一組所能容納的面積，並找出最大值
```python=
class Solution(object):
def maxArea(self, height):
# 創建 result 並於每次迭代更新為最大值
res = 0
# 用索引值進行兩個迴圈的迭代
for l in range(len(height)):
for r in range(l + 1, len(height)):
area = (r - l) * min(height[l], height[r])
# 將 res 更新為最大值
res = max(res, area)
return res
```
用這個方法來做的話，因為有用到兩個 for 迴圈，因此時間法砸度為 $O(n^2)$，又因為沒其他需要創造的空間，因此空間複雜度為 $O(1)$
:man:：這聽起來是可行的，不過你有更好的解法嗎?
:baby:：可以試試看兩個 pointers 的方式，第一個指向第一個數字，第二個指向最後一個數字，算完面積後將較小的 height 做更新，這樣可以確保較高的都可以被留著，最後得出的結果應該就可以是最大的面積
:man:：聽起來是合理的，那麻煩你試試看
:baby:：沒問題
##### Two Pointers
```python=
class Solution(object):
def maxArea(self, height):
# 將要更新的質初始設成 0
res = 0
# 兩個指標分別指向第一個及最後一個數
l= 0
r = len(height) - 1
# 持續執行直到兩個指標交錯
while l < r:
# 計算每一次的面積
area = (r - l) * min(height[l], height[r])
# 更新成較大的面積
res = max(res, area)
# 移動指向較低高度的指標
if height[l] < height[r]:
l += 1
else:
r -= 1
return res
```
以這個解法來說，因為終止條件為兩個 pointers 交錯的時候，因此我們會完整走過整個 list，因此所花的時間複雜度為 $O(n)$，那空間複雜度因為沒有創建其他額外的空間，因此為 $O(1)$
:man:：這是一個好方式，他運用到的時間複雜度比上一個方法好，那我這輪面試到這邊，謝謝！
---
### 延伸閱讀
1. [Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)
## 初步檢討
#### 針對影片呈現檢討
- 錄完影才發現可以用 OBS 開視訊鏡頭，下次改進
#### 針對 interviewer 檢討
- 討論可以更多面向，不是只局限於複雜度
- 討論時可以更多變化，直到了解 interviewer 能耐
#### 針對 interviewee 檢討
- 打字如果在快一點可以更加順暢
- 照順序打就像為了面試背答案
## [LeetCode#1 Two Sum (easy)](https://leetcode.com/problems/two-sum/)
> 影片連結：[1-3(英)](https://youtu.be/eKaWpFNK0To)
#### 模擬面試過程的討論
:man:：Hi, I'm your today interviewer. In this round, our given question is Two Sum. The descreption is given an interger array, and an interger target, and you need to return two indexes such that they add up two target. So for example, the input list is one, two ,and three, because one and three added up is equal to four, so the output will be zero and two which is there index. Is there any question?
```
input: [1, 2, 3] 4
output: [0, 2]
```
:baby:：I would like to ask is the list in order, and is it possible for a number use more than one time?
:man:：That's a good question. So the list is not in order and there will no number used more than one time.
:baby:：That's clear. So I think we can add up each of the two numbers, and check if they're added up to the target number.
:man:：Okay cool, that's sounded possible. You can start your code.
:baby:：Due to the reason that we need to sum each of the two numbers, so we'll use the for loop.
##### Using two for loop (bruteforce)
```python=
class Solution(object):
def twoSum(self, nums, target):
# start with the first index and go through each number in the list
for i in range(len(nums)):
# The second index of the number
for j in range(i+1, len(nums)):
# check if they're sum up equal to target number
if nums[i] + nums[j] == target:
return [i, j]
```
So this is my first solution, and the time complexity because of two of the for loop, so it is n square, and the space complexity because they didn't use other extra space, so the space complexity will be constant.
:man:：Do you have better solution, because this time complexity is too high.
:baby:：We can try to use hashmap, for each of the number we to through, we can try to find other number which is the target minus the number we go through, and then try to find in the hashmap, if we find in the hashmap, then return the index, if we didn't find in the hashmap, we can save the number and index into the hashmap, then in the future we can find this number.
```
# 題目要求
a + b = target
# 可以想成
b = target - a
```
:man:：Okay cool, that sound nice, do you want to try yout code?
:baby:：Okay sure.
##### Hash Table
```python=
class Solution(object):
def twoSum(self, nums, target):
# create a dictionary which is similar with haspmap
d = {}
# go through each number
for i in range(len(nums)):
# the number we go through
num1 = nums[i]
# the other number we want to find
num2 = target - num1
# if the number is in our dictionary then return
if num2 in d:
return [d[num2], i]
# if not, save the number and the index of in the dictionary
d[num1] = i
```
In this solution we need to get in the hashmap is constant, so in this solution the time complexity and space complexity is both linear time
:man:：Okay cool, sound great. I think this is the end of the interview
## 初步檢討
#### 針對影片呈現檢討
- 錄完影才發現可以用 OBS 開視訊鏡頭，下次改進
#### 針對 interviewer 檢討
- 都講 "we"，但應該用 "I"
- 太常說 "so"
#### 針對 interviewee 檢討
- 邊打字邊說英文不太順暢
Google Drive
Gist
Clipboard
Sign in with Wallet
