# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 祥變牆-becomeStrong
> 模擬面試錄影: [1](https://www.youtube.com/watch?v=BQF6Be5fxSc), [2](https://www.youtube.com/watch?v=nqDRzJmsXBA), [3](https://youtu.be/4GjlwNrmth8)
> 👨: interviewer
> 👶: interviewee
### 141. Linked List Cycle
https://leetcode.com/problems/linked-list-cycle/
#### 自我初步檢討
- 英語口說不夠通順，應該加強英語口說，尤其是在執行 REACTO 的 Approach 的時候。應該使用更簡單易懂的句子描述 Approach。
- 在執行 REACTO 的 E 的時候，舉了兩個相似的例子，看完影片覺得對於理解沒太多用途，應該舉出有差別的例子
- 有提出一些疑惑加以詢問，這樣可以避免檢查一些 boundary case（比如 node 是否可以指向自己形成 cycle），加分
- 在提出第二個 solution 後，沒有執行到第一個 solution 的第二個 example，應該都用相同的 example 來驗證 solution
- 第二個方法是看到 follow up 才去思考的，應該在第一次解答的時候就考慮空間複雜度的問題
- code 用太少甚至沒有用註解解釋變數
- 在第二個 solution 提到用 MSB 去判斷 val 是否是正整數或負整數，但 coding 的時候卻使用了 comparison operator(>) ，coding 應該和想法一致
- 在第二個 solution，求出 second MSB 的 mask 寫錯了，應該是 0x40000000 而不是 0x4fffffff
- 在第二個 solution 說了要用 unsigned right shift 結果寫成了 signed right shift
```java
secondMSB = (iter.val & secondMSBMask) >> 30;
// 應該改成
secondMSB = (iter.val & secondMSBMask) >>> 30;
```
- 在第二個 solution 的 negate second MSB 寫錯了
```java
iter.val &= ~secondMSBMask;
// 應該改成
iter.val &= secondMSBMask;
```
- 在第二個 solution，最後忘了 return false
- 在第二個 solution 錯誤比較多，也沒有即使發現修改，扣分
👨：Hi, BecomeStrong, how are you?
👶：Hi, I am good, thanks for asking. Shall we begin?
👨：
Sure.The question today is:
Given a head, the head of a linked list, please determine if the linked list has a cycle in it.
There is a cycle in a linked list if there are some nodes in the list that can be reached again by continuously following the next pointer. You need to return true if there is a cycle in the linked list. Otherwise, return false.
Moreover, I want you to code in Java. So, the class of node is defined as the code snippet that I give you right now:
```java
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
```
The ListNode contains two members which are val and next pointer.
The range of the val member is between -10^5（negative 10 power to 5） <= val <= 10^5 and (positive 10 power to 5). The next member will point to the next node. Does it clear?
👶：Yep, May I repeat the question so that I can confirm some points of the question?
👨：Sure, go ahead.
👶：
So, I will be given a linked list and the head of the linked list. What I need to do is to detect if any cycle exists in the linked list. Does it make sense?
👨：Yep, it make sense.
👶：
Let me confirm some points which might confusing:
1. Does the linked list could be empty or not?
2. Does the node can point to itself to form a cycle?
👨：
Oh, yeh, the linked list could be empty and the node cannot point to itself to form a cycle. Does it clear?
👶：
Yep, it is clear now. So, I will write a function called `hasCycle` which has one parameter, the head of the linked list, and it will return true if a cycle is detected or false otherwise. let us take some examples to demonstrate the behavior of the function.
👨：OK, please go on.
👶：
The input is a which is the head of the linked list, and b is a boolean tell us that if any cycle is detected.
```
hasCycle
a -----------> b
no1. a = [3,2,0,-4], assume the next of -4 points to 2 ----> true
no2. a = [1,2], assume the next of 2 points to 1 ----> true
And the last one. a = [1,2,3,4], assume the next of 4 points to null ----> false
```
Any comments of the my examples?
👨：Nope, they looks good. What about your solution to the question?
👶：
Yep, so there is a trivial solution such that I could create a visited list,
Such that before traversing the node, we have to lookup the node in the visited list first,
if found means we have traversed the node before and there is a cycle then return true, otherwise keep traversing the list of node until reach NULL. At this time, return false since all the nodes are traversed exactly one time.
👨：Sound interesting. You may start coding it.
👶：（code time）
```java
class Solution {
List < ListNode > visitedList = new ArrayList < > ();
boolean lookup(ListNode n) {
for (ListNode n2: visitedList) {
if (n == n2)
return true;
}
return false;
}
boolean hasCycle(ListNode head) {
ListNode iter = head;
while (iter != null) {
if (lookup(iter) == true)
return true;
visitedList.add(iter);
iter = iter.next;
}
return false;
}
}
```
Lets run the examples proposed before to verify the solution.
1. a = [3,2,0,-4], assume the next of -4 points to 2, lookup 3 in visited list first, of course it will not be found then 3 will be stored into visited list, do the same thing on the rest of nodes. When we reach 2 again after 4 since the next of 4 is 2, we will find 2 in visited list means there is a cycle exists then return true.
2. a = [1,2,3,4], assume the next of 4 points to null, so do the same thing: lookup each node in visited list first, if not found then store it, otherwise cycle is detected and return true.
When we reach 4, the next of 4 should be null. So, the linked list do not have a cycle and return false.
👨：Great. I think you are good. So, let's move on. Could you propose a solution which using O(1) constant space to solve the question?
👶：
Let me think about it. So, the space complexity of previous solution is O(N) since we maintain a visited list. To reduce the space complexity to O(1) constant space, I think we can utilize the bitwise operation to lower the complexity of space from O(n) to O(1). The idea is that we can store the visited information in the value of val member of node since the val member of node in range [-10^5, 10^5], we can utilize the second MSB bit as our visited bit. There are two cases:
1. for val member is positive number, the second MSB bit will be 0 initially, if we traverse the node, the second MSB bit should be set to 1. So if we find second MSB bit of the node is 1 in a positive val member, then there is a cycle and return true. Otherwise, return false after traversing all the nodes.
2. for val member is negative number, the second MSB bit will be 1 initially since it is in 2's complement environment. if we traverse the node, the second MSB bit should be set to 0. So if we find second MSB bit of the node is 0 in a negative val member, then there is a cycle is detected and return true. Otherwise, return false after traversing all the nodes.
👨：Sounds great. Can you code it out?
👶：Sure, let's start coding. （code time）
```java
class Solution {
boolean hasCycle(ListNode head) {
// 0b0100xxx
int secondMSBMask = 0x4fffffff;
ListNode iter = head;
int secondMSB;
while (iter != null) {
secondMSB = (iter.val & secondMSBMask) >> 30;
if (iter.val > 0) { // positive
if (secondMSB == 1)
return true;
iter.val |= secondMSBMask;
} else { // negative, 0b10
if (secondMSB == 2)
return true;
iter.val &= ~secondMSBMask;
}
iter = iter.next;
}
}
}
```
Lets run the examples proposed before again to verify the new solution:
1. a = [3,2,0,-4], assume the next of -4 points to 2. The 32bit of 3 in binary is 0b00000000000000000000000000000011, we can see that MSB is 0 so it is a positive val member also the second MSB bit is 0 so no cycle is detected. Then, set second MSB bit to 1. When we reach 2, the 32bit of 2 in binary is 0b00000000000000000000000000000010, we can see that MSB is 0 so it is a positive val member also the second MSB bit is 0 so no cycle detected also. Then, set second MSB bit to 1. Do the same thing to the rest of node. When we reach 2 again after -4, the second MSB bit bit of 2 is 1 that is set at the first encounter of 2 so a cycle is detected and return true.
2. a = [1,2,3,4], assume the next of 4 points to null, so do the same thing in example 1:
traverse the linked list and check the MSB and second MSB bit, if positive val member having 1 in second MSB bit then cycle is detected.
if negative value having 0 in second MSB bit then cycle is detected. In this example, no cycle is detected since they are all traversed exactly once.
👨：Great, I think the new solution met the requirement of O(1) constant space. Could you talk about the time complexity of two solutions respectively?
👶：Sure. The time complexity of first solution is O(N^2) since we have to lookup the node in visited list. The time complexity of second solution is O(N) since we only loop through the linked list plus one node which form the cycle.
👨：Good, the interview is done, let's call it a day.
👶：Thank you for interviewing.
### 26. Remove Duplicates from Sorted Array
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
#### 自我初步檢討
- 第一個 solution 能想到 in-place 應該算不錯（雖然題目有要求）
- 驗證 solution 的時候，第二個 example 感覺有點多重複的步驟，可能可以加快這一部分，不然 interviewer 可能聽不下去
- code 用太少甚至沒有用註解解釋變數
👨：你好，我是你今天的面試官。
👶：你好, 我叫祥變牆。
👨：
今天的題目是給定一個已經排序好的整數陣列，你要把陣列裡面重複的整數移除掉。
此外，你必須使用 in-place 演算法。在移除的過程中，整數的順序不能改變。
然後回傳沒有重複整數的陣列長度。
我們來看幾個例子：
1. input: nums = [1,1,2]
output: 2
output 等於 2 因為 1 重複了，你需要把重複的移除，移除後剩下 1 和 2，長度就會是等於2。
2. Input: nums = [0,0,1,1,1,2,2,3,3,4]
output: 5
output 等於 5 因為 0、1、2、3 重複了，你需要把重複的它們移除，最後陣列的長度就會是等於5。
還有一點要注意： input 整數陣列的 order 長怎麼樣，處理過後的整數陣列的 order 應該要是一樣的。這邊有一些變數規範：第一個： 陣列的長度的範圍是 1 到 312（包含）， [1， 312]，第二個： 整數的範圍是 -100 到 100（包含）， [-100， 100]
這樣 OK 嗎？
👶：嗯，了解。請問我可以重複敘述一遍題目嗎？這樣我可以確定我的理解對不對。
👨：沒問題，請說。
👶：
就是我會得到一個整數陣列，陣列的長度是 1 到 312（包含），整數的範圍是 -100 到 100（包含）。我需要把陣列裡面重複的整數移除，只需要保留一個就好，而且移除過程中陣列的 order 是不能改變的。比如 input 是 [1, 2, 2, 3]，在移除後不能是 [2, 1, 3]。最後，我只可以使用 in-place 的方法，換句話說不能宣告新的陣列。
請問我的理解，對嗎？
👨：嗯，你理解得很好。請問你會用什麼方法來解決這個問題？
👶：
既然只可以使用 in-place 方法，我就必須針對 input 陣列操作。我覺得我可以宣告三個變數，
一個叫做 current，一個叫做 next，一個是回傳的陣列長度 k。把 current 初始化為 nums[0],
k 初始化為 nums 陣列的長度。接著，我們可以使用迴圈走訪 nums 陣列，走訪的起始 index i 應該等於 1。當每一次迭代的時候， next 會等於 nums[i]。在迴圈裡面，可以去檢查 curr 是否和 next 相同，如果相同表示重複了，k 應該 -1； 相反地，如果 curr 和 next 不相同表示 next 是新的整數，接著需要把 next 移動到前一個不重複整數的下一個 index，然後還要更新 idx 和 current。所以我這邊應該要再宣告多一個變數 idx，這個 idx 記錄的東西就是剛提到的前一個不重複整數的下一個 index，初始化為1 因為第一個不重複的 index 必為1。這樣我們就可以確保移操作結束後，前 k 個陣列整數必定是不重複的。
👨：聽起來這個 in-place 方法不錯。那你可以把這個演算法寫出來嗎？你可以用任何程式語言。
👶：好，那現在我來開始寫程式。我打算用 Java 來寫。 首先，我會寫一個 class 叫作 Solution...
```java
class Solution {
public int removeDuplicates(int[] nums) {
int numsLen = nums.length;
if (numsLen == 1)
return 1;
int k = numsLen;
int current = nums[0];
int next;
int idx = 1;
for (int i = 1; i < numsLen; i++) {
next = nums[i];
if (current == next) {
k -= 1;
} else { // not equal
current = next;
nums[idx] = next;
idx += 1;
}
}
return k;
}
}
```
那我現在跑幾個例子來驗證一下這個演算法是否可行，這邊我就用面試官你剛一開始講解的例子好了...
👨：嗯，這個演算法應該已經解決了問題。你可以講解一下這個演算法的計算和空間複雜度嗎？
👶：
沒問題。這個演算法的計算複雜度是 O(N) 因為我們只有一層迴圈走訪一次整數陣列。空間複雜度的話是 O(1) 因為我使用的是 in-place 方法，我只針對 input 的整數陣列操作，而沒有宣告
多餘的陣列。
👨：很好，那今天的面試就到這裡，拜拜～
👶：謝謝面試官，拜拜～
### 189. Rotate Array
https://leetcode.com/problems/rotate-array/
#### 自我初步檢討
- 能考慮到圓的特性應該算加分（modulus）
- 只想到了 O(N) space complexity 的解，但無法提出 O(1) space complexity 的解，扣分
- leetcode 有說至少有三種解法，但我只想到一種，扣分
- code 用太少甚至沒有用註解解釋變數
- interviwer 把5次冪講成5次方
- 感覺應該提出更多 test case 來驗證演算法
👨：你好，我是你今天的面試官。
👶：你好, 我叫祥變牆。
👨：
今天的題目是給定一個整數陣列和 k，你需要對該陣列向右旋轉 k 次，k 是一個非負整數。
我們來看幾個例子：
1. input: nums = [1,2,3,4,5,6,7], k = 3
output: [5,6,7,1,2,3,4]
第一次向右旋轉: [7,1,2,3,4,5,6]
第二次向右旋轉: [6,7,1,2,3,4,5]
第三次向右旋轉: [5,6,7,1,2,3,4]
2. Input: nums = [-1,100,3,99], k = 5
output: [3,99,-1,-100]
第一次向右旋轉: [99,-1,100,3]
第二次向右旋轉: [3,99,-1,100]
第三次向右旋轉: [99,-1,100,3]
第四次向右旋轉: [3,99,-1,100]
第五次向右旋轉: [100,3,99,-1]
這邊有一些變數規範：
1. k 的範圍是 0 到 10^5 (包含)
2. 整數的範圍是 -2^31 到 2^31 - 1（包含）
3. 陣列的長度的範圍是 1 到 10^5（包含）
這樣了解嗎？
👶：嗯，了解。請問我可以重複敘述一遍題目嗎？這樣我可以確定我的理解對不對。
👨：沒問題，請說。
👶：
就是我會得到一個整數陣列和向右旋轉次數 k ，陣列的長度是 1 到 10^5（包含），整數的範圍是 -2^31 到 2^31 - 1（包含）。k 的範圍是 0 到 10^5（包含），然後我需要對陣列向右旋轉 k 次。向右旋轉是說所有陣列所有元素都向右 shift 一個 index，最後一個整數就要 shift 到 index 0。比如 input 是 [1, 2, 3, 4]，k = 2, 旋轉結果就是 [3, 4, 1, 2]。請問我的理解，對嗎？
👨：嗯，你理解得很好。請問你打算用什麼方法來解決這個問題？
👶：
既然是旋轉，那我就想到跟圓相關的特性，就是圓旋轉一圈後會回到起始位置。對應陣列向右旋轉的話，k 如果等於陣列的長度就表示向右旋轉一圈，也就是等於一開始的自己，換句話說就是陣列的樣子不會發生變化。因此，可以計算出真正需要向右旋轉的 k。那計算的方法，我想就是使用求餘數 mod 即可，k mod nums 陣列的長度，得到的餘數就是真正需要向右旋轉的 k。那有了新的 k 之後，需要從 nums 陣列的右邊算起 k 個，這 k 個整數要放到 tmp 陣列的開頭，然後把從 nums 陣列 index 0 到 index k 放到 tmp 陣列最後的位置即完成向右旋轉 k 次。最後，再把 tmp 陣列覆蓋掉 nums 陣列的整數即可。
👨：聽起來這個方法不錯。那你可以把這個演算法寫出來嗎？你可以用任何程式語言。
👶：
好，那現在我來開始寫程式。我打算用 Java 來寫。
首先，我會寫一個 class 叫作 Solution...（code time）
那我現在跑幾個例子來驗證一下這個演算法是否可行，這邊我就用面試官你剛一開始講解的例子好了：
1. input nums = [1,2,3,4,5,6,7], k = 3
k = 3 % nums.length = 3 % 7 = 3，所以 3 是真正需要向右旋轉的次數。從右邊算起 k 個整數，也就是5， 6， 7，把他們放到 tmp 陣列, tmp = [5, 6, 7]。然後，從 nums 的 index 0 到 index k 的整數，也就是 1, 2, 3, 4 放到 tmp 的後面，tmp = [5, 6, 7, 1, 2, 3, 4]
最後，用 tmp 陣列覆蓋掉 nums 陣列即可。所以在這個 example 是 work 的。
2. input nums 是: [-1,100,3,99], k = 5
k = 2 % nums.length = 5 % 4 = 1，所以 1 是真正需要向右旋轉的次數。從右邊算起 k 個整數，也就是99，把他放到 tmp 陣列, tmp = [99]。然後，從 nums 的 index 0 到 index k 的整數，也就是 -1, 100 放到 tmp 的後面，tmp = [3, 99, -1, 100]。最後，用 tmp 陣列覆蓋掉 nums 陣列即可。因此在這個 example 也是 work 的。
跑完這兩個例子，我覺得這個演算法應該解決了這個問題。
👨：嗯，這個演算法應該已經解決了問題。你可以講解一下這個演算法的計算和空間複雜度嗎？
👶：
沒問題。這個演算法的計算複雜度是 O(N) 因為我們只有一層迴圈走訪整數陣列。空間複雜度的話是 O(N) 因為我有使用一個 tmp 陣列來暫存向右旋轉後的結果。
👨：
很好。請問你可以提出 in-place 方法，把空間複雜度壓縮到 O(1) constant space 嗎？提醒你面試時間剩下5分鐘。
👶：
額...，我想想...，額...，我想想...，我覺得以某種 swapping 的方式可能可能可以把空間複雜度壓縮到 O(1) constant space。
👨：聽起來可能可行。你現在有辦法把程式寫出來嗎？
👶：
額，時間應該不太夠了，但概念應該就是以 swapping 展開，然後可以直接操作 input 的陣列。但現在如果要寫出來應該有點困難，但方向的話我應該會以 swapping 去思考，我面試之後再思考一下。
👨：
沒關係，你提出的 swapping 概念是對的方向，你回去可以再思考一下。那今天的面試就到這裡，拜拜～
👶：好，謝謝面試官，拜拜～
## 他評01
### Interviewer
- [ ] 優點
* 很清楚說明限制，而且還說明例子給面試員聽。
- [ ] 可改進的地方
* [00:04](https://youtu.be/nqDRzJmsXBA?si=1FCiypdbhFwqPZhp&t=2): 可以不用用面試官來進行面試，這樣會有上對下的感覺。
* 也許要想一些情境，會有甚麼情形遇到第二題。例如Database的資料插入，所以需要做移除之類的。
* 第三題，面試官有給出五分鐘，但實際上不到五分鐘就結束了。
### Interviewee
- [ ] 優點
* 講解REACTO時很清楚
* Bitwise第一題很有趣，有做到Follow up, 哭啊我當下看影片想說哪裡怪怪的，想好久才發現老哥你先一步檢討了==，有很有趣的方式! 希望之後有機會可以看到即時糾錯的版本，不然我卡好久XD(我太菜)。 [Logical right shift stackoverflow c++](https://stackoverflow.com/questions/5253194/implementing-logical-right-shift-in-c)
- [ ] 可改進的地方
* [12:35](https://youtu.be/nqDRzJmsXBA?si=rWIUGSrN8w5wMfLg&t=755): 這邊可以直接繼續講一下，有一些冗詞，但缺點不大
* 第三題提出Swapping，當面試官聽到Swapping沒有質疑時其實可以盡力想想看，讓面試官知道你的努力(e.g., 比如從一開始Shift的角度去闡述題目，也許就有機會想到解法)
## 他評02
### Interviewer
- [ ] 優點
* [2:07](https://youtu.be/4GjlwNrmth8?t=2m07s)與[1:47](https://youtu.be/4GjlwNrmth8?t=1:47): interviewer講解題目的時候清楚會用例子解釋，並將過程視覺化幫助溝通。
* [16:28](https://youtu.be/4GjlwNrmth8?t=16m28s): 提醒面試剩下幾分鐘。
- [ ] 可改進的地方
* 可以把題目打在文件上比較方便看
### Interviewee
- [ ] 優點
* 英語流暢
* 有將方法視覺化寫在文件上，給interviewer了解自己的想法
* 將變數的意義與方法流程直接寫在文件上，思路清晰
* [5:59](https://youtu.be/BQF6Be5fxSc?t=5m59s): 搭配手勢加強語氣
* 能邊寫程式邊講解
* [16:27](https://youtu.be/BQF6Be5fxSc?t=16m27s): 講解仔細
* [5:08](https://youtu.be/4GjlwNrmth8?t=5m08s): 講出思路方法的由來
* [23:15](https://youtu.be/nqDRzJmsXBA?23m15s): 進一步提出空間複雜度，並解釋說明
- [ ] 可改進的地方
* [17:17](https://youtu.be/4GjlwNrmth8?t=17m17s): 可以嘗試快速用虛擬碼在五分鐘內釐清思路。直接說有點困難會讓對話難以繼續。
Sign in with Wallet
Connect another wallet