# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS11ooE4Rh)」作業 1
---
> 貢獻者:
> 太陽🌞:interviewer 章魚🐙:interviewee

> [模擬面試錄影(漢)](https://youtu.be/XlUSK-oPl2I)
> [模擬面試錄影(漢)](https://youtu.be/fO4SjHJ4lJc)
> [模擬面試錄影(英)](https://youtu.be/5Bp0U9V6Ouw)

---
## [118. Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/description/)

### 面試過程
🌞: 你好，從我手上這份簡歷，我感受到您對程式設計的熱情和專業，但在我們談及工作內容前，我想幫公司同仁先認識你在程式開發的想法和風格
🌞: 假設公司現在手邊有個數學導向的專案，它需要大量的計算二項式系數，同仁想知道你的想法，請你稍後討論並在Google Docs撰寫程式碼
🌞: 我現在給你一個數字k ,需要你幫我把前k次方的二次項系數表示出來
🐙: 一開始k是幾次方
🌞: k 為1時表示0次方
🐙: 所以我需要求出從0次方到k次方的二項式系數對吧，如果k 為0 我會輸出 1 如果k為1 我會輸出
 1
1 1
K為2會輸出
 1
 1 1
1 2 1
🌞: 是的沒錯
🐙: 那最直覺的方式是使用公式解，對於第k次方的系數，他的項數依序是是C K取N N是從0開始到K這樣逐個算出來即可得到答案
🌞: 你可以嘗試時做看看
#### ***Methed:*** *Binomial coefficient*

# Time: O(N^(max(i,n-i)+2))
# Space: O(N^2)

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans=[]
        #第幾次方
        for i in range(numRows):
            Row=[]
            #第幾項
            for j in range(i+1):
                #C i 取 0 or C i取i
                if j==0 or j==i:
                    Row.append(1)
                else:
                    tmp=1
                    # i,i-1,...j+1
                    for num in range(i,j,-1):
                        tmp*=num
                    #j !
                    for num in range(j):
                        tmp//=num
                    Row.append(tmp)
            ans.append(Row)
        return ans

🌞: 那這個演算法的時間複雜度為何?
🐙: 由於使用階乘計算所以時間複雜度非常龐大，會到O(N^N))
🌞: 沒錯這個演算法的複雜度非常之大，這並不適合用於計算大量的二次項系數
🌞: 你有聽過巴斯卡三角形嗎?
🐙: 聽過這也是用來計算二次項系數的方法之一
🌞: 那你能不能利用巴斯卡三角形設計出一個演算法來優化其時間複雜度呢?
🐙: 當然可以我們觀察巴斯卡三角形可以得到除了首尾的數字之外，其他的數字皆為上一層的兩個數字相加而來，所以我們不用再去重新計算階乘，只需要兩個數字相加即可達成，這樣讓時間複雜度降至O(N^2)
#### ***Methed:*** *Pascal's Triangle*

# Time: O(N^2)
# Space: O(N^2)

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans=[]
        #第幾次方
        for i in range(numRows):
            Row=[]
            #第幾項
            for j in range(i+1):
                #C i 取 0 or C i取i
                if j==0 or j==i:
                    Row.append(1)
                else:
                    Row.append(ans[i-1][j-1]+ans[i-1][j])
            ans.append(Row)
        return ans

🐙: 這就是我的演算法實做
🌞: 能不能再讓它的複雜度繼續下降呢?
🐙: 因為要印出所有二項式系數，這勢必要從0開始逐個計算二項式系數，因此我認為N^2 就是極限了，但這僅限於第一次計算的時候，我們可以在一邊在計算一邊建表，這樣以後求出數字時只需要查找表格就行了，第一次計算會花O(N^2)的時間，但之後每次計算只需要查表O(1)的時間即可，但這代表需要花費額外空間去紀錄表格，但專案是為了大量計算二項式系數，因此我覺得犧牲一點空間去縮短計算時間式是得的
🌞: 很棒的想法，謝謝你今天來面試，我會與同仁討論過後再電話通知結果

---

## [1679. Max Number of K-Sum Pairs](https://leetcode.com/problems/max-number-of-k-sum-pairs/description/)
### 面試過程
🌞: 你好，從我手上這份簡歷，我感受到您對程式設計的熱情和專業，但在我們談及工作內容前，我想幫公司同仁先認識你在程式開發的想法和風格
🌞: 假設公司現在有若干筆資料需要加密，我們把這些資料拆成兩組數字，我們設定當兩組數字相加為指定數字時才能確定他們是由相同的資料分割而來進而解密他，現在我們隨意選取任意組數字，你有辦法設計一個演算法求出有多少筆資料是可解密的嗎?
🐙: 每個拆分後的資料只能使用一次對吧?
🌞: 是的拆分後的資料只能使用一次，並且我們能確保每筆資料都只有一組解
🐙: 依我的理解，我可以把他視為若干筆數字需要計算出相加為特定數字的對數對吧?
🌞: 你可以這麼認為
🐙: 那我一開始用相同大小的list來儲存是否有使用過該數字以及用ans來表示數組個數，接著用for loop 掃過每個數字，只要他是沒被使用過的，就可以在從list中找出還沒被使用過且數字剛好為k-該數字的數，接著標記為只用過，這樣就算一組以此類推
#### ***Method:*** *maxOperations(Brute Force)*

# Time: O(N^2)
# Space: O(N)

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        ans=0
        visit=[False]*len(nums)
        for i in range(len(nums)):
            if  not visit[i]:
                visit[i]=True
                target=k-nums[i]
                for j in range(i+1,len(nums)):
                    if visit[j]==False and nums[j]==target:
                        ans+=1
                        visit[j]=True
                        break
        return ans

🌞: 那這個演算法的時間複雜度是什麼?
🐙: 這演算法的時間複雜度是O(N^2)
🌞: O(N^2)在求解這問題來說不是最好的量級，你有辦法優化這個演算法嗎?
🐙: 我們可以在內層for loop中使用binary search這樣時間複雜度會變成O(N log N)
🌞: 這想法不錯，但有沒有什麼方法可以讓他時間複雜度降至linear time 呢
🐙: 有的，我們可以使用dictionary來記錄每個數字，這樣內部for loop查找起來只需要花費O(1)的時間，這樣子只需要跑外部一層for loop即可，這樣時間複雜度會變成O(N)即linear time
🌞: 那你的dictionary該怎麼判斷呢?
🐙: 我會使用defaultdict來當作我的dictionary，因為我會用其中的value值0 or 1來表示是否未配對到，所以defaultdict可以直接對value值做加減符合我的需求，一開始全部都是為已配對狀態，在for loop執行當中我們遇到新的數字只需要檢查前面是否有還未配對且符合條件的資料，如果有則將該資料的value值改為以配對，反之則改為未被配對狀態，接著只要一邊記錄一邊查找即可
🌞: 利用dictionary達成linear time，不錯的想法，那今天的面試就到這裡結束，有問題歡迎聯絡我們，那我會跟同仁討論之後再告知結果，謝謝你的參與

#### ***Method:*** *maxOperations(using Dictionary)*

# Time: O(N)
# Space: O(N)
class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        ans,lists=0,defaultdict(int)
        for i in nums:
            target =k-i
            if lists[target]>0:
                lists[target]-=1
                ans+=1
            else:
                lists[i]+=1
        return ans

---
## [643. Maximum Average Subarray I](https://leetcode.com/problems/maximum-average-subarray-i/description/)
### 面試過程
🌞: Hello I'm Yog,thank you for being here,before talking about job description,we would like to offer several questions to get acquainted with each other
🐙: OK! I'm Azathoth ,nice to meet you
🌞: Suppose our company has a sensor that can detect whether humans are in the frame, and if so, the return value tends to be close to 1. Occasionally, some animals like dogs and cats may also enter the sensor's range, but usually, the return value won't be higher than that for humans.Now,we provide you with a time series of sensor readings. Could you design an algorithm to identify the most likely time segments when humans were detected?
🌞: yes
🐙: what is time part range from
🌞: about 1 seconds
🐙: OK I simplify the problem to computing the average value because it maens there must be a human walking through the sensor's range during the time while the average return value is high,so we can take return value during the time as a list and use a 1s mask to compute every time segment'saverage possibility,the maximum average value represent that it must be a human there
🐙: We can extend the problem beyond just one second,for example, k frames,so I use for loop to gone through the whole time series list ,and we just iterate len(nums)-k+1 times because we choose k frames separately, and each step compute the k frame subarray’s average and use a variable Max to store Maximum average number and return Max

#### ***Method:*** *maxOperations(Brute Force)*

# Time: O(N*K)
# Space: O(1)
class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        Max=-10000
        for i in range(len(nums)-k+1):
            avg=0
            for j in range(k):
                avg+=nums[i+j]
            avg=avg/k
            Max=max(Max,avg)
        return Max

what is the time complexity of this algo
it’s O(N*K)
🌞: it seems that as k increases, the time complexity approaches O(N^2)
🌞: do you have a better solution which time complexity is not effect on k?
🐙: do you heard about sliding window ?
🌞: yes but can you explain how sliding window implement on this issue?
🐙: we can see that in each for loop step ,the new one is just delete the first element from the last one and add a new element at the end,the others overlap,we can use sliding window technique to avoid redundant computation, we add a variable Sum that store the last subarrays sum ,when the new one need to compute ,just delete the first element from Sum and add a new element to Sum,we can simply get the new one’s Sum

#### ***Method:*** *maxOperations(using Dictionary)*

# Time: O(N)
# Space: O(1)
class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        Sum=sum(nums[:k])
        Max=Sum/k
        for i in range(len(nums)-k):
            Sum=Sum-nums[i]+nums[i+k]
            Max=max(Max,Sum/k)
        return Max

🐙: here is my code with sliding window technique,i wish it's helpful to improve the efficency
🌞: Excellent! please keep in touch and see you next time!

## 總體初步檢討
***交談過程***

* 語助詞太多(例如哦...)
* 講話會口吃
* 整體節奏偏慢
* 本來想要用語氣區分出Interviewee and Interviewer結果精神錯亂搞混只好上貼圖
* 面試官一直想要壓時間複雜度，有種咄咄逼人的感覺?
* 雖然有例舉但還是有點牽強
* Coding完之後面試官除了問時間複雜度跟能不能再變快之外就不會問其他問題了
* REACTO 的Test部分只run過程式流程而已沒有細講
* 同上因為沒問清楚所有input的數字範圍，現在是面對有寫過的題目，但以後面對沒寫過的題目時可能會少考慮一些邊界條件
* 菜英文，口說也菜，菜到連自己也聽了很痛苦，需要多加努力練習
* 工具列有時會露出來

***程式過程***

* 有些註解好像沒必要
* 變數命名還需要加強
* 程式打的還是太慢了
* 有時候非最佳解的方法反而是不直覺的