# 資訊科技產業專案設計: Homework1

###### 貢獻者: `外興仁`

## 撰寫語言: python

[Problem 1 : two sum](https://leetcode.com/problems/two-sum/)

**interviewer:** 給予一個整數陣列以及一個目標的整數，在陣列中尋找兩個數相加為目標整數，並輸出兩數分別的index。

**ME:** 我的想法是寫兩個for loop，第一層包在外面，每一次執行時再跑一個for loop，去尋找與現在的值相加為目標的值，最後返回兩個index。

**interviewer:** 那請問這個做法的時間複雜度是多少呢?

**ME:** 由於跑兩次迴圈，假設陣列長度為n，跑兩次迴圈就是n*n，那時間複雜度就是
$$O(n^2)$$

**interviewer:** 要特別注意不能找到兩個相同值。

**ME:** 好的，就在每次迴圈加個限制條件就沒問題了。

for i in range( len(nums) ):
            
            for j in range( len(nums) ):
                
                if (i != j):
                    
                    x= nums[i] + nums[j]
                    if ( x == target):
                    
                        return [i,j]

**interviewer:** 那除了兩次迴圈的方法之外，有複雜度更低的方法嗎?

**ME:** 我的想法是建立一個hash table，將看過的數字記錄下來，若下次有數字與之相加為目標數值，就可以得出解答!!

seen = {}
for i in range( len(nums) ):
            
            remaining = target - nums[i]
            
            if (remaining in seen ):
                return [seen[remaining] , i]
            else:
                seen[nums[i]] = i

**ME:** 以測資nums[i]為2為例子，假設目標為target = 10，所以loop裡面的remaining就是10 - 2 = 8，若是hash table內沒有8，就把 i 存進去seen，這樣下次遇到8時，就知道是2與之相加為target了。

$complexity:O(n)$

---

[Problem 2: Reverse Integer](https://leetcode.com/problems/reverse-integer/)

**interviewer:** 在第二題中，我會給一個有號32bit的數字，請輸出反轉後的數字。

**ME:** 我的想法是把input x用％ 10 提出最小位元的數字，並*10加到output中，最後輸出output。

output = output *10 + int (x % 10)
            x /= 10

**ME:** 將正負號另外處理，symbol紀錄正負號。

if (x < 0):
            
            symbol = -1
            x = -x
        
        else:
            
            symbol = 1

**interviewer:** 注意要檢查最後輸出的值，不能超過2的31次方。

**ME:** 若是overflow，則輸出0。

return 0 if output > pow(2,31) else (output*symbol)

        output = 0
        
        if (x < 0):
            
            symbol = -1
            x = -x
        
        else:
            
            symbol = 1
            
        while ( x >=1 ):
            
            output = output *10 + int (x % 10)
            x /= 10
            
            
        return 0 if output > pow(2,31) else (output*symbol)
        

---

### Problem 3 : Add Two Numbers

**interviewer:** 給兩個非空的非負整數linked list，節點從頭開始代表數字的個位數，並依此類推，請相加兩list，並輸出答案。

**ME:** 從個位數開始相加，如果加完大於9就進位(自己 carry / 10 ，下一位 carry %10)，一直做直到兩個數都加完且不用進位了。

**ME:** Create一個空節點，給於val為0，並用兩個pointer: head & cur。

head: 指向第一個Node。
cur: 現在的Node。
carry: 進位數值。

head = cur = ListNode(0)
carry = 0

**ME:** loop執行條件： 兩數加完or進位也加完。

while l1 or l2 or carry:

**ME:** 兩linker list各節點相加

if l1:
        carry += l1.val
        l1 = l1.next
if l2:
        carry += l2.val
        l2 = l2.next

**ME:** 將相加的值給予節點，並進到下一個Node，並對carry做處理。

cur.next = ListNode(carry%10)
cur = cur.next
carry //= 10

dummy = cur = ListNode(0)
        carry = 0
        while l1 or l2 or carry:
            if l1:
                carry += l1.val
                l1 = l1.next
            if l2:
                carry += l2.val
                l2 = l2.next
            cur.next = ListNode(carry%10)
            cur = cur.next
            carry //= 10
        return head.next
        

---

### 檢討

* interviewer 問太少，沒從interviewer 的角度出發去詢問問題，只單純拋出問題本身，沒有真正達到interview。
* interviewee 沒有第二個鏡頭，只有螢幕畫面，在回答題目時也沒有清楚表達。
* 拍得好爛，第一次這樣自拍自答，有點尷尬...