# 資訊科技產業專案設計(HW2)

## **作業(二)**
##### ***Author : 瞧滷肉GIOGIO***

## ***2. Add Two Number***

* **Description** : 給定兩個linked list 陣列中如果出現順序為 1 -> 2 -> 3 代表為321，將兩個陣列加起來後return 新陣列的linked list，舉例 1 -> 2 -> 3 加上 2 -> 4 -> 6 -> 4 輸出 3 -> 6 -> 9 -> 4 因為 321 + 4642 = 4963
* **Solution**
- 利用兩個指針分別指向 linked list
1. 進位數
2. 然後用雙指針各自往下
3. 把值加起來個位數當成 $node.value$ 而進位數就一定是十位數
4. 每次都創造一個 $node$ 存下 $node.value$
5. 如果其中一個 $node$ 到 $null$ 就停止，把$res$指向另外個答案
6. 判斷進位數跟後面答案就直接用加法持續修正
7. return答案
- 兩個Linked List 長度分別 $n$ ,$m$
* **Complexity Analysis**
- 時間複雜度為$O(max(n,m))$
- 空間複雜度為$O(max(n+m)$

    # 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]:

            add = 0 
            head = ptr = ListNode()

            while l1 and l2 :
                currentNode = ListNode()
                currentTatol = l1.val + l2.val + add 
                currentValue , add = currentTatol%10 , currentTatol//10
                currentNode.val = currentValue

                ptr.next = currentNode
                ptr = ptr.next
                l1 = l1.next
                l2 = l2.next

            while l1 :
                currentNode = ListNode()
                currentTatol = l1.val + add 
                currentValue , add = currentTatol%10 , currentTatol//10
                currentNode.val = currentValue

                ptr.next = currentNode
                ptr = ptr.next
                l1 = l1.next

            while l2 :
                currentNode = ListNode()
                currentTatol = l2.val + add 
                currentValue , add = currentTatol%10 , currentTatol//10
                currentNode.val = currentValue

                ptr.next = currentNode
                ptr = ptr.next
                l2 = l2.next
            if add :
                currentNode = ListNode()
                currentTatol = add 
                currentValue = currentTatol%10
                currentNode.val = currentValue
                ptr.next = currentNode

            return head.next

* **Solution(優化)**
- 利用原本的linked list 作為儲存空間對資料修改，故不需要額外空間，空間複雜度可降低到$O(1)$

            # 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]:

            add = 0 
            head = ptr = l1
            prev = ListNode()

            while l1 and l2 :
                currentTotal = l1.val + l2.val + add 
                currentValue , add = currentTotal%10 , currentTotal//10
                l1.val = currentValue 
                prev = l1
                l1 ,l2 = l1.next ,l2.next

            while l1 :
                currentTotal = l1.val + add 
                currentValue , add = currentTotal%10 , currentTotal//10
                l1.val = currentValue
                prev = l1 
                l1 = l1.next

            if l2:
                prev.next = l2 
                while l2 :
                    currentTotal = l2.val + add 
                    currentValue , add = currentTotal%10 , currentTotal//10
                    l2.val = currentValue
                    prev = l2
                    l2 = l2.next

            if add :
                lastNode = ListNode(add)

                prev.next = lastNode

            return head

* **對話草稿**

    🦍: interviewer
    🐵: interviewee

    🦍: 你好，我是今天參與SuperSecurity超安公司的senior SWE Argo，很高興今天你過來進行這場面談，
    那希望你用輕鬆的狀態來面對這場面試，過程中可以盡量展示你的想法，那首先先介紹一下你自己，可以嗎
    🐵: 你好，我叫做Sandow Monky，很高興認識你，很期待今天的面試，請多多指教
    🦍: 好的，那首先思考一下一個場景，台七億公司有一個機密文件，那該公司有兩個部門會access該文件，分別是技術部門跟行銷部門，以下簡稱T跟S
    "T"代表technical，"S"代表Sales，"T"，"S" 部門有不同階級的主管，數量也不一定相同，但要access該文件有一個條件，要從T部門的主管的資料庫中按照順序排出他們的安全碼
    接著"S"同理，然後安全碼從"T","S"各自最低階開始往上進行加法進位，所以真正的password不能夠通過單一主管去知道正確答案。
    1.注意"安全碼的排列並非照階級，而是由加密系統隨機assign下個主管"，所以是個別存在每個主管的profile中，
    而你是一名商業駭客，你已經透過某些方法取得他們資料庫的權限
    2.但問題是就算找出安全碼，實際場域可能會出現超複雜的密碼串，而資料庫的開啟是有時效性的，系統不允許同一個人開啟profile在一天之內超過1分鐘，所以一旦出現這種狀況系統會直接鎖死文件並重新分配安全碼
    3.你今天運氣很好，僱用你的商業對手獲得他們各自的最低階人員密碼跟權限，賺完這一票保證可以讓你躺平買在台北市蛋黃區，但被系統抓到你的雇主肯定不會認帳，你就會進土城躺好躺滿
    🐵: 好的，這裡如果想破解這個問題，是否可以先假設安全碼的範圍再一個區間呢
    🦍: 可以這一題你可以先假設每個人安全碼落在0~9之間
    🐵: 根據剛剛所說這一個我們可以類比成兩道linked list的題目，而最低位數必須由最後一個人得到，然後最後對兩個串列進行加法。
    請問這樣的理解有問題嗎?
    🦍: 沒問題，但這裡要注意打開linked list是有時效性的，看完之後必須馬上關掉
    🐵: 好的，我會注意那我會先利用一個進位數維持進位值，然後做完加法後移動pointer到下一個profile，同時create一個list來記錄該位數，
    因此我會利用以下方法...
    🦍: 好的你可以先實作這個算法並且分析一下時空間複雜度
    🐵: coding...
    🐵: 這個算法的時間是O(n) ，而空間則是O(n)
    🦍: 好，但今天這個系統有進行更新，單純進行存取是不允許在額外空間create一個linked list，這聽起來很合理對吧，畢竟讀取資料又可以新建一整個profile本身就是很奇怪的事情，給你一個提示，每個profile中其實有個備註欄你可以偷偷的使用，系統不會發現因為那是屬於個人的隱私權
    🐵: 了解，所以該做法可能必須要改進到空間O(1)才行，以下是我的算法
    🦍: 恩恩，很好，謝謝你提供的算法，那有關面試結果我們會再這周給你答覆，謝謝
    🐵: 好的謝謝!

* **自我評量**
* 針對interviewer
* 有點提示太明顯，且作圖時就已經幾乎把背後要使用的概念展現出來了
* 針對interviewee
* 講話贅詞太多，盡量減少痾..或這個..，或是使用不確定的用詞(如或許可以)，可以不一定要為了不發生空窗而一直說話，可以提出讓我思考一下來整理思緒。
* 應該主動提出優化程式碼的提議，雖然第一步寫出lengthy code幾乎是不可避免，但過程中也可以對可能需要優化的部分加以註解。以利後續可能會出現的延伸問題

## **他評筆記**

## 月退 - Leg

#### ***1. Two Sum***
* hashmap解在空間複雜度應為O(n)，因為本題interviewee 是先把(nums[i],i)作為(key,value)存入dict，此步驟就已經會占用O(n)
* 更好的解法也是利用hashmap一步一步存，每次先檢查dict是否有存在一個答案，如果有就把答案的value取出直接return，但複雜度其實也是跟interviewee差不多

#### 針對 interviewer 檢討
* 這題interviewee 聽完面試者解答可以透過修改two sum，告訴interviewer說真實狀況有可能出現很多種的配對，所以nums中是有機會出現重複數字，請interview講解應如何列出所有可能的答案，作法其實就是修改字典中value唯一個list 或C++中的array

#### 針對 interviewee 檢討
* 因為說實在第一次遇到這題講出hashmap最佳解其實應該都是之前寫過XD，所以可以假裝不知道最佳解，先用暴力解(雙迴圈)，來讓面試官有討論的空間

#### ***9. Palindrome Number***
* 講解不錯，不論是暴力解或者用字串反向的解講都可以讓完全不知道狀況的人，很容易明白

#### 針對 interviewer 檢討
* 或許可以在問一下複雜度會不會細微差異，因為方法(一)利用迴圈 + 數學計算 方法(二)則是把字串切開反向然後比對，

#### 針對 interviewee 檢討
* 可以簡述一下方法二的空間複雜度運用，會讓interviewee 知道interviewee對python語言的熟悉度

#### ***2. Add Two Numbers***
* 題目解法很直覺，但整體仍有優化空間

#### 針對 interviewer 檢討
* 程式碼的提問很細節，可以讓interviewer明確知道interviewee有follow到
* 可以提示interviewee其實本題第一個一定是個位數，

#### 針對 interviewee 檢討
* 可以再提出**優化**，事實上 linkedlist1 : 5->2->3 linkedlist2 : 6->1->7 ，第一位一定是最小值，作法可以如下
1. 進位數
2. 然後用雙指針各自往下
3. 把值加起來個位數當成 $node.value$ 而進位數就一定是十位數
4. 每次都創造一個 $node$ 存下 $node.value$
5. 如果其中一個 $node$ 到 $null$ 就停止，把$res$指向另外個答案
6. 判斷進位數跟後面答案就直接用加法持續修正
7. return答案
* **上述缺點**
* 比較不直覺且寫法也比較要考慮多一點，時間複雜度也沒有優化太多，但可以偷一點時間，最佳狀況就是根本沒有進位結果後面還有一大串，此時就可以直接指過去當return

## 霍夫曼-Mark Hoffman

#### ***268. Missing Number***
* 針對暴力解的優化展現interviewee對C++語言操作上的靈活性，且在優化解上也利用數學方式減少空間複雜度的運用

#### 針對 interviewer 檢討
* 對interviewee的提示不會太多也很剛好，連續暗示兩次還有更好得記憶體優化解法

#### 針對 interviewee 檢討
* 解法的展現有表現出語言、跟陣列型態操作熟悉度，對題目的理解背後數學意義也能很快跟上

#### ***387. First Unique Character in a String***
* 面試者對題目理解很清楚之外，在影片開頭中展現的示範也有利interviewer去知道面試者的理解進度

#### 針對 interviewer 檢討
* 對interviewee的引導方向跟講解都很清楚明白。

#### 針對 interviewee 檢討
* 暴力解跟優化解都有提出對應的作法，也展現使用C++ stl的理解程度，包括本題因為是存入字母故實際上不可能用$log(n)$，也簡潔的提出說明。

#### ***16. 3-Sum Closest***
* 對暴力解跟優化解都有提出對應作法，且都有給出合理的複雜度解釋

#### 針對 interviewer 檢討
* 當面試者提出$O(n^2)$ 可以適時的提點面試者，因為本來就會預期大概在submit階段過不了

#### 針對 interviewee 檢討
* 暴力解可以利用圖示帶過，因為跑在leetcode上面某些狀況就算是對的也有可能過不了
* 優化解的分析很好，對完全沒寫過的人來說仍然是蠻好理解的

## 火箭-Raccoon
#### ***34. Find First and Last Position of Element in Sorted Array***
* 暴力解跟最佳解都有明確寫出跟講解。尤其是暴力解有稍微在最後聊一下解法

#### 針對 interviewer 檢討
* 可以對二搜法的變體提出一些疑問觀察interviewee的回應。

#### 針對 interviewer 檢討
* 寫完暴力解code後有在針對code說明清楚code中各項數字的意義，對聽者有強化對解法的理解
* 最優解運用2個binary search，找出最左跟最右，但因為binary search是基礎觀念，而本題是運用二搜法並做出細部調整，對於第一次看到寫法的人可能會有發不出差異的狀況，可以像暴力法講解，在結束coding在聊一下細部的操作。

#### ***141. Linked List Cycle***
* 快慢指標跟Hashmap方法的複雜度都有提出解釋，而且還比較各自優缺點

#### 針對 interviewer 檢討
* 可以針對C++ Stl使用時是否對複雜度產生影響進行分析

#### 針對 interviewee 檢討
* 針對題意理解可以用畫圖講解

#### ***70. Climbing Stairs檢討***
* 這是經典的遞迴練習題，可以透過iterative去遍歷得到最佳解，個人覺得答案很好，但解釋上或許可以搭配圖案或是給出範例來強化解題的概念
#### 針對 interviewer 檢討
* 當interviewee講出複雜度時可以去細問為何why?因為此類型的題目太經典，光是用背的其是就可以背出複雜度，如果細問下去就可以去區分面試者對複雜度的理解
#### 針對 interviewee 檢討
* 解釋複雜度可以花一些時間表演出對複雜度分析的概念。

## 肯尼-Ken
#### ***26. Remove Duplicates from Sorted Array***
* 影片非常用心!!!!還有上字幕而且英文講解非常的清楚，但[6:11](https://youtu.be/bIYaaTPyI30?t=371) 剪輯好像有點失誤，都沒有聲音
#### 針對 interviewer 檢討
* 最佳解提示有點太明顯幾乎等於大暴雷
#### 針對 interviewee 檢討
* 程式寫法很簡潔很容易就能理解算法的核心內容.

#### ***94. Binary Tree Inorder Traversal***
* 解釋很清楚，但實作上應該不需要try ... except .. 因為不太可能會有error或無法預期之狀況出現

#### ***152. Maximum Product Subarray***
* 暴力解跟最佳解都有提出合理的作法，解釋也很能理解
#### 針對 interviewer 檢討
* 在批評出暴力解太慢之前，應該請面試者去分析一下複雜度，畢竟第一道解法通常都是最直覺的暴力解，也可以去了解面試者對演算法分析的理解度
#### 針對 interviewee 檢討
* 講解題目可以用一些資料結構術語去說明，比如DP解法，這樣聽者如果是有相關背景知識就會很容易catch上講者的解題思路
* 此題DP解就是maintain **最大(正值)** & **最小值(負值)** 去紀錄可能的最佳解，也可以去說明一下這樣寫法的時間or空間複雜度

## 靈魂程式手-Soul Coder
#### ***2. Add Two Numbers***
* 面試者在解題的想法有考慮到題目設計，而不是單純加起來然後反向然後輸出linked list
#### ***1646. Get Maximum in Generated Array***
* 雖然本題光看題意就直覺想到DP，或許講解DP的概念，也可以說明一下該題的範例中Dynamic Programming
#### 針對 interviewer 檢討
* 雖然是easy的題目但仍然可以詢問為什麼要利用DP的概念，以及如果給定某些情境下，DP作法的優缺點。
* 可以請面試者優化程式碼
#### 針對 interviewee 檢討
* interviewee第一眼就看出用DP解確實蠻合理，因為題目就寫在那，但如果從表演層面或許可以聊一下DP，或是給出一些範例說明。
#### ***20. Valid Parentheses***
* 經典的stack題型，解法上也沒什麼問題
#### 針對 interviewer 檢討
* 因為基礎題型太簡單，或許可以變化一下說是否加入一些計算式子在中間