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

貢獻者：月退 - Leg
:cat:：interviewer
:dog:：interviewee

1. Two Sum

模擬面試錄影(英)

模擬面試過程

:cat:：Hi, Leg! It's great to see you here. I have a few questions for you. We can discuss solutions together. If you have any questions later on, feel free to interrupt me and ask.
:dog:：Great, I understand.
:cat:：In our daily lives, we often encounter the challenge of setting goals, and we hope that the goals we find meet our expectations. This is similar to when we search for employees, and when you search for a job, we both confirm whether or not it meets our expectations.
:dog:：Exactly, we are both going through a process of confirmation.
:cat:：Based on this premise, I hope you can answer the following question: Assuming I have a List with many non-repeating numbers, I want to find two numbers whose sum equals the input target number. Additionally, return the positions of these two numbers.
:dog:：(Repeat)So, our input will consist of a sequence of numbers in List format and a number target. We hope to find two numbers from the List that, when added together, equal target. Finally, we need to return the positions of these two numbers within the List. Is that correct?
:cat:：Yes, your understanding is correct.
:dog:：(Example)So, if the input List is [4,1,3] and target=4, then the expected output should be [1,2] instead of [0]. This is because [0] contains only one number. Is that right?
:cat:：Yes, your assumption is correct.
:dog:：(Approach)I would like to start by using a dictionary in python to record the position of each number, where the key is the number in the List and the value is its position. Next, I'll iterate through the numbers in the List and calculate the difference between target and the number in the List. Then, I'll check if the difference is in the dictionary. If not, I will continue searching. If it is, I will return the current position and the position of the subtracted number.
:cat:：It sounds quite reasonable. So, please go ahead and code the idea you just mentioned.
:dog:：(Code)
首先，我need a dict whose name is nums2id，and the length of nums,so for … the key of nums2id is the number in nums,the value of nums2id is the position of this key number
i want to calculate the difference between target and each element in nums
for …
we need to ckeck that the position of difference and i are different

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums2id = {}
        n = len(nums)
        for i in range(0, n):
            nums2id[nums[i]] = i
        for i in range(0, n):
            difference = target - nums[i]
            if difference in nums2id:
                if nums2id[difference] != i:
                    return [i, nums2id[difference]]

:dog:：We can use the example I just provided to verify. nums=[4,1,3], target=4, so nums2id[4]=0, nums2id[1]=1, nums2id[3]=2. Then we traverse through nums, when i=0, complement=0. Since 0 is not in nums2id, we proceed to i=1. At this point, complement=3, and 3 is in nums2id. Moreover, the positions of 1 and 3 are different, so we return [1,2], representing the positions of numbers 1 and 3, respectively.
:cat:：Alright, then I'd like to ask you to analyze the time complexity and space complexity of this function.
:dog:：Because we only need to iterate through nums once, the time complexity is O(n). Additionally, since there is no extra memory allocation, the space complexity is O(1).
:cat:：Then there's no further questions. Let's conclude here for today.Thank you for coming by.
:dog:：Thank you, and I hope to see you again.

9. Palindrome Number

模擬面試錄影(漢)

模擬面試過程

:cat:：你好月退，今天是由我來問你一些問題，如果對我的描述有疑問都可以直接打斷我，沒關係。
:dog:：好的，我瞭解了。
:cat:：那你在來面試前應該知道我們公司是做語言相關的對吧？那在語言中有個特別的概念叫做迴文，也就是你正著唸或是倒過來唸，結果都是一樣的，如果我們今天想要知道這個句子或是符不符合迴文的現象，你會想要怎麼做呢？
:dog:：(Repeat) 好的，那我想再做一次確認，看我的理解有沒有錯誤。也就是說，現在我要檢驗一個句子，它從第一個字唸到最後一個字，和從最後一個字唸回第一個字，是否相同這樣對嗎？
:cat:：你的理解沒錯。
:dog:：(Example)所以如果以英文來舉例的話就是像是，level或是deed，如果我以數字來舉例的話，就會像是1221或是212這樣對嗎？
:cat:：是的，你的舉例都是合理的。你可以用數字的方式來解釋你的想法或是解法。
:dog:：那我想確認一下，輸入數字包含小於零的數字嗎？
:cat:：包含小於零的數字。
:dog:：(Approach)好的，那第一個我想到的是，可以使用數學的計算。首先，如果數字小於零，那他一定不會是迴文，所以直接return False就可以了，如果大於等於零的話，就不斷地將數字除以10並取餘數的方法來取得輸入數字的個位數字、十位數字、百位數字…，取得個位數字時將它存起來，取得十位數字的時候，將個位數字乘以10加上十位數字並存起來，以此類推…，就可以得到反過來的數字了，最後只要驗證得到的數字和輸入數字是否相同就可以了。
:cat:：聽起來蠻合理的，但有點複雜，你可以把你剛剛說的方法實作出來嗎？
:dog:：(Code)好的沒問題

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        old_x = x
        tmp = 0
        while x > 0:
            tmp = 10 * tmp + x % 10
            x = x // 10
        if tmp == old_x:
            return True
        else:
            return False

:dog:：那這邊講幾個例子，假如x設為121，那就先將x紀錄為old_x，一開始tmp設為0，因為121大於0所以進入迴圈，接著可以利用%這個工具取得除以10的餘數，也就是個位數的1，所以此時tmp是1，接著將121除以10並取整數商得到12，再次進入迴圈，重複剛剛的動作，可以得到tmp是12，這是由剛剛10*tmp等於10加上12%10等2得到的，最後x更新為1，一樣進入迴圈，重複剛剛的動作就可以得到tmp=121，最後就會回傳True。
:cat:：看起來沒有什麼問題，那我想問你，你覺得你的這份code可能會有什麼淺在的問題呢？
:dog:：嗯，我覺得可能會相對比較複雜一點，因為過程中都是數學計算，對於其他人來說可能會比較沒那麼容易一眼就看懂。
:cat:：這確實是可能的問題，那你有辦法提供更簡潔易懂的其他解法嗎？
:dog:：我想到的是，可以將數字轉換成字串，直接去比較第一個字和最後一個字，第二個字和倒數第二字，以此類推下去，如果都相同就是迴文，如果有一個不同就不是迴文。
:cat:：這樣確實有比較好理解，那請你實做看看。
:dog:：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        number = str(x)
        length = len(number)
        
        for i in range(length // 2):
            if number[i] != number[length - i - 1]:
                return False
        
        return True

:dog:：這樣就可以達到比較的效果了，也相對於第一個解法更直覺一點。不過如果要達到剛剛講的效果，其實python中對字串的切片功能也可以達到將字串反過來。
:cat:：那請你實做一下這個功能如何操作呢？
:dog:：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        y=str(x)
        if y==y[::-1]:return True
        else:return False

:cat:：這樣程式碼看起來是更加簡潔了。好，那我今天就大概到這裡為止，你有什麼問題想問的嗎？
:dog:：沒有了。
:cat:：好的，那期待能再看到你。掰掰
:dog:：謝謝，掰掰。

2. Add Two Numbers

模擬面試錄影(漢)

模擬面試過程

:cat:：嗨，又見面了，這次是最後的面試了。你會很緊張嗎？
:dog:：有一點緊張又有一點期待。
:cat:：好，那之前有一次是要你找出，兩個數字加起來等於目標的題目，你還記得嗎？
:dog:：記得。
:cat:：那這次希望請你做看看把兩個數字加起來。但不是簡單的單純用加法加起來。會給你兩個數字，但這兩個數字是用 linked list 來表示的，像是325，會表示成node5指向node2指向node3，接著你需要把這兩個數字加起來，並且再用一樣概念的 linked list 表示。
:dog:：(Repeat)好的，所以我會拿到兩個數字順序是反的的 linked list ，最後要回傳這兩個數字相加後的數字的 linked list 。這樣對嗎？
:cat:：是的沒錯。
:dog:：那我可以先把數字325用[5,2,3]來表示嗎？
:cat:：可以。
:dog:：(Example)好的，那我先舉個例子來確認我的理解有沒有錯，假設輸入[5,2,3]、[6,1,7]分別代表325和716，最後我要輸出[1,4,0,1]，因為325+716=1041，這樣對嗎？
:cat:：沒錯。
:dog:：(Approach)好的，那假設輸入[5,2,3]，我等等會把325稱為「原始數字」這樣來表示。首先，需要先定義一下這個代表數字的 linked list ，它會有val用來代表數值，next用來代表指向誰。接著我們的輸入就是符合這個定義的 linked list 。得到兩個輸入後，我會想先把它們改寫成int的格式，因為這樣相加起來會變得很容易。那要把他們變成int的格式就需要分別跑過兩個輸入的所有node，先利用字串的加法會是直接把兩個字串接起來，我們可以把後面node的val一直加在字串的前面，這樣就可以得到代表原始數字的字串格式，接著再利用python內建函示把它轉成int格式就好。之後將轉換好的兩個原始數字相加，接下來就是要把答案轉換成 linked list ，因為 linked list 需要把答案反過來接起來，因此可以利用之前使用過的取餘數的方式來取得最後數字一位，接著再依序接起來就可以了。
:cat:：聽起來沒什麼問題，那就直接起你實做看看吧。
:dog:：(Code)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        num1 = ""
        num2 = ""
        while l1 != None:
            num1 = str(l1.val) + num1
            l1 = l1.next
        while l2 != None:
            num2 = str(l2.val) + num2
            l2 = l2.next
        num = int(num1) + int(num2)
        
        res = ListNode(0)
        head = res
        if num == 0:
            return res
        while num > 0:
            rem = num % 10
            tmp = ListNode(rem)
            res.next = tmp
            res = res.next
            num = num // 10
        return head.next

:dog:：那我們用[5,2]、[6]來檢驗看看，l1=[5,2]，第一次進到while後，num1="5"，第二次num1="25"，因為"2"+"5"，類推可以得到num2="6"，接著num=31，接著我們先建立一個假的 head ，利用取餘數的方式取得rem=1，並建立一個新的node，tmp.val=1，再將它和res接起來，此時我們會得到0指向1，接著更新num=3，取得rem=3，並將新的node，tmp.val=3，再和res接起來，就會得到0指向1指向3的 linked list，最後只要回傳1指向3的部分就好，所以我們回傳head.next。
:cat:：好的，那我想問你，為什麼需要res和head這兩個 linked list呢？
:dog:：哦，因為我們在接node的時候，res指向的位置會不斷地往後更新，所以最後他會停在我剛剛舉例的3的位置，如果直接回傳res會是錯的，但因為一開始有讓head指向0的位置，所以只要回傳head.next就可以得到1的位置，就會是正確的答案
:cat:：好的，那沒什麼問題了，今天就先這樣，辛苦了
:dog:：不會，你也辛苦了，謝謝。

---

第二次作業-他評01

:warning: 英文影片的連結有誤

關於interviewee

• 優點

• 口齒清晰，對於題目的要求非常簡單易懂
• 有把題目融入公司的相關背景

關於interviewer

• 優點

• 有重複確認題目要求，並舉例子來確認其正確性

• 可改進的地方

• 01:51: 這邊可以考慮開一份文件把描述的內容用畫面表示出來，這樣面試官可能比較好理解

第二次作業-他評02

關於interviewee

• 優點

• 是我看到互動感最好的面試者!!!

• 可改進的地方

• 左下角不小心露出名子了

關於interviewer

• 優點

• 畫面很大很清楚!!!
• 邊打程式邊打註解配合講解讓人容易聽懂

• 可改進的地方

• 再重複題目以及講解想法時，感覺可以加點畫面打點字

第二次作業-他評03

關於interviewee

• 優點

• 講解不錯，不論是暴力解或者優化解講都可以讓完全不知道狀況的人，很容易明白

• 可改進的地方

• two sum 利用hashmap解，空間複雜度應該會因為要存入hashmap的數量有關，因此為O(n)比較合理

關於interviewer

• 優點

• 說明題目很清楚，可以讓interviewee有follow題目規則。
• 當過程卡關有適時提出暗示，讓整場面試不至於卡關，產生兩人對談的良好互動

• 可改進的地方

• 針對add two numberS 空間複雜度應該有更優解O(1)，可以提出跟面試者討論

第二次作業-他評04

Interviewer

• 優點

• 講解符合實際公司情況。
• 有先和 interviewee 聊天降低一些緊張。

• 可改進之處

Interviewee

• 優點

• 有先透過例子確認問題。
• 有先確認邊緣條件。
• 有先說明自己會如何實作，口頭 go through 一遍。
• 說明蠻清晰的，聽的人很容易就知道在說什麼。
• 有做到 REACTO

• 可改進之處

第二次作業 - 他評05

for interviewer

• 優點
  • 很有活力，感覺很有親和力
  • 和interviewee有良好的互動
• 可改進的地方
  • 應避免過多的眼神飄移
  • 0:18 的「對吧」感覺像要問interviewee問題，接著說明時卻沒有停頓；建議若沒有要提問可以把「對吧」省略，或至少要等interviewee有反應
  • 0:14 feel free to "interrupt" me要留意發音

for interviewee

• 優點
  • Examples的步驟有舉出充足且合理的例子，有表現出自己對於題目的理解
• 可改進的地方
  • 應避免過多的眼神飄移
  • 在說明自己的想法時，可以善用文件，將想法已畫面的方式呈現，會比單純口語表達更容易讓人理解

others

• 2:44 開始coding時，錄影的畫面沒有截到coding的部分
• 名字露出來ㄌ