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

貢獻者: 牙塑-Wind
🧔：interviewer
👶：interviewee

121. Best Time to Buy and Sell Stock

影片: 00:01

測驗說明與問答

🧔：我這裡有一些近幾日的股價資料，每一份資料會是一段連續時間的股價變化，每天的股價都不太相同，我想請你幫我在這段連續時間內找出一組最大獲利
👶：好的，我想請問，一組最大獲利指的是在連續時間內哪一天買哪一天賣可以使得利益最大嗎，這些天數與股價的範圍有沒有什麼限制呢。
🧔：沒錯，請你找到在這段時間中，哪天買入哪天賣出可以獲得最大利益，請注意，必須先買股票才能賣出。天數範圍界在1 ~ 100000之間，股價界在 0 ~ 10000。
👶：那我會用python去實作想先請問一下，我是否能假設function的輸入為一個list
🧔：你可以假設輸入是一個list
👶：我想到的方法是，假設list名稱為prices，因為賣出股票前一定要先買股票，所以我可以設定兩個指標left與right分別設置在index0與index1的位置，left代表買入，right代表賣出，再來使用一個while迴圈遍歷list，每次迭帶去計算獲利，也就是prices[right]-prices[left]，如果獲利為負數，表示賣出的數值比買入還要小，我們會希望買入的值可以盡量小，因此這時候可以把left指標移動到right的位置，right的指標加一，如果獲利為正，則去比較當前獲利與過去獲利的大小，並保留較大的獲利值，right指標加一去查看下一個數值。如此重複計算，迭帶到right指標遍歷完整個list，就可以終止迴圈並獲得最大獲利。
👶：這樣的作法時間複雜度為O(n)，空間複雜度為O(1)，以上為我的演算法。
🧔：OK，那請你用google document來實作這個題目。

def maxProfit(prices):
    left = 0 #buy
    right = 1 #sell
    max_profit = 0
    while right < len(prices):
        profit = prices[right] - prices[left] #current profit
        if profit > 0:
            max_profit = max(profit,max_profit)
        else:
            left = right
        right += 1
    return max_profit

👶：以上為我的演算法實作後的code，請問有什麼問題嗎?
🧔：你覺得這個題目存在時間複雜度更低的解法嗎？
👶：因為這是一個沒有排序的list，我想勢必要遍歷一次來確認所以值，才能找到最大獲利，因此我覺得最低的複雜度應該就是O(n)。
🧔：那你覺得你的程式碼還有什麼可以優化的地方嗎?
👶：我發現在每次while迴圈中，right都會加一，所以其實可以將迴圈改成使用for，這樣的好處在於，for的執行次數比較明確，再來是python code的效率是比較慢的，如果使用while迴圈，需要多right < len(prices)的邊界確認與right+=1這兩個步驟，使得while迴圈速度較慢。
🧔：你提到的邊界確認與變數加一的操作，for迴圈也需要進行不是嗎?
👶：是的，不過python底層是由C來實作，在for迴圈中，邊界確認與變數加一這兩個操作是底層的C做好的，所以會比使用while需要自己多兩這兩步驟的python code還要快。
🧔：了解，那請你把程式改成for迴圈的版本。

def maxProfit(prices):
    left = 0 #buy
    max_profit = 0
    for right in range(1, len(prices)): #sell
        profit = prices[right] - prices[left] #current profit
        if profit > 0:
            max_profit = max(profit,max_profit)
        else:
            left = right
    return max_profit

🧔：你是否能夠證明兩者的速度差異呢？

import timeit
import random
from functools import partial

def maxProfit_for(prices):
    left = 0 #buy
    max_profit = 0
    for right in range(1, len(prices)): #sell
        profit = prices[right] - prices[left] #current profit
        if profit > 0:
            max_profit = max(profit,max_profit)
        else:
            left = right
    return max_profit

def maxProfit_while(prices):
    left = 0 #buy
    right = 1 #sell
    max_profit = 0
    while right < len(prices):
        profit = prices[right] - prices[left] #current profit
        if profit > 0:
            max_profit = max(profit,max_profit)
        else:
            left = right
        right += 1
    return max_profit

def main():
    prices_list = [random.randint(1, 10000) for _ in range(100000)]
    partial_function_for = partial(maxProfit_for, prices_list)
    print('for loop\t\t', timeit.timeit(partial_function_for, number=1))
    partial_function_while = partial(maxProfit_while, prices_list)
    print('while loop\t\t', timeit.timeit(partial_function_while, number=1))

122. Best Time to Buy and Sell Stock II

影片: 12:25

測驗說明與問答

🧔：承接上一題，我們稍微改變一下題目，我一樣會給你一段連續時間的股價，這次要尋找的是整體的最大獲利，也就是在這段時間，我可以重複進行買跟賣，我們限制同一天只可以持有一張股票，不過可以在當天同時買跟賣。
👶：跟上一題一樣，我會拿到一個代表價格的陣列，但是不同於上一題只做一次買賣，這次不限買賣次數，但限制同一天只能持有一張股票，然後去尋找最大利益這樣嗎？
🧔：是的，沒錯。
👶：那請問天數與價格的範圍也都跟上一題一樣嗎？
🧔：是的，天數範圍界在1 ~ 100000之間，股價界在 0 ~ 10000。
👶：這題應該是要使用DP的想法來解，當前的最大獲利會根據於前一天的最大獲利計算得出，每一天我會有兩個狀態，持有股票跟沒持有股票，持有股票的狀態包括我原本就有持有股票沒賣出跟我把股票賣出今日買股票兩種，只要對這兩種情況取max計算最大收益，就可以計算今日持有股票可以獲得的最大收益。沒持有股票狀態包括，我原本就沒有持有股票跟我原本有持有但是今日賣掉了，同樣對這兩種情況取max，就可以獲得今日沒持有股票所得的最大收益。而最大利潤的情況會發生在最後一天沒有股票的狀態，因為把目前手中持有的股票賣掉才能獲得最大收益。
🧔：分析挺有道理的，那一樣請你用google document來實作這個題目。

def maxProfit(prices: List[int]) -> int:
        
        cur_hold, cur_not_hold = -int('inf'), 0
        
        for stock_price in prices:
            
            prev_hold, prev_not_hold = cur_hold, cur_not_hold
            
			# either keep hold, or buy in stock today at stock price
            cur_hold = max( prev_hold, prev_not_hold - stock_price )
			
			# either keep not-hold, or sell out stock today at stock price
            cur_not_hold = max( prev_not_hold, prev_hold + stock_price )
            
        # maximum profit must be in not-hold state
        return cur_not_hold

👶：這樣的演算法，時間複雜度為O(n)，空間複雜度為O(1)。
🧔：這題有更直觀更簡單的理解方式，時間複雜度同樣為O(n)，空間複雜度為O(1)，你可以想想你平常買賣股票的策略。
👶：我會希望在股價低的時候買入，價格上升的時候賣出。
🧔：而你現在已經可以知道在一段時間內股價的變化。
👶：我了解了，若把股價畫成折線圖，斜率正的區間為正收益的部分，只要將所有斜率為正的區間相加，即是最大收益。

def maxProfit(prices: List[int]) -> int:
      if not prices:
            return 0
      profit_sum = 0
      for i in range(1,len(prices)):
        profit = prices[i] - prices[i-1]
        if profit > 0:
          profit_sum += profit
      return profit_sum

👶：這樣演算法的時間複雜度與空間複雜度都跟使用DP作的方式相同，但是更為直觀，使用的變數也比較少。

380. Insert Delete GetRandom O(1)

影片: 20:28

測驗說明與問答

🧔：Please implement a class called RandomizedSet that includes three operations: insert, remove, and getRandom. The insert operation inserts an item with the value into the set if it is not already present. It returns true if the item was not previously present, and false otherwise. The remove operation removes an item with the value from the set if it is present. It returns true if the item was previously present, and false otherwise. The getRandom operation returns a random element from the current set of elements. It is guaranteed that at least one element exists when this method is called, and each element in the set has an equal probability of being returned. You must implement the functions of the class such that each function works in average O(1) time complexity.
👶：So I need to define a class called RandomizedSet and implement three operations: insert, remove, and getRandom, all with a time complexity of O(1), while ensuring that these operations return the correct values. So, should I expect the input to be a series of operations?
🧔：That's correct. The input will be passed as a series of operations, and your class should correctly return boolean values or numbers as required. It's important to ensure that all your operations are completed in O(1) time complexity.
👶：To achieve O(1) time complexity for both insert and remove, I can utilize a hashmap data structure. I propose using a set as the data storage container, which would provide constant time complexity for both searching and the insert and remove operations. As for getRandom, I can use the random function to achieve the desired functionality.
🧔：Okay, please implement your class in a Google Document.

class RandomizedSet:

    def __init__(self):
        # Initialize Set
        self.data = set()

    def insert(self, val: int) -> bool:
        # If n is present in set then return false
        if val in self.data : 
            return False
        
        # If n is not present in set then add it to the set.
        self.data.add(val)
        return True

    def remove(self, val: int) -> bool:
        # If n is in set then remove n else return false
        if val in self.data:
            self.data.remove(val)
            return True
        return False

    def getRandom(self) -> int:
        # Return random number using random module
        return random.choice(list(self.data))

👶：This is the class I've implemented, and all three operations have O(1) time complexity.
🧔：Your insert and remove operations do indeed achieve O(1) complexity, but your random operation does not.
👶：Random.choice indeed has O(1) complexity, so converting a set to a list does not have O(1) complexity. So, I would need to maintain a list, but the issue is that when I perform a remove operation on the list, it still has O(n) complexity. I might need to use a dictionary to store the values and their corresponding indices in the list. Then, when I need to remove a value, I can swap it with the last element in the list and use pop to remove the last element. This way, the remove operation would also achieve O(1) complexity.
🧔：Great! Please go ahead and showcase your implementation.

class RandomizedSet:

    def __init__(self):
        # Store the index of each val in self.arr.
        self.indices = {}
        # Store all vals.
        self.arr = []

    def insert(self, val: int) -> bool:
        # Return False if val is already present as requested.
        if val in self.indices: return False
        
        # Append val to the array.
        # Store its index in the hashmap
        self.arr.append(val)
        self.indices[val] = len(self.arr)-1
        return True
    
    def remove(self, val: int) -> bool:
        # Return False if val is not present as requested.
        if val not in self.indices: return False
        
        # Get the index of the val that needs to be removed.
        i = self.indices[val]
        
        # Update the index of arr[-1] in the indices.
        self.indices[self.arr[-1]] = i
        
        # Move the last element to the i th position.
        self.arr[i] = self.arr[-1]
        
        # remove the last element, and remove the index of val
        self.indices.pop(val)
        self.arr.pop()
        
        return True

    def getRandom(self) -> int:
        return random.choice(self.arr)

👶：Using a combination of a list and a dictionary, it is possible to achieve O(1) time complexity for all three operations.

檢討

優點

• 對話完整，語速自然
• 打程式時有適時加入解說
• 對程式分析清楚，包括程式碼底層的小知識，很有趣

可以改進的地方

• 部分題目缺少Test case，應該善用Test case解釋想法
• 部分題目註解不完全，可以用註解的方式去寫Test case，以及用註解去區分程式的部分，讓面試官更明白程式流程
• 講話偶爾會有口吃的情況，應先仔細思考後再進行回答
• 打字速度偏慢且常常打錯字，應花時間練習打字
• 邊寫程式邊講話還是會有點卡卡的

他評01

優點

• 程式碼有註解
• 說明解題邏輯後再開始實作
• 邏輯清晰有條理
• 邊撰寫程式碼邊解說
• 說明底層邏輯

可以改進的地方

• 第二題當interviewee提出使用DP時，interviewer可以提出質疑，讓interviewee思考並說出理由

他評02

優點

• interviewee 邊 coding 邊講解，還附上註解，而且全部都蠻順的，很厲害！
• interviewee 將想法表達得很詳細

可以改進的地方

• 8:34 interviewer 有希望 interviewee 證明兩者的速度差異，可以的話，感覺 interviewer 要讓 main() 執行一次看看才能真正證明。
• 13:21 interviewee 一次假設的情況有點多，建議可以打下來，讓人更容易理解。舉例:
  • 持有股票
    • 原本就有持有股票沒賣出
    • 已把股票賣出，今日買股票
  • 沒持有股票
    • 原本就沒有持有股票
    • 我原本有持有但是今日賣掉了
• 英文部分太像念稿，可以增加一些語氣起伏和停頓

他評03

interviewer

• 優點
• 絲滑的切入讓interviewee coding的開頭
• 有對題目題目變形
• 可改進之地方
• 如果interviewee沒有做測試的動作可以嘗試讓其進行測試

interviewee

• 優點
• 有跟interviewer確認資料沒說明的資訊
• 可改進之地方
• 講解的時候可以帶上圖或打出來，只用嘴巴在念interviewer需要很專心才可以接收到資訊
• REACTO 中的example、testing 感覺沒完成

可以假裝在寫unit test把自己寫的function當做pure function來測試， fn (input).expect(output)

他評04

優點

解釋解題思路清楚明確，且在撰寫程式碼時會同時解釋該段程式碼作用。
雖然使用python撰寫程式，但interviewee有同時說明底層實作的原理。

可以改進的地方

缺乏了舉例說明與程式碼可行性驗證的階段，interviewee一開始說明解題邏輯時沒有搭配畫面內容，稍顯可惜。

他評05

interviewer

• 優點
• 對Leetcode 題目做變形，很讚
• 語速穩定

interviewee

• 優點
• 一邊打程式一邊講解，聲音大小及口齒依然使人可以聽得清楚
• 可改進之地方
• REACTO不太完整