2023 年「資訊科技產業專案設計」作業 1

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1 > 貢獻者: 佛萊迪-Freddy >video: [1](https://www.youtube.com/watch?v=uaA_eWw3Rxk), [2](https://www.youtube.com/watch?v=VvXsyD1LtiQ), [3](https://www.youtube.com/watch?v=VEXz0W4YzRs) * 對話代表 : * :nerd_face: : Interviewee * :bearded_person: : Interviewer ## [409. Longest Palindrome](https://leetcode.com/problems/longest-palindrome/) (漢) ### 測驗說明、問答與程式碼實作 * :bearded_person: : 哈囉 Freddy，這是我們今天面試的題目。題目會給你一個字串 `s`，其中包含出現大寫或小寫的英文字母，請使用 `s` 中的字母拼湊出最長的迴文，並回傳它的長度。 * :bearded_person: : 同時此題有些規定，首先英文字母是要區分出大小寫的，像是文件中 `"Aa"` 這個字串就不是迴文。然後，`s` 的長度介於 1 到 2000 之間。 * :nerd_face: : 好的，稍微重複一下這個問題。題目會給我一個 `s` 的字串，這個字串可能包含大寫/小寫英文字母。我要做的事情是，找出最長的迴文，並回傳它的長度，而迴文會由 `s` 中的字母所組成。我想請問一下我這樣的理解是 OK 的嗎? * :bearded_person: : 是的沒錯。 * :nerd_face: : 好的，那我先來舉個例子好了。(舉例)。想問一下我這樣的舉例是正確的嗎? ``` s = "abccccdd" -> cccc + dd + a/b -> max length 為 7 ``` * :bearded_person: : 沒問題，這個舉例是 Ok 的。 * :nerd_face: : 好的，在寫程式之前，我想先敘述一下我的想法。我這題會使用 1. Hashmap 用途與儲存格式 2. 變數 `cnt` 的用途與舉例 3. 回傳的條件判斷 * :nerd_face: : 那我就開始寫我的程式碼。 ```python3= def longestPalindrome(s: str) -> int: hashmap = {} for char in s: if char in hashmap: hashmap[char] += 1 else: hashmap[char] = 1 cnt = 0 for key in hashmap: if hashmap[key] % 2 == 1: cnt += 1 # cnt >= 1 if cnt >= 1: return len(s) - cnt + 1 # len(s) - cnt = even_cnt + odd_cnt else: # cnt == 0 return len(s) ``` * :bearded_person: : 這個解法滿直觀的，那你能說明一下你程式碼的效率如何嗎? * :nerd_face: : 時間複雜度為 $O(n)$，空間複雜度也為 $O(n)$ * :bearded_person: : 你的程式用了兩個 for 迴圈，那有辦法只使用一個 for 迴圈去提升它的效率呢? * :nerd_face: : 將兩個 for 迴圈的判斷式寫進同一個 for 迴圈中。 ```python3= def longestPalindrome(s: str) -> int: hashmap = {} cnt = 0 for char in s: if char in hashmap: hashmap[char] += 1 else: hashmap[char] = 1 # 條件式應該是 hashmap[char] 才對... if hashmap[key] % 2 == 1: cnt += 1 else: cnt -= 1 # cnt >= 1 if cnt >= 1: return len(s) - cnt + 1 # len(s) - cnt = even_cnt + odd_cnt else: # cnt == 0 return len(s) ``` * :bearded_person: : 那如果今天實際應用上，你不能使用 Hashmap 的話，有沒有其他寫法呢? * :nerd_face: : 改使用 `t_list` 陣列，去儲存烙單的字母。之後 `t_list` 的長度就會等同於之前使用的變數 `cnt` ```python3= def longestPalindrome(s: str) -> int: t_list = [] for char in s: if char in t_list: t_list.remove(char) else: t_list.append(char) cnt = len(t_list) # cnt >= 1 if cnt >= 1: return len(s) - cnt + 1 # len(s) - cnt = even_cnt + odd_cnt else: # cnt == 0 return len(s) ``` * :bearded_person: : 那這個寫法的效率如何呢? * :nerd_face: : 時間複雜度為 $O(n)$，空間複雜度也為 $O(n)$ * :bearded_person: : 今天的面試差不多就到這邊，感謝你。 ### 初步自我檢討 #### Interviewee :nerd_face: * 卡詞太多了，`那、這個、然後、接下來呢`等贅詞也過多 (`那`也講太多，氣死...) * 思考與敘述太過沒有脈絡，思考途中也容易腦袋當機 * 打字速度與精準度要加強... * 1:25: 這邊應該要說 `cccc + dd +a/b` 可以由這些字母去組合出最長的迴文 * 2:40: 說明 `cnt` 的功能時，說話過於卡詞，以至於聽起來很混亂 * 7:45: 說明回傳資料的判斷條件時，應該要先把`len(s) - cnt = even_cnt + odd_cnt`的關係提出，這樣後續在說明時才能更加順暢 * 10:30: 在思考的時候要持續說話，避免自己看起來在放空 * 13:14: 程式碼有錯誤(`hashmap[char] % 2 == 1`才對) * 15:14: 要提一下為何這邊可以直接用 `remove()` 去刪除一字元 (Ans: 因為 `t_list` 中的所有字母一定都不同) #### Interviewer :bearded_person: * 一樣，`那、這個、然後`等贅詞太多 * 不應該一直使用 `沒問題` * 0:19: 敘述題目時沒有提到「迴文會由 `s` 中的字母所組成」 * 12:33: 不應該直接要求 Interviewee 將兩個 for 迴圈改成一個，應該改用「是否能提精簡程式碼」等詞彙去敘述 * 13:55: Interviewee 的程式碼有明顯的錯誤，但沒有發現並提出 --- ## [150. Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/) (漢) ### 測驗說明、問答與程式碼實作 * :bearded_person: : 哈囉 Freddy，這次的面試就交給我來主持，那就廢話不多說，趕快來看題目吧。 * :bearded_person: : 在我們共享文件中可以看到題目的敘述。我們公司最近遇到了些小困難，有個介面是要由消費者輸入一些數值的，我們需要對這些數值進行運算。為了節省儲存空間，我們將一班的運算式轉換為反轉波蘭表達式去儲存。然而，現在需要計算出該表達式的值，那你有沒有什麼想法呢? * :bearded_person: : 題目會給定一個反轉波蘭表達式的字串陣列 `tokens`，請你計算出該表達式的值。(提醒其他限制。) * :nerd_face: : 好的，我稍微整理一下剛剛提到的題目好了。你會給我一個字串陣列 `tokens`，它會用反轉波蘭表達式來表示一個運算式。我要做的事情，就是去計算出這個表達式最後的答案為何。這樣我的理解是對的嗎? * :bearded_person: : 沒錯，這就是我要的。 * :nerd_face: : 那我再舉個例子好了。(舉例)我要做的事情是這樣沒錯吧? ``` tokens = ["3", "4", "*", "6", "/"] => Ans: 2 ``` * :bearded_person: : 是的沒錯。 * :nerd_face: : 那在寫程式碼之前，我先說一下我的想法好了。我會使用 Stack 當儲存空間，當中放置碰到的運算元。接著會用一個 While 迴圈去依序逐一走訪每個元素。若是運算元，就 Push 到 Stack 中；若碰到運算子，則先 Pop 兩個運算元出來，對他們兩個進行那個符號的運算，最後把結果 Push 回 Stack 中。等走訪完後，Stack 中只會剩下一個值，即為答案 * :bearded_person: : 聽起來滿合理的，那你可以趕快寫你的 Code 了。 * :nerd_face: : 那我就開始寫我的程式碼。 ```python= def calculate(a, b, token): # 這邊宣告錯誤 if token == "+": return a + b elif token == "*": # 這邊輸入錯誤 return a - b elif token == "*": return a * b else: #/ return int(float(a) / b) def eval(tokens: List[str]) -> int: stack = [] # 運算元 op = [“+”, “-”, “*”, “/”] for token in tokens: if token not in op: # 運算元 stack.append(int(token)) else: # 運算子 b = stack.pop() a = stack.pop() res = calculate(a, b, token) # +-*/ stack.append(res) return stack[0] ``` * :bearded_person: : 你可以敘述程式碼效率為何嗎? * :nerd_face: : 由於 for 迴圈會逐一走訪每個元素，故時間複雜度為 $O(n)$。而空間複雜度會受到表達式的影響，最糟的狀況應為 $O(n)$。 * :bearded_person: : OK，那你程式中有使用到 `calculate()` 函式中使用了 if/else去計算。如果今天公司要去新增其他的運算子，那你要怎麼修改成更彈性的計算方式呢? * :nerd_face: : 我會使用把 `op` 改成用 dictionary 的形式，其中儲存方式改用 key = 運算子、value = 對應的 `lambda` 函式。 ```python= def eval(tokens: List[str]) -> int: stack = [] # 運算元 op = { "+" : lambda x, y: x + y, "-" : lambda x, y: x - y, "*" : lambda x, y: x * y, "/" : lambda x, y: int(float(x) / y) } for token in tokens: if token not in op: # 運算元 stack.append(int(token)) else: # 運算子 b = stack.pop() a = stack.pop() res = op[token](a, b) # +-*/ stack.append(res) return stack[0] ``` * :bearded_person: : 這個寫法確實能提升效率，那你可以敘述改善解法的效率為何嗎? * :nerd_face: : 時間複雜度為 $O(n)$。而空間複雜度也是 $O(n)$。 * :bearded_person: : 好，那我們今天的面試就到這邊，謝謝你。 ### 初步自我檢討 #### Interviewee :nerd_face: * 講話贅字一樣太多了 * 卡詞問題 * 要多練習邊寫程式邊講解 * 10:36: 運算元處理這塊要講得更通順一點 * 13:39: 函式宣告錯誤，應為 `def calculate(a: int, b: int, token: str) -> int` * 14:10: 這邊判斷式應為 `elif token == "-"` * 16:27: Calculate 發音 * 23:22: 用這種寫法最大的優點是彈性 (要增加運算子變得更加容易) #### Interviewer :bearded_person: * 這次比起第一次，有試著提高互動性，敘述題目時有配合一個情境 * 講話贅字一樣太多了 * 卡詞問題 * 0:12: 花過多時間講故事，應該要簡易說明即可 * 13:39、14:10: 沒有發現 Interviewee 的程式碼錯誤 --- ## [217. Contains Duplicate](https://leetcode.com/problems/contains-duplicate/) (英) ### 測驗說明、問答與程式碼實作 * :bearded_person: : Hi, I'll be your interviewer for today. And let me walk through the question for today. Recently, our company is sorting out files on employees' computers, and we often find that there are multiple copies of the same file with the same name on the computer. We hope to determine whether a file appears at least twice by scanning the IDs of all files. Therefore, here I gather the IDs of all files in a computer, and turn them into an integer array `nums`. * :bearded_person: : What you gonna do is to return `true` if any value appears at least twice in the array, otherwise return `false` if every element is distinct. It should be noted that the length of `nums` is between 1 and 10,000, and then each element in `nums` will be bounded by plus or minus one billion. So, That's basically the question. * :nerd_face: : Sure, let me repeat the question. You'll give me an array of integer called `nums`, and I need to find whether there are at least two elements that are the same. And let me take an example. (舉例). Is my understanding correct? ```python nums = [1, 3, 4, 2, 1] => True (1 duplicate) nums = [1, 2, 3, 4] => False (distinct) ``` * :bearded_person: : That's what I mean. * :nerd_face: : Before I start coding, I'd like to explain my approach first. So, I'm going to sort the array first. Its elements will be sorted in ascending order. Then, I'll use the for loop to visit all the element in the array. If the former is the same as the latter, we could just return `True`. And after finishing the loop, we could say there are no duplicate elements in the array. * :nerd_face: : So, let me implement it. ```python= def contain(nums: List[int]) -> bool: nums.sort() for i in range(len(nums) - 1): if nums[i] == nums[i + 1]: return True return False ``` * :bearded_person: : Yeah, I think it's pretty reasonable. Could you help me walk through your solution with the example you just give? * :nerd_face: : Sure. (將前面舉的範例套用至解法)。 * :bearded_person: : Seems great. And could you help me walk through the complexity of your solution? * :nerd_face: : The time complexity will be $O(n \log n)$, and the space complexity will be $O(1)$ ($n$ = `len(nums)`) * :bearded_person: : If now I don't want to sort the array with $O(\log n)$ time complexity, is any way that you think you could optimize your solution into $O(n)$? * :nerd_face: : How about using the set? Because we could be sure that every element in a set will be distinct. And we could add element into a set gradually. If I find an element that already exists in the set, we could say that `nums` contain duplicate elements. * :bearded_person: : Sounds good. Could you help me implement it? * :nerd_face: : Sure. ```python= def contain(nums: List[int]) -> bool: temp_set = set() for num in nums: if num in temp_set: return True temp_set.add(num) return False ``` * :bearded_person: : That's good. Could you help me walk through this solution with the example you just mention? * :nerd_face: : OK. (將前面舉的範例套用至解法)。 * :bearded_person: : And how about the complexity of your solution? * :nerd_face: : The time complexity will be $O(n)$, and the space complexity will be $O(n)$ ($n$ = `len(nums)`) * :bearded_person: : OK, that is the interview today. Thank you for your time. ### 初步自我檢討 #### Interviewee :nerd_face: * 這次有將 Time/Space Complexity 寫在文件中 * 講話贅字太多、卡詞問題 * 英文發音要加強 * 講到後面許多英文發音歪掉了，像是 element (`ˈeləmənt`) 都變成了 `ˈæləmənt`、duplicate 都糊在一起 * 單字間連音也要注意 * 邊寫程式邊用英文敘述的能力要加強 #### Interviewer :bearded_person: * 講話贅字一樣太多了 * 卡詞問題 * 前面鋪陳故事的部分轉得有點硬要 ## 第二次作業-他評01 ## interviewer ### 優點 1.有直接根據code 給出公司的要求，要求interviewee做進一步優化討論 2.問題闡述詳細 ### 可改進之處 [14:06](https://youtu.be/uaA_eWw3Rxk?si=CKOJaV1pwtTJxdQF&t=846): 如果只問"你有其他辦法嗎"，若是在撰寫過程中沒有發現或想到其他辦法的話，此時還是一頭霧水，所以interviewer可能可以指出特定的點，要interviewee做出優化 [0:08](https://youtu.be/VvXsyD1LtiQ?si=frVMS0ugPcq5shSN&t=8):開頭有點太像主持一個show，會給人一種不太認真(嚴肅)的感覺在英語口說的時候，一句話中"強調"的字通常是關鍵字，但同學"強調"的字眼卻可能是連接詞或語助詞，會比較無助於抓重點。 ## interviewee ### 優點 1.分析時間複雜度時的分析很清楚詳細，不會只吐出一個答案 2.有主動做Test ### 可改進之處 [3:45](https://youtu.be/uaA_eWw3Rxk?si=PzjHd6NrJ6o0X82U&t=225):建議可以停頓觀察interviewer的反應，也許對方會提出質疑或是不同的看法在邊打code 邊解釋的時候可以更有自信一些，避免一些思考時的贅字，會顯得對自己的東西不太確定，以及與其卡在一個詞，不如放慢語速想好再講完。在打code 的時候，有時候會變成喃喃自語 ## 第二次作業-他評02 ## interviewer ### 優點 - 有些地方有適度的引導面試者。 - 仔細講解面試的題目。 ### 可改進之處 - 有些地方的引導太模糊，面試者如果沒想那麼多就會想不到。 (這點不一定不好) ## interviewee ### 優點 - REACTO 做的不錯。 - 有邊寫程式邊講解。 - [16:09](https://youtu.be/uaA_eWw3Rxk?si=MzmA4BEi1fWzjrSV&t=969) 手勢讓人感覺有在思考 ### 可改進之處 - 有些英文的發音怪怪的，雖然還是聽得懂

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.