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

貢獻者：塔塔 Jennifer
模擬面試錄影: 漢
模擬面試錄影: 漢
模擬面試錄影: 英

interviewer, interviewee 身份切換，以time code標註於影片上

392. Is Subsequence

Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

interviewee: 假設我們現在有個project是要做觀光景點路線推薦，我們設計了一條路線上面有幾個著名景點，以及我們搜集到了觀光客們去各景點的打卡時間紀錄。如何判斷我們這個路線的景點是不是普遍大眾喜歡且順暢的路線？
interviewer: 根據問題描述，我認為這個問題可以簡化成把觀光路線變成string, 裡面的每個char視為景點。如果我們設計的路線(string s)為大中普遍會去的觀光路線(string t) 且順序一致，這個路線規劃就是合理的。所以可以將這個問題想成判斷是不是子序列的問題。
interviewee: 我了解了。 那請你邊撰寫邊解說你的處理過程。

程式碼解說

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:

          if not s:
            return True

          len_s = len(s)
          i=0
          for char in t:
            if char == s[i]:
              i+=1
            if i== len_s:
              return True
          return False

interviewer:這個方法的TC為O(n)，我認為是最快的方法了。另一個方法為使用pointer 分別去指向兩個string，但這個方法不會比較快。

---

21. Merge two Sorted List

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

interviewee: 下一個問題。假設我們公司有消費者這個月的消費記錄，每個人的消費金額已經從低排到高做好排序。若我們想得知所有顧客中最低的消費金額與最高的為多少，應該要怎麼處理這個問題？
interviewer: 這個問題可以想成把排序好的list合併。需要注意的是list可能為空的情況，以及當其中一個list已經接到最後一位數時，即可直接將另一個list剩餘的值直接在merge list後方（因為list本身已經經過排序）

程式碼解說

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

        ans= temp = ListNode()
        while list1 and list2:
          if list1.val < list2.val:
              temp.next = list1
              temp = temp.next
              list1 = list1.next
          else:
              temp.next = list2
              temp = temp.next
              list2 = list2.next
        if list1:
              temp.next = list1
        if list2:
             temp.next = list2
        return ans.next

215. Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

interviewee: Hi, I am the interviewee in this test session. If you don't have any questions, let's move on to the first question.

interviewer: ok.

interviewee: During data cleaning, sometimes we need to calculate the top few largest numbers within a dataset. So, This time, I would like you to use a matrix that only stores inumbers to calculate the kth largest number.

interviewer: Excuse me, I'd like to confirm that if there are multiple identical values, for example, I have five numbers present integer 3 ,do they represent different ranks?

interviewee: Yes, they are seen as different ranks.

interviewer: Okay, I got it. The first method that comes to my mind is to sort all the data using quick sort and then find the value at the specified position. For example, if a matrix has 9 numbers, and we want to find the 7th largest value, I would sort all the values from smallest to largest and then find the second smallest number.

interviewee: So, is there any way to get the solution without sorting the data?

interviewer: Umm, I’ve encountered this problem before, and my idea is to use a min-heap to solve it. This way, the time complexity would be smaller than quick sort.

interviewee: I got it. Please go ahead and organize your code.

程式碼解說

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        
        min_heap=[]
        for num in nums:
            if len(min_heap)<k:
                    heapq.heappush(min_heap,num)
            else:
                    heapq.heappushpop(min_heap,num)
        return min_heap[0]

整體初步檢討

• 要訓練邊打字邊講話… 打字的時候應該要邊講解題目
• 目前僅能夠針對演算法提出其他種解法，無法預判面試官可能會在哪個地方提出考點 或如何更深入探討問題（可能要多觀摩其他人的面試影片）
• 多練習英文面試以及增進口語表達，因為緊張跑出很多無意義的語助詞
• 整題結束的時候不知道該怎麼結束
• 嘗試改用c++練習leetcode

---

第二次作業-他評01

interviewer

• 優點

• 將題目包裝的很好，讓interviewee需要更動腦來找答案
• 3:02正確地引導interviewee想出時間複雜度較低的解法

• 可改進的地方

• 應該有目的的問其他解法，會讓問題更有挑戰性
• 10:08: 直接要求interviewee 分享「其他解法」似乎有些突兀且意義不明，若能改成加入某些限制使interviewee一開始的解法無法使用，再提出有無「其他解法」會更優。

interviewee

• 優點

• REACTO的部分都有cover到
• 13:27: example的部分利用顏色分類的十分清楚

• 可改進的地方

• 英文口說的部分比較不連貫，若能順暢的表達會很加分
• value 跟 calculate在ue和ul的發音應該比較像是you而非lu
• 12:23
  • 缺少了Test的部分，沒有去說服為什麼這麼寫會正確
  • 缺少了Optimize的部分

第二次作業-他評02

interviewer

• 優點

• 語速適中
• team的project內容帶入題目，能讓interviewee提早熟悉工作內容

• 可改進的地方

• 1:16: 建議可以換衣服來表示更換角色為interviewee了
• 10:08: 「有沒有其他解法解這個問題?」可以換個方式問，問說有沒有覺得這個解法哪裡可以換做其他解法去嘗試看看。
• 第三題英文的文字版本，interviewer與interviewee的對話內容有打顛倒，因為影片中沒有標示誰是interviewee與interviewer有點難懂誰說了甚麼。

interviewee

• 優點

• 10:54: 有解釋complexity為什麼是這樣，表示自己的依據。
• 2:11: 講話會搭配手勢。
• 2:20: 把要做的事情說出來，以免自己忘記，也讓interviewer能知道之後你要做甚麼
• 5:30: 用寫程式的人的術語解釋自己要做甚麼"dummy node"，比起用一堆普通的話去描述這個意義還更有用。
• 寫程式的時候講解得很清楚，可以讓interviewer知道interviewee在做甚麼
• 12:32: 有沒有結束講完的感覺。

• 可改進的地方

• 1:25: 前段講Approach的部分說話會卡頓，會在不應停頓的地方停頓，讓interviewer無法快速自然地理解interviewee的說話內容，建議可以先想完一整句話再講，不用急著回答而邊講邊想。
• 6:00: 可以把變數命名的比較有意義，interviewer有可能會忘記，也確保interviewee自己有記得。也可以加註解在後面。
• 9:40: 可以再對"比較快的解法"的說詞再多做說明。
• 10:18: 說明時可以用文件輔助說明，描述pointer分別對string去計算目前跑到哪個位置用圖能夠讓interviewer快速理解。
• 6:29: 這裡用list，前面就不要用matrix 1:06: 統一說法會讓interviewer的理解比較前後連貫，8:03的時候又換成array。如果一開始interviewer用的是matrix可以盡量跟interviewer一致。這也表示interviewee有聽懂interviewer的題目順序，並且理解正確。
• 7:01: "I will put an integer because all the data in the array is numbers" 應該改成 "I will put an integer because all the data in the array is integer"會比較好，因為number不一定要用integer。

第二次作業-他評03

• 整體優點： 口齒很清晰 讚
• 可改進的地方：影片編輯可以標注一下interviewer跟interviewee（雖然在實際面試中不會用到，但HW會有差）

interviewer

• 優點

• 有先包裝過題目

• 可改進的地方：

• 可以多引導interviewee一點內容，再讓對方打程式，對話可以試探interviewee的想法跟能力。

interviewee

• 可改進的地方：

• 對於包裝過的題目反應成code前好像太快了點，可以先多問幾個問題再總結目前的想法，讓雙方討論。
• 在coding前可以先說明程式碼架構要如何實現，這樣對方比較好懂。
• 缺少testing，可以的話優化的coding也可以再放上去。

第二次作業-他評04

關於 interviewer

• 優點

• 有包裝題目

• 可改進的地方

• 可以多給一些提示

關於 interviewee

• 優點

• 邊cοding邊解釋使會議不會有太多空白

• 可改進的地方

• 應該在A的時候就可以提出時間複雜度是多少
• E的部份沒有確實執行
• 應標示interviewer和interviewee

第二次作業-他評05

關於 interviewer

• 優點

• 0:20: 題目有巧思

• 可改進的地方

• 0:33: 題目描述有點冗長和過多贅詞，面試者口頭聽完很難馬上抓到重點
• 3:55: 可以給予面試者一些肯定或討論，再讓他編碼。

關於 interviewee

• 優點

• 語速恰當，口齒清晰。

• 可改進的地方

• 3:55: 可以稍微說明自己將使用何種程式語言。
• 9:29: 說出"比較快的解法"，但不知道是跟甚麼比較。
• 10:11: 分不出是interviewer還是interviewee在說話。

它評-06

Interviewee

• 優點

• 0:26有先介紹自己的研究不錯
• 2:57 有分析時間
• 5:14 有解釋下coding 過程了
• 7:35 coding 前有解釋了
• 12:18 有解釋了，很好
• 15:19 coding 到一半有解釋全局，可以讓面試官更能掌握情況

• 缺點

• 0:15 左下角有寫是面試者或著面試官，但有點小，可以更明顯一點讓人好看出
• 1:18 我覺得可以把repeat 跟example這步驟做的更確實，很突然跳到coding 解釋也有點短，沒有解釋溝通，要更多範例
• 2:23 coding過程有點小尷尬，可以編寫邊解釋下這行的作用
• 3:14 可以簡略下解釋此作法與前者不同，例如：前者會有重複計算問題… 所以令一個思路是… 來清晰解釋下
• 5:14 可以coding 多一點註解 # 這行目的… 比較可以清晰表達想法，不然光聽說話有點難
• 7:35 可以在螢幕上打字解釋下，不然直接跳到打好的解釋，很奇怪不自然，用google圖片搜尋然後抓一個解釋比較順
• 12:18 沒做 test 跟 Optimize
• 14:19 不太確定父的解釋圖示幹麻用的，需要在coding 前可以邊解釋邊劃下示意圖
  Interviewer

• 優點

• 3:14 只是清晰
• 12:50 題目清晰

• 缺點

• 0:44 直接跳到費氏數列介紹感覺有點跳動，沒啥題目介紹也沒變形，還是面試官跟受侍者沒分清楚，我重複聽好多次才有點分清楚誰是誰
• 7:18 應該是面試官出題目吧，面試者自己出題有點怪