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

嚐味鹽-Yuanson
video: 模擬面試影片(漢)、模擬面試影片(英)
🧔：interviewer
👶：interviewee

17. Letter Combinations of a Phone Number

測驗說明與問答

🧔:你好，我是今天負責主持面試的David
👶:你好
🧔:希望你可以實作以下題目，有一串數字2~9的字串，每個數字都包含了一些字母，例如2可能表示a,b,c，在給你一串數字的情況下，返回這一串數字可能表示的所有字母組合，下面會給你對應的表格。

$$\left[\begin{array}{c}2:a,b,c\\ 3:d,e,f\\ 4:g,h,i\\ 5:j,k,l\\ 6:m,n,o\\ 7:p,q,r,s\\ 8:t,u,v,w\\ 9:x,y,z\end{array}\right]$$
👶:好的，我想再跟您確認一下題目的要求，2代表的是a,b,c，3代表的是d,e,f，如果現在有一串數字是23，我應該要表示出這兩個集合能表示出的所有組合嗎，像ad,ae,af,bd,be,bf…
🧔:你的理解是正確的。
👶:嗯…，我預計一開始會使用一開始會使用字典來記錄每個數字對應的字母，後續用一個迴圈來偵測每一輪的數字和其對應的字母，從第一個數字開始逐步將字母組合起來找出答案
🧔:聽起來不錯，你可以開始了
👶:好

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if digits=="":
            return []
        
        space={
            '2':["a","b","c"],
            '3':["d","e","f"],
            '4':["g","h","i"],
            '5':["j","k","l"],
            '6':["m","n","o"],
            '7':["p","q","r","s"],
            '8':["t","u","v"],
            '9':["w","x","y","z"]
        }

        ans = space[digits[0]]
        for i in range(1,len(digits)):
            ans = [char1 + char2 for char1 in ans for char2 in space[digits[i]]]
        return ans

🧔:恩 還不錯 但有沒有速度更快的辦法
👶:痾 我想想，我預計會用遞迴的方式寫出一個function，先從最尾端偵測數字，將其代表的字母回傳後再與前一個數字的字母組合，逐步推出答案
🧔:你可以開始了

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """

        if digits=="":
            return []

        space = {   
            '2': ["a", "b", "c"],
            '3': ["d", "e", "f"],
            '4': ["g", "h", "i"],
            '5': ["j", "k", "l"],
            '6': ["m", "n", "o"],
            '7': ["p", "q", "r", "s"],
            '8': ["t", "u", "v"],
            '9': ["w", "x", "y", "z"]
        }

        def generate_string(i):
 
            if i == len(digits):
                return [""]

            previous = generate_string(i + 1)
            new_string = []

            for letter in space[digits[i]]:
                for string in previous:
                    new_string.append(letter + string)

            return new_string

205. Isomorphic Strings

測驗說明與問答

🧔:很好，那那在第二個問題中，題目提供兩個字串s跟t，他們的長度都是相同的，你需要判斷他們是不是同構的，像add跟egg這種，如果是add跟geg雖然字母數量對的上，但他們不是同構的，同時還要滿足一些條件，像假如a對應到e，那d就不能再對應到e
👶:好的，所以我需要確認兩個字串是不是同構來回傳true or false，如果只是對應字母的數量相同，但位置不一樣的話也不算同構嗎
🧔:沒錯
👶:恩，那我會先寫出兩個字典來記錄每個字分別對應到哪個字，後續寫一個迴圈來依序判斷兩者是否相等，如果是第一次出現的字，會先檢查對應的字有沒有被使用過，沒有的話會將這兩個字母記錄在字典中，後續再出現相同字母的話，再來判斷他們對應的跟字典上記錄的是不是一樣的，最後判斷結果
🧔:好~你可以開始了

class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        space_s=defaultdict(str)
        space_t=defaultdict(str)
        
        
        for char_s,char_t in zip(s,t):
            
            if space_s[char_s]=="":
                if space_t[char_t]!="":
                    return False
                space_s[char_s] = char_t
                space_t[char_t] = char_s
            elif  space_s[char_s] != char_t or space_t[char_t] != char_s:
                return False
        return True

🧔:還不錯，但顯得有點複雜，有沒有方法可以幫助你簡化這段程式碼呢
👶:恩…我知道了，我馬上就可以實作
🧔:好的，請隨時開始

class Solution(object):
    def isIsomorphic(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: bool
            """
            zipped = set(zip(s, t)) 
            return len(zipped) == len(set(s)) == len(set(t))  

🧔:恩，你表現得很好，請隨時留意信箱有關第二次英語面試的通知

485. Max Consecutive Ones

測驗說明與問答

🧔:Hello, Yuanson, I'm David. Welcome to the second round of the interview. Let's get started
👶:hi, i'm ready
🧔:ok,Here's question,given a binary array nums, return the maximum number of consecutive 1's in the array.
👶:Alright, it's a binary array, so I'll have an array that consists only of 0s and 1s, and I need to find the length of the longest consecutive sequence of 1s.
🧔:right
👶:I guess I could use a for loop to iterate through the entire string. I'll use two variables: one for the current length and another for the maximum length. Whenever I encounter '1', I'll increment the current length; if I encounter '0', it will reset to zero. I will compare the current length with the maximum length and update the maximum length
🧔:sounds good, feel free to code it

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        temp = 0
        for i in range(len(nums)):
            if nums[i] == 1:
                temp += 1
            else :
                ans = max(ans,temp)
                temp = 0
        ans = max(ans,temp)
        return ans

🧔:good, Is there any way to speed up the program?
👶:Ummm, sure I can do it

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        temp = 0
        for i in nums:
            if i == 1:
                temp += 1
            else :
                ans = max(ans,temp)
                temp = 0
        ans = max(ans,temp)
        return ans

🧔:Well done, please wait for the following email
👶:thank you

自評

• 談話過程
  • 聲音忽大忽小不固定
  • 語速跟咬字可以再加強
  • 應在程式設計的環節有更多溝通，包含程式複雜度、可讀性等問題都可以討論
  • 術語可以再練習
  • 盡量把細節都想好，再開始談話，可以有點停頓
  • 英文的部分口齒不清更明顯，需加強
• 程式部分
  • 練習如何邊打邊解釋自己對程式的想法，又或是打完再完整講解
  • 部分程式碼可以再精簡

他評-01

interviewer

可改進之處

• 3:56: 有沒有速度更快的方法這裡，可以說明要朝著哪個方向改進
• 8:44: 可以改成能不能用python語法來達到先前程式碼的效果

interviewee

優點

• 0:53: 那個思考的眼神相當到位
• 在撰寫程式碼時，有說明這段程式的用途

可改進之處

• 0:31: 在說明例子時，可以配合圖解來說明，會比較清楚

他評-02

interviewer

優點

• 將205.融合，直接當作17.的後續討論

可改進之處

• 題目不應該只有口頭講

interviewee

優點

可改進之處

• 舉例應該邊講邊打在螢幕上
• 應該用Google文件等沒有自動補齊的工具撰寫
• 6:32: 沒有舉例何謂同構
• 都沒有說明時間和空間複雜度
• 2:25: 沒有解釋更快速的方法是什麼，直接說"I can do it."，而且使用的方法時間複雜度是一樣的

class Solution {
public:
    const vector<string> pad = {
        "", "", "abc", "def", "ghi", "jkl",
        "mno", "pqrs", "tuv", "wxyz"
    };
    
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
		vector<string> result;
        result.push_back("");
        
        for(auto digit: digits) {
            vector<string> tmp;
            for(auto candidate: pad[digit - '0']) {
                for(auto s: result) {
                    tmp.push_back(s + candidate);
                }
            }
            result.swap(tmp);
        }
        return result;
    }
};

class Solution {
private:
    void letterCombinations(string digits, vector<string>& output, string &temp, vector<string>& pad, int index){
        if(index == digits.size()){
            output.push_back(temp);
            return;
        }
        string value = pad[digits[index]-'0'];
        for(int i=0; i<value.size(); i++){
            temp.push_back(value[i]);
            letterCombinations(digits, output, temp, pad, index+1);
            temp.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()){
            return {};
        }
        vector<string> pad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> output;
        string temp;
        letterCombinations(digits, output, temp, pad, 0);
        return output;
    }
};

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map <char , char> rep;
        unordered_map <char , bool> used;
        for(int idx = 0 ; idx < s.length() ; idx++) {
            if(rep.count(s[idx])) {
                if(rep[s[idx]] != t[idx])
                    return false;
            }
            else {
                if(used[t[idx]])
                    return false;
                rep[s[idx]] = t[idx];
                used[t[idx]] = true;
            }
        }
        return true;
    }
};

他評-03

interviewer

優點

• 敘述題目時口頭清晰

可改進之處

• 3:54: 這裡可以請受試者分析一下自己寫的程式，分析完後適當引導受試者改善他的程式

interviewee

優點

• 表達清晰，React 以及 Example 做的很到位

可改進之處

• 雖然 React 以及 Example 表達清晰，但是應透過螢幕來實際舉例子會更加清楚

他評04

Interviewer

• 可以改進的部分

• 第一題討論優化時，面試官讓面試者提出改善的解法後，應該要先要求使用者分析時間複雜度來證明真的有優化的效果，而非直接讓面試者進行實作
• 第一題寫完後應該要跟面試者有更多的討論，像是舉例驗證實作的正確性，或是效能的改善等等，而非直接跳下一題

Interviewee

• 可以改進的部分

• 請不要把「d」念成「豬」
• 3:28 面試者講說要利用 Python 語法寫一個巢狀迴圈，可以直接講出是利用 Python 的 list comprehension
• 第一題應該要先解釋為何需要額外撰寫 inner function generate_string(i)，解釋這個 function 的功能，然後才開始實作
• 第一題的第二種作法有明顯的錯誤，inner function generate_string 沒有被呼叫到，且 digits 非空時沒有回傳值
• 第一題的第二種作法看起來只是換個語法寫，不太懂為什麼會有加速的效果，面試者應該要解釋
• 三題都沒有確實進行 REACTO，尤其是 Test 和 Optimization 的部分，無法呈現程式碼實作的正確性，且 Optimization 不應該只是在玩語法糖，應該要有更深入的效能分析和比較

他評-05

interviewer

優點

• 會給予 interviewee 肯定

可改進之處

• 應該給題目的文字說明(google doc之類的…)
• 詢問"速度更快的方法之前"，可以先請 interviewee 說明原先 code 的 complexity 再詢問能否有更簡便或更快速的解法。
• 8:48這邊 interviewee 還沒有說明要怎麼改進就直接讓他實作，應該先讓他說明他的想法，再從同事或是 co-work engineer 的身分跟他討論，最後有共識再實作。

interviewee

優點

• 有說明自己要怎麼實作，且實作前也有先確認一些題目上的疑慮。
• 有一邊撰寫程式一邊說明程式碼之意義。
• 題目都很快就想出解法。

可改進之處

• 沒有做 REACTO 的 Test，應該要跑跑看測資或自己想測資代入試試看程式碼正確性。
• 字典可以不用全列出來，interviewer 應該更在意的是解題的邏輯、想法，全列出來有一點冗，可以改用部分或 pseudo code 代替即可。
• 8:48這邊沒有說明要怎麼改進。