# info2022-homework1
Requirement:
* 取名字
* 英文：Aragorn
* 中文：亞拉岡
* 挑兩題LeetCode problem
* Easy：[136. Single Number](https://leetcode.com/problems/single-number/)
* Medium：[11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/)
* REATO :
* R : **R**epeat
* E : give **E**xamples
* A : describe your **A**pproach
* C : implement the **C**ode
* T : **T**est the code
* O : talk about **O**ptimization
* 錄製interviewer & interviewee
* 錄製Note :
* 咬字要清晰。關鍵字尤其要注意！
* 要讓觀眾可以輕易分辨interviewer & interviewee（可用後製直接標註）
* 音量的部分要注意，要注意不要太小聲，但也不可以大聲到爆音。
* google document（作答區）應放大等等，讓觀眾輕易的看清楚。
* 不要過多的中英夾雜。
* interviewer :
* 應演的有氣勢、直接、明確。
* 講解題目時，應舉例，更輕易表達題目。
* 講解題目時，除了題目本身，重要的Constrains也應該說明，使題目明確。
* *幾個影片可以搭配假裝interviewer沒有說明，interviewee主動詢問確認*
* 在approach時應該要引導interview去談論更多，而非讓interviewee順順的講完。
* interviewee:
* 在approach時，不應直接去實作，應先表達自己的做法，與interviewer討論，再實作。
* 在實作時，應邊表達想法邊打字。
* 要避免很像在背答案。
## Part 1 : [136. Single Number](https://leetcode.com/problems/single-number/)
🥸 : interviewer
👨🏼⚕️ : interviewee
🥸 : 嗨，中文名字 你好，我是你的面試官，在這次的code interview中，我會給你一個問題，你需要在這份google文件上，設計與實作出可以解決這個問題的code，針對這樣的方式，你有什麼問題嗎？
👨🏼⚕️ : OK，沒有問題！
🥸 : 好！ 那我們直接開始吧！以下是題目：
>給予一個非空的整數陣列，除了一個特定的整數只出現一次，其餘所有整數恰好出現兩次，請找出那一個特定的數字，例如，給予一個整數陣列，裡面包含三個元素 [2, 2, 1]，因為1只出現一次，所以需要回傳數字1。
請開始作答。
👨🏼⚕️ : 好的，所以這個題目的input是一個整數整列，而且這個陣列至少有一個元素，不會是空陣列對嗎？
🥸 : 是的。
👨🏼⚕️ : 除了一個特定的數字只會出現一次，其餘數字恰好會出現兩次，不會出現三次、四次等等其他次數，這樣對嗎？
🥸 : 沒錯。
👨🏼⚕️ : 然後我需要回傳一個整數，也就是那一個只出現一次的數字，對嗎？
🥸 : 對。
__*Question : 在以上REACTO中的Repeat部分，interviewee會不會問得太冗長，感覺有點拖慢面試節奏。*__
👨🏼⚕️ : 好，那假如輸入的陣列為[1]，則應該要回傳數字1，對嗎？
🥸 : 沒錯。
👨🏼⚕️ : 如果輸入的陣列為[1, 2, 1, 2, 3]，因為數字3只出先過一次，則應該要回傳數字3，這樣也沒錯吧？
🥸 : 是的，沒問題。
👨🏼⚕️ : 我的第一個直覺的想法，便是使用Hashmap來解，使用一個Key跟Value的型別都是整數的Hashmap，Key表示這是哪一個數字，Value則用來記錄這個數字出現了幾次。運算流程的第一步：從頭到尾掃描輸入的陣列，以建立Hashmap。
以[1, 2, 1, 2, 3]這個陣列為例子的話，掃到[<span style="color:blue">1</span> , 2, 1, 2, 3]的時候，Hashmap為：
| Key | Value |
| --- |:-----:|
| 1 | 1 |
掃到[ 1, <span style="color:blue">2</span>, 1, 2, 3]時，Hashmap為：
| Key | Value |
| --- |:-----:|
| 1 | 1 |
| 2 | 1 |
依序掃完後，Hashmap為
| Key | Value |
| --- |:-----:|
| 1 | 2 |
| 2 | 2 |
| 3 | 1 |
建立完Hashmap以後，從Hashmap找出value為1的資料，回傳這筆資料的key值即可。
🥸 : OK，很直覺的方法，請分析一下複雜度。
🥸 : Ok, It's direct. Ok, It's the direct way to do that. Please analy the complexity.
Please assess the complexity.
👨🏼⚕️ : 好的，首先是時間複雜度，第一步掃描整個陣列，需花費$O(n)$，n為陣列長度。第二步從Hashmap中找出value為1的值，也是$O(n)$，因此整體的時間複雜度為$O(n)$。
空間複雜度的部分，需要額外的空間存放Hashmap，而Hashmap資料數等於陣列長度除以2，再取ceiling，因此空間複雜度為$O(n)$。
🥸 : 對，就像你說的，這個方法的空間複雜度為$O(n)$，如果需要將空間複雜度降低至$O(1)$，你有什麼方法嗎。
👨🏼⚕️ : 恩...$O(1)$的空間複雜度，代表不能用紀錄不同數字出現次數的方式。
🥸 : 沒錯，可以這麼說。
🥸 : Yes, That's creat. Yes, you are right about it.
👨🏼⚕️ : c我想到一個方法是可以先排序輸入的陣列，例如[ 1, 2, 1, 2, 3]排序後變成[ 1, 1, 2, 2, 3]，接著再依序掃描此排序過的陣列，一次檢驗兩筆資料，如果檢驗到的兩筆資料不相等，則回傳兩筆中的第一筆資料。例如假設排序後的資料為[ 1, 2, 2, 3, 3,]，掃瞄到[<span style="color:blue">1</span>, <span style="color:blue">2</span>, 2, 3, 3]兩筆資料不相等，則回傳兩筆中的第一筆資料，也就是1，或是掃描後只剩一筆資料時，例如[ <span style="color:gray">1</span>, <span style="color:gray">1</span>, <span style="color:gray">2</span>, <span style="color:gray">2</span>, 3]，便回傳該筆資料。
🥸 : 那複雜度的部分呢？
👨🏼⚕️ : 這個方法的話，複雜度就取決於排序演算法。以空間複雜度要求要$O(1)$的話，可以使用Insertion sort, Selection sort, Bubble sort, 和 Heap sort，這些排序演算法的空間複雜度皆為$O(1)$。其中 Heap sort的時間複雜度為 $O\left( n\log n\right)$，優於Insertion sort, Selection sort, 和Bubble sort的$O\left( n{}^{2}\right)$。
🥸 : 的確使用Heap sort的話，時間複雜度較使用你說的其他排序演算法還好，但是， $O\left( n\log n\right)$的時間複雜度，就比你前面線性的時間複雜度還差，如果今天時間複雜度要求要$O(n)$，空間複雜度要求$O(1)$，那你有什麼方法嗎？
👨🏼⚕️ : 請問，可以給我一點提示嗎？
👨🏼⚕️ : May I have some tips?
🥸 : 好，我給你一個提示，使用Bitwise operation。
OK ! Here is the tip.
👨🏼⚕️ : 恩...Bitwise operation的話，我直覺想到像是左移、右移等等的運算，<span style="color:gray">_這邊感覺是提及以前用Bitwise做過哪些東西的好時機_</span>，不過通常是用來進行2的冪次方乘、除法，感覺不太相關。另外就是AND、OR、XOR等的計算。啊！我突然想到XOR運算特性是：相同數字進行XOR運算會等於0，且0 XOR任何數字等於任何數字，應該可以從這方面入手！
👨🏼⚕️ : 方法是：先宣一個整數變數，初始值為0，只要把這個變數依序跟陣列元素進行XOR運算，因為相同的元素XOR會等於零，因此跟輸入陣列裡的所有元素進行XOR運算後，該變數就是那一個特定的數。
🥸 : OK，聽起來不錯，你可以實作出來嗎？
🥸 : Ok ,It's sound great. Please implement it.
👨🏼⚕️ :
```
int singleNumber(int* nums, int numsSize){
int rt = 0;
for(int i=0; i<numsSize; i++) {
rt ^= *(nums+i);
}
return rt;
}
```
🥸 : 針對你的程式碼，你有覺得有什麼地方可以優化的嗎？
```
int singleNumber(int* nums, int numsSize){
int rt = *(nums);
for(int i=1; i<numsSize; i++) {
rt ^= *(nums+i);
}
return rt;
}
```
## Part 2 : [11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/)
🥸 : 那我們接著下一題，請打開另一份文件。
👨🏼⚕️ : 好的。
🥸 : 以下是題目：
> 給予一個整數陣列，該陣列裡的成員，代表由左至右柱子的高度為幾個長度單位，任兩相臨的柱子，距離皆相同，為一個長度單位，你需要找出兩枝柱子，使得這兩支柱子可以容納最多的水，請注意，兩支柱子間的柱子，其體積不納入計算。請回傳可以包含最多的水量值。
例如，圖上這個例子，輸入的高度陣列為[1,8,6,2,5,4,8,3,7]，經過計算後，可以得出由圖上標示的兩個紅色柱子，包含的水量最多，回傳水量為49立方單位。
此題目有一些限制：
輸入陣列的長度介於 $2$~$10^{5}$
陣列成員的數值範圍為 $0$~$10^{4}$
請開始作答。
__*Question : 在此題的題目說明部分，感覺很多敘述可以加強。*__
👨🏼⚕️ : 首先輸入的陣列為整數陣列，其中第i個成員代表由左至右第i根柱子高度為幾個長度單位，這樣對嗎？
🥸 : 每錯。
👨🏼⚕️ : 相鄰的柱子，距離皆是一個長度單位，這樣對嗎？
🥸 : 對。
👨🏼⚕️ : 我需要找出兩根柱子，使得可以容納最多的水量，像圖中的左邊一單位的部分，我就不用考慮對嗎？
🥸 : 對，只有兩根柱子內的範圍。
👨🏼⚕️ : 我需要回傳的就是一個整數，也就是最大的水量，這樣對嗎？
🥸 : 對。
👨🏼⚕️ : 假設今天的輸入陣列是[0,1]，則我應該要回傳0對嗎？
🥸 : 對。
👨🏼⚕️ : 假射今天的輸入陣列是[1,1,1]，則我應該要回傳2對嗎？
🥸 : 對。
👨🏼⚕️ : 最先想到的是暴力法，暴力法就是去計算出每一對柱子所能涵蓋的水量多寡，再從中找出最大值，回傳該值，這方法複雜度為$O(n^{2})$，不過應該有更好的解法。
🥸 : 嗯，ok，那你有什麼方式？
👨🏼⚕️ : 覺得應該有蠻多可以省略，例如以同樣的寬度來說，若兩側的柱子沒有比較高，則水量絕對不會比較多，一開始可以假定第零個跟最後一個柱子所含的水量為最多，接著依序往內挑， 以寬度-1的兩個範圍來說，如果左邊的柱子比右邊的柱子矮，那水量絕對不會比較多，因此可以直接選擇右側這一塊，以這樣的方式持續做下去，就可以得到最多的水量。
🥸 : 好，想法不錯，請實作看看。
👨🏼⚕️ :
```
class Solution:
def maxArea(self, height: List[int]) -> int:
lp, rp = 0, len(height) - 1
res = 0
while lp != rp:
res = max(res, min(height[lp], height[rp])*(rp-lp))
if height[lp] < height[rp]:
lp += 1
else:
rp -= 1
return res
```
英文版：
## [136. Single Number](https://leetcode.com/problems/single-number/)
🥸 : interviewer
👨🏼⚕️ : interviewee
🥸 : Hey, Arogen, I'm your interviewer, In this code interview, I will give(ask) you a question, you need to design and implement your code on this google document, do you have any question ?
Ok, no problem.
🥸 :Ok! Let's start it. Here is the question:
>Given a non-empty array of integers, every element appears twice except for one. Find that single one. For example, given an array of integers with three elements [2, 2, 1], the number 1 needs to be returned because 1 occurs only once.
Please start answering.
👨🏼⚕️ : Ok, so the input of this question is an array of integers, and this array has at least one element, it won't be an empty array, right?
🥸 : Right.
👨🏼⚕️ : Except for a particular number that will only appear once, the rest of the numbers will appear exactly twice, not three, four, and so on, right?
🥸 : Yeap.
👨🏼⚕️ : Then I need to return an integer, the one that only occurs once, right?
🥸 : Yes.
👨🏼⚕️ : Well, if the input array is [1], the number 1 should be returned, right?
🥸 : Yes.
👨🏼⚕️ : If the input array is [1, 2, 1, 2, 3], since the number 3 only occurs once, the number 3 should be returned, right?
🥸 : Yes, you are right.
👨🏼⚕️ : My first intuitive idea is to use a Hashmap to solve the problem. Use a Hashmap whose Key and Value are both integer types. Key indicates which number it is, and Value is used to record how many times this number appears. The first step of the operation is : scan the input array from beginning to end to build a Hashmap.
Taking the array [1, 2, 1, 2, 3] as an example, when [<span style="color:blue">1</span> , 2, 1, 2, 3] is scanned, the Hashmap is:
| Key | Value |
| --- |:-----:|
| 1 | 1 |
when [ 1, <span style="color:blue">2</span>, 1, 2, 3] is scanned, the Hashmap is:
| Key | Value |
| --- |:-----:|
| 1 | 1 |
| 2 | 1 |
After scanning in sequence, the Hashmap is :
| Key | Value |
| --- |:-----:|
| 1 | 2 |
| 2 | 2 |
| 3 | 1 |
After the Hashmap is created, find the data whose value is 1, and return the key value of this data.
🥸 : OK, very intuitive method, please analyze the complexity.
👨🏼⚕️ : Okay, the first is the time complexity, the first step is to scan the entire array, which takes $O(n)$, where n is the length of the array.The second step is to find the data whose value is 1 from the Hashmap, which is also $O(n)$, so the overall time complexity is $O(n)$.
For the space complexity part, additional space is needed to store the Hashmap, and the number of Hashmap data is equal to the length of the array divided by 2, and then the ceiling is taken, so the space complexity is $O(n)$.
🥸 : Yes, like you said, the space complexity of this method is $O(n)$, if you need to reduce the space complexity to $O(1)$, do you have any method.
👨🏼⚕️ : Well...$O(1)$ space complexity means that I can't use the way to record the number of occurrences of different numbers.
🥸 : Yeah, you are right about it.
👨🏼⚕️ : I thought of a way to sort the input array first, for example array [ 1, 2, 1, 2, 3] after sorting becomes array [ 1, 1, 2, 2, 3], and then scan the sorted array in sequence, Check two data at one time, if the two data are not equal,then return the first piece of data.For example, suppose the sorted data is [ 1, 2, 2, 3, 3,]，Scan to [1,2], find that the two data are not equal,then return the first data, which is 1. Or when there is only one piece of data left after scanning. For example[ <span style="color:gray">1</span>, <span style="color:gray">1</span>, <span style="color:gray">2</span>, <span style="color:gray">2</span>, 3], this data is returned.
🥸 : So, What about the complexity?
👨🏼⚕️ : The complexity of this method depends on the sorting algorithm。If the space complexity requires $O(1)$，Insertion sort, Selection sort, Bubble sort, and Heap sort can be used, and the space complexity of these sorting algorithms is $O(1)$。The time complexity of Heap sort is $O\left( n\log n\right)$, which is better than $O\left( n{}^{2}\right)$ of Insertion sort, Selection sort, and Bubble sort .
🥸 : Indeed, if you use Heap sort, the time complexity is better than using other sorting algorithms you mentioned, but, The time complexity of $O\left( n\log n\right)$ is worse than your previous linear time complexity method. If today’s time complexity requires $O(n)$, the space complexity requires $O (1)$, do you have any method?
👨🏼⚕️ : Could you please give me some hints?
🥸 : Well, I'll give you a hint, use Bitwise operation.
👨🏼⚕️ :Well... for Bitwise operation, I intuitively think of operations such as left shift, right shift, and so on. But it is usually used for power-of-2 multiplication and division, which doesn't feel very relevant.The other is the calculation of AND, OR, XOR, etc. Oh! I suddenly thought that the XOR operation characteristic is: XOR operation of the same number will be equal to 0, and 0 XOR any number is equal to any number, it should be possible to start from this aspect!
👨🏼⚕️ : The method is: first declare an integer variable, the initial value is 0, as long as this variable is XORed with the array elements in sequence, because the same element XOR will be equal to zero, so after XOR operation with all elements in the input array, the variable is that specific number.
🥸 : Ok ,It's sound great. Please implement it.
👨🏼⚕️ :
```
def singleNumber(nums):
a = 0
for i in nums:
a ^= i
return a
```
🥸 : Do you think there is anything you can do to optimize your code?
```
def singleNumber( nums):
a = 0
for i in nums:
a ^= i
return a
```
Sign in with Wallet
Connect another wallet