# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 節瓜-Zebra
>[模擬面試影片(英)](https://www.youtube.com/watch?v=W_ZCrJodw1A)
>[模擬面試影片(漢)](https://www.youtube.com/watch?v=UoEk9QRiWrg)
## [9. Palindrome Number](https://leetcode.com/problems/palindrome-number/)
### Interviewer
你好，我是xxx的工程師，今天由我來主持這場面試。那我們就簡單測試一下你的程式邏輯吧！首先我想問，假設今天有間銀行，他們希望在世界完全對稱日2030年3月2日舉辦ATM抽獎活動讓客戶玩，如果客戶領完錢後當下帳戶的餘額數目正讀跟反讀都是一樣的話則可以參加抽獎。請設計一個可以檢查這樣的餘額的程式。
### Interviewee
*Repeat :*
好的，所以您是希望我讀入一個整數，然後將這個整數reverse後，觀察是否與讀入的整數相同嗎？
### Interviewer
是的，沒錯。
### Interviewee
*Example :*
好的，我這邊舉個例子確認一下我的理解是否正確。當Input: x = 121時，Output會是true，而當Input: x = -121時，Output會是false，這樣對嗎？
### Interviewer
是的，沒錯。
### Interviewee
*Approach* :
好的，我選擇使用python進行編碼。首先我會先將x以str()轉換為字串型別，再用list()將剛才的結果轉換為list型別，接著分別存放到a跟b兩個變數之中。由於list可以直接用reverse()做反轉處理，所以就將a做reverse()，並且跟b，也就是原本的餘額數目做比較。最後只要回傳是或否就好，所以就return(a==b)。
### Interviewer
OK，那我們開始coding吧。
### Interviewee
```python
class Solution(object):
def isPalindrome(self, x):
a=list(str(x))
b=list(str(x))
a.reverse()
return(a==b)
```
### Interviewee
*Test* :
這樣就完成code了，為了驗證我的想法，舉例來說，假設有一個帳戶餘額是951159，先變成str和list型別後分別存放到a和b這兩個變數，接著會將a做reverse變成951159再和b做比較，透過```a==b```我們可以得到true的結果。
那假設另一個帳戶餘額為321146，先變成str和list型別後分別存放到a和b這兩個變數中，接著會將a做reverse變成61123再和b做比較，透過```a==b```我們可以得到false的結果。
那假設第三個帳戶餘額為0，0經過reverse後還是0，會得到true的結果並可以參加抽獎，為了防止大家把錢領光建議您可以在前面多用一個條件式檢查餘額。
### Interviewer
好的，謝謝。這邊我想請問一個問題，今天我們客戶的ATM比較老舊，我希望您可以再用更加快速的方法來去解決這個問題，你會如何改進呢？
### Interviewee
*Optimization* :
我想，餘額為負數以及個位數為0的金額可以直接return False。再來創建一個變數result並初始化為0，用來儲存反轉的部分。
接著進入一個循環，條件是x大於result。在循環中，將result乘以10，相當於將 result 的數字部分向左移一位，然後將x的最後一位數字加到result上，這樣就實現了反轉操作。
同時，將x用//10的方式將最後一位數字去掉，以繼續處理下一位數字。
循環結束後，比較x是否等於result或者是否等於result的一半。如果是其中之一，則表示x是迴文，return True，否則return False。
```python
class Solution(object):
def isPalindrome(self, x):
if x < 0 or (x > 0 and x % 10 == 0):
return False
result = 0
while x > result:
result = result * 10 + x % 10
x = x // 10
return x == result or x == result // 10
```
### Interviewer
你認為為何這樣會比較快呢？
### Interviewee
首先，雖然它們的時間複雜度都是 O(log10(x))，但是跟第一個程式相比，第二個程式只需處理一半的數字，且第二個程式只使用了一個整數result來存儲反轉的一半數字，因此不需要額外的空間。再者，第一個程式創建了兩個list，a和b，並將整數轉換為字串，這需要額外的空間來存儲字串和 list。最後，第二個程式中是通過整數操作來實現的，而在第一個程式中是通過字串操作來實現的。整數操作通常比字串操作更高效。
## [234. Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list)
### Interviewer
好的，那接下來我們進入下一題。假設這間銀行有一個ATM無卡提款的交易系統，每當客戶需要使用ATM無卡提款服務時，系統將生成一個隨機的驗證碼（OTP）。這個OTP將寄送6位數字到客戶的手機簡訊，客戶在驗證時需要依次輸入簡訊內顯示的數字，以驗證交易的合法性。
為了應景世界完全對稱日，您的任務是設計一個程式模擬客戶輸入OTP的過程，檢查他們按照順序輸入的數字是否為迴文，如果是的話就獲得一次抽獎機會，但我們希望抽獎次數有限，所以使用過的迴文數字不會重複使用。為了簡單了解你的想法，先不設限6位數字，你會怎麼做呢？
### Interviewee
*Repeat :*
好的，所以您是希望我依序讀入一串整數，然後檢查這些整數是否為迴文嗎？
### Interviewer
是的，沒錯。
### Interviewee
*Example :*
好的，我認為linked list很適合這種情況，可以用於儲存使用過的迴文數字，我這邊舉個例子確認一下我的理解是否正確。當客戶依序輸入[1,2,2,1]，Output會是true，當客戶依序輸入[1,2]，Output會是false，這樣對嗎？
### Interviewer
是的，沒錯。
### Interviewee
*Approach* :
我會先創建一個空array來存儲鏈接列表中的值，然後設置一個指針來遍歷鏈接列表，並在遍歷的過程中將每個節點的值添加array中。接著用（[::-1]）來獲得array的反向版本。然後，他們將原始array和反向array進行比較，如果它們相等，則鏈接列表是回文的，否則不是。
### Interviewer
OK，那我們開始coding吧。
### Interviewee
```python
class Solution(object):
def isPalindrome(self, head):
num = []
ptr = head
while ptr:
num.append(ptr.val)
ptr = ptr.next
return num == num[::-1]
```
### Interviewee
*Test* :
這樣就完成code了，為了驗證我的想法，舉例來說，假設客戶依序輸入[3, 1, 8, 8, 1, 3]，num在新增第一個數字3之後，會因為指針指向下一個數字ptr.next，繼續將下一個數字1新增到num中，直到遍歷整個linked list，while迴圈才會結束。最後就比對num和反向num是否相同，是就回傳True，否則回傳False。
### Interviewer
好的，謝謝。你這邊用到了兩個陣列來儲存linked list的所有節點值，一個正向，一個反向。有沒有可能只用一個陣列就能解決呢？
### Interviewee
*Optimization* :
好的，設置兩個指針：一個用於遍歷鏈接列表（p），另一個用於實現鏈接反轉（prevNode）可以符合您的要求。
我會使用一個循環來遍歷linked list，並將每個節點的值添加到陣列中，這樣我們就可以在後續比較中使用它們。同時，我們也需要實現鏈接的反向，因此在這個循環中，我們會將當前節點的下一個節點指向前一個節點，這樣就實現了鏈接反轉。
當鏈接列表遍歷完畢並完成反轉後，我們擁有原始陣列和反轉後的linked list。最後我們只需比較這兩個陣列是否相等。如果它們相等，則linked list是回文的；否則不是。
```python
class Solution(object):
def isPalindrome(self, head):
array = []
p = head
while p:
array.append(p.val)
p = p.next
prevNode = None
currNode = head
while currNode:
nextNode = currNode.next
currNode.next = prevNode
prevNode = currNode
currNode = nextNode
#print prevNode
array2 = []
p = prevNode
while p:
array2.append(p.val)
p = p.next
if array == array2:
return True
```
### Interviewer
好的，謝謝你今天的時間，後續結果我們將寄email給您。
## [763. Partition Labels](https://leetcode.com/problems/partition-labels)
### Interviewer
你好，我是xxx的工程師，今天由我來主持這場面試。那我們就簡單測試一下你的程式邏輯吧！首先我想問假設您是一家資料安全公司的工程師，負責設計一個安全的消息傳輸系統。在這個系統中，資料消息被加密並分割成多個部分，然後傳送到接收端，接收端需要將這些部分重新組合成原始消息並解密它。
為了增加安全性，我希望確保每種字母最多只在一個部分出現，以防止潛在的資料泄露或破解，請你告訴我分割後每一個部分的長度。
### Interviewee
*Repeat :*
好的，所以您是希望我讀入一個字串，然後將這個字串分割後，使得每一個部分內出現的字母只在那個部分出現，並且告訴您分割後的每一個part的長度嗎？
### Interviewer
是的，沒錯。
### Interviewee
那請問分割的group數量是盡可能多嗎？
### Interviewer
是的，沒錯。
### Interviewee
*Example :*
好的，我這邊舉個例子確認一下我的理解是否正確。當Input是"ababcbacadefegdehijhklij"時，Output會是[9,7,8]，因為分割的結果是"ababcbaca", "defegde", "hijhklij"，但如果分割成[16, 8]是錯的，因為還可以再分割。請問是這個意思嗎？
### Interviewer
是的，沒錯。
### Interviewee
*Approach* :
好的，首先我會用一個for迴圈遍歷字串，會有個i紀錄索引，c紀錄目前字符。迴圈外有一個j跟蹤當前區間的起始，end紀錄當前區段的結束。迴圈中，更新變數j，使其保持當前字符c最後出現的位置索引，如果遇到i等於j，就表示當前位置end是此區間的結尾。與此同時，我們可以計算此區間的大小，並再用一個變數儲存。更新end作為下一個部分的起始索引，直到遍歷完整個字串，儲存每區間大小的變數就是我們要的答案。
### Interviewer
OK，那我們開始coding吧。
### Interviewee
```python
class Solution(object):
def partitionLabels(self, s):
indexes = {c : i for i, c in enumerate(s)}
j = end = 0
ans = []
for i, c in enumerate(s):
j = max(j, indexes[c])
if i == j:
ans.append(i - end + 1)
end = i +1
return ans
```
好的，我選擇用Python撰寫我的code。首先，我會創建一個字典indexes來存儲每個字母在字串中最後出現的位置索引。
使用j和end，跟蹤當前區段的起始和結束索引。再用一個ans來存儲每個區段的大小。
隨後使用一個迴圈遍歷字串 s，同時記錄當前字符的索引i和字符c。
在迴圈中，用 j = max(j, indexes[c])更新變數j，使其保持當前字符c最後出現的位置索引。
如果 i 等於 j，就表示當前位置是部分的結尾。與此同時，我們可以計算此區間的大小，並將其添加到 ans 列表中。接著，更新 end 為下一個部分的起始索引，loop直到遍歷完整個字串就停止。ans就是我們要的答案。
### Interviewee
*Test* :
用我剛才舉的例子，當字串為ababcbacadefegdehijhklij時，
* i = 0, c = 'a'
* j = max(0, 8) = 8，i 不等於 j，不處理。
* i = 1, c = 'b'
* j = max(8, 5) = 8，i 不等於 j，不處理。
* i = 2, c = 'a'
* j = max(8, 8) = 8，i 不等於 j，不處理。
* i = 3, c = 'b'
* j = max(8, 5) = 8，i 不等於 j，不處理。
* i = 4, c = 'c'
* j = max(8, 7) = 8，i 不等於 j，不處理。
* i = 5, c = 'b'
* j = max(8, 5) = 8，i 不等於 j，不處理。
* i = 6, c = 'a'
* j = max(8, 8) = 8，i 不等於 j，不處理。
* i = 7, c = 'c'
* j = max(8, 7) = 8，i 不等於 j，不處理。
* i = 8, c = 'a'
* j = max(8, 8) = 8，i 等於 j，此時部分結束。
* 第一部分大小為 8 - 0 + 1 = 9，將 9 添加到 ans 中。
* 更新 end 為 i + 1，即 end = 9。
### Interviewer
好的，謝謝。麻煩你用一個stack解決這樣的問題。
### Interviewee
*Optimization* :
```python
class Solution:
def partitionLabels(self, S):
# diff用來存儲每個字母在字串中第一次出現和最後一次出現的索引範圍
diff = []
for i in set(S):
# 找到字母i在字串中的第一次出現的索引和最後一次出現的索引
first_index = S.index(i)
last_index = S.rindex(i)
# 將這個字母的索引範圍添加到diff列表中
diff.append([first_index, last_index])
# 將diff列表按照第一次出現的索引升序排序
diff = sorted(diff, key=lambda x: x[0])
# 初始化一個堆疊(stack)列表，用來存儲合併後的索引範圍
stack = [diff[0]]
# 遍歷diff列表的其餘部分，並進行合併操作
for i in diff[1:]:
if i[0] <= stack[-1][1]:
# 如果當前索引範圍的第一個索引小於等於堆疊中最後一個索引範圍的最後一個索引，則合併這兩個範圍
a, b = stack.pop()
stack.append([min(i[0], a), max(i[1], b)])
else:
# 如果當前索引範圍不與堆疊中的範圍重疊，則將其添加到堆疊中
stack.append(i)
# 計算堆疊中每個索引範圍的大小，並存儲在stack列表中
stack = [x[1] - x[0] + 1 for x in stack]
# 回傳最終的stack列表，其中包含了每個部分的大小
return stack
```
## 檢討
* 改進的部分多是參考他人的code，自己沒什麼想法，但是學到不少厲害的用法。
* 有些數學英文的念法不太知道需要再多練習，比如：%是mod不是divide也不是percent。
* 發現自己面試的時候有點死板，沒有足夠的肢體語言。
* 英文對話的時候很常詞窮，比如::1不知道怎麼念，後來查到應該唸"colon colon one"。
* 面試中寫code的時候發現有些不是很懂的地方心虛會含糊帶過。
* 下次會再更早開始寫作業，這次趕在deadline前完成，有些錯誤的地方只能先將錯就錯。
* 用剪輯軟體剪完影片之後才發現需要我付費解除浮水印，導致影片中的程式碼被遮擋，之後再問問同學都用什麼軟體。
---
## 第二次作業-他評 01
### 關於 interviewer
- [ ] 優點
* 題目講得很好，有避免提出關鍵字。
* 頭飾實在是太酷了。
* 兩題用英文好強。
- [ ] 可改進的地方
* 有個中國的剪輯軟體「剪映」，他的功能和版面基本上都跟你使用的wondershare相同，且沒有浮水印，差別只是素材庫幾乎都是中國那邊的歌曲跟抖音特效。(我也是跟你一樣先用了wondershare才發現浮水印真的很大XD)
### 關於 interviewee
- [ ] 優點
* 邊寫程式邊說明很棒。
* REACTO做得蠻完整的。
* 程式碼字體大，清楚。
* 後面英文用記事本打程式，就不會像word會一直糾正，好聰明。
* (漢語) 舉例解釋很清晰。
* (英語-1) 兩個方法，兩種解題思路很棒。
- [ ] 可改進的地方
* window能夠關閉英文單字開頭大寫的功能。
## 第二次作業-他評 02
### 關於 interviewer
- [ ] 優點
* 語速適中
* 邊界定義清楚
- [ ] 可改進的地方
* 題目可以附上文件已方便討稐
### 關於 interviewee
- [ ] 優點
* REACTO步驟都有做到
- [ ] 可改進的地方
* 優化後未進行驗證的部份
Sign in with Wallet
Connect another wallet