Try   HackMD

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

畝畸陡-Ivan

模擬面試錄影(漢)

A: Interviewer
B: Interviewee

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

A:首先第一題，一開始會給你一個string array，那你要做的事情就是找出他們最大的共同前綴，如果他們沒有共同的前綴的話，那就回傳空字串，這邊有兩個例子(如上，逐字稿省略～)，請問你還有什麼問題嘛？

B: 沒有問題，那再做這個問題時，我會把他想成把所有字串並排在一起，然後先檢查他們的第一位是否都一樣，如果一樣那就檢查到下一位，直到檢查到任一個不一樣的，比如說已第一個例子為例（這邊邊寫例子邊講解）

A: 聽起來是個不錯的解法，請你吧他寫出來吧。

B: (如下)

//flower
//flow
//flight

// f -> l ->
sting lcp(vector<string> strs)
{
    if(strs.size()==0) return "";
    string res;
    for(int i = 0; i < strs[0].size(); i++)
    {
        char c = strs[0][i];
        for(int j = 1; j < strs.size(); j++)
        {
            if(strs[j].size() < i || strs[j][i] != c)
            {
                return res;
            }
        }
        res.push_back(c);
    }
    return res;
}

A: 可以請你說明一下這個驗算法的時間複雜度和空間複雜度嘛？

B:
Time complexity O(m*n)
Space complexity O(1)

A: 我們把題目做一些改變，一樣我們會給你一個存放string的陣列，但這個陣列不會有任何更動，是這次多一個 string q 目標是找出 陣列string 和 字串 q 的最長前綴
我希望你可以設計出一個在同個string set下，提高他每次在搜尋與字串q最常相同前綴的方法

以上一題為例

strs set = ["flower","flow","flight"]
q = fly => fl
q = dog => ""


strs = ["flower","flow","flight"]
q = fly => fl
q = dog => dog

B: 我可以理解為要設計一個資料結構儲存 string set 來加速他的查詢速度嘛？
A: 可以
B: 那我可能會用一個資料結構叫做trie的資料結構，他的特點就是如果字的前綴一樣的話那他們前面的路徑會是一樣的，舉上面的例子來說
trie

​​​​      f
​​​​     / 
​​​​    l
​​​​   / \
​​​​  o   i
​​​​ / 
​​​​w

/
e
/
r

A: 可以解釋為什麼這個資料結構可以加快找出 string set 與 q 的吹長前綴的速度嘛？

B: 因為當他們的前綴一樣，那他們就只會有一個child那當他們開始不同的時候就會出現多個child，因此只要去檢查child的數量是否等於一，如果是零或是大於一那就可以不用在搜尋了，所以他的時間複雜度是O(n) n是指q的長度

A: 那可以請你寫一下你會怎麼定義這個資料結構

B: (如下)

struct trie_node {
    char val;
    struct trie_node* children[26];
};

A: 那我們把題目定義完善一點，我們現在會傳入一個trie root以及字串q請你找出他們的最常前綴
B: (如下)

trie_node* helper(trie_node* root)
{
    int index = -1;
    for(int i = 0; i < 26; i++)
    {
        if(root->children[i] != null)
        {
            if(index==-1)
            {
                index = i;
            }
            return null;
        }
    }
    return index==-1?null:root->children[index];
}

sting lcp(trie_node* root, string q)
{
    if(root==null||q.size()==0) return "";
    trie_node* flag = root;
    string res;
    while(flag)
    {
        res.push_back(flag->val);
        flag = helper(flag);
    }
    return res;
}

互評

  • 0:00 不要用單聲道，很不舒服

  • 0:00 老問題了，不要講自己是面試官

  • 2:10 Interviewer可以提出更多關於constrain 的要求，比如字串大小會多大，但是interviewee也沒有問，所以這邊是一個大敗筆

  • 1:19 input 看起來明明像是一個list，其中有可能有不同長度的字串也有不同長度的list，Interviewee竟然沒有先詢問是不是只有像螢幕上一樣只有三個input，這點有非常大的瑕疵

  • 2:56 下面一直有東西在跑來跑去，有點傷眼睛

  • 8:36 明明time complexity 都已經打出來了，為甚麼不把space complexity 也一併打出來呢?

  • 13:42 剪接好像出了一點問題，這邊interviewee 重複講了structure 兩次

  • 18:21 明明前面正確的講出了 null 的音，為何這時候又變成了台灣的版本呢?

  • 20:51 剪接又出問題了，這邊又重複了一次，我還以為我中了伊邪那美

  • 0:54 interviewee 沒有問大小寫有沒有差別
  • 6:59 由上到下寫 code 很像在被答案，可以的話先寫 comment 再去把 code 實作
  • 8:21 沒有做 REACTO 的 T
  • 9:28 dog 應該要回傳 ""
  • 14:46 應該是 trie_node* children[26]; 而不是 struct trie_node* children[26]
  • 15:32 為什麼這時候 input 變成 tree node 而不是 string array? interviewee 沒有詢問 input。而且 如果 string array 都沒有 common prefix 那就會有3個 root，與面試者的 input 也不符合 (e.g., "dog", "cat", "flag" 會有3個 trie)
  • 17:05 寫 helper 應該先說明怎麼用 (client side) 然後才說明他的 function signiture，最後才是實作 code (這樣比較好懂)
  • 19:37 77 行打錯，應該是 if(root->children[i] != nullptr

互評02

15:20 string 拼成sting

18:22 children 拼成chrildren，如果怕拼錯，可以寫child就好

拼錯很多字會讓人觀感不太好，覺得你可能英文不好(?，並且也沒有及時發現錯誤

19:30 感覺對自己的答案也沒有很肯定(有在被答案得感覺)

Helper函數那段我有點沒聽懂，包括index那一段為甚麼要設-1跟回傳值，覺得可以先介紹你這段程式碼要做甚麼再來寫程式，否則一邊寫又一邊講解，會讓人很Confuse你現在寫的東西到底是甚麼作用

24:05 interviewer在說明題目的時候沒有提到input跟output的格式，interviewee也沒有問，跟上面的討論一樣，直接以傳進TreeNode為假設去實作，並且res的部分也沒有提到如果今天沒有common prefix是要回傳null嗎，還是怎麼樣的

Longest Mountain in Array

You may recall that an array arr is a mountain array if and only if:

​​​​arr.length >= 3
​​​​There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
​​​​    arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
​​​​    arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.

Example 1:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: arr = [2,2,2]
Output: 0
Explanation: There is no mountain.

A: 接下來來到我們的第二題，一開始會給你一個數列，請你找出一個數列滿足下列情形(如上)…那你要輸出子陣列的最長長度，這邊有兩個例子(如上)
B: 那在解這個題的時候，我會去計算現在上升和下降得長度，比如說(如下)，我會分成兩個數列 up, down。一開始預設都是0，然後一開始up是0然後1因為比2小所以還是0，然後4比1大所以加一up這邊是1，然後7比4大…down(這邊相反逐字稿省略) ，最後答案就會是down+up+1的最大值

     2 1 4 7 3 2 5
up   0 0 1 2 0 0 1  
down 1 0 0 2 1 0 0
down + up + 1

A: 可以請你把他實做出來嘛？

B: (如下)

int LongerstMontain(vector<int> arr)
{
    vector<int> up(arr.size(),0);
    vector<int> down(arr.size(),0);
    for(int i = 1; i < arr.size(); i++)
    {
        up = (up[i] > up[i-1])? up[i-1]+1 : 0;
        down = (up[arr.size()-i-1] > up[arr.size()-i])? up[arr.size()-i]+1 : 0;
    }
    int res = 0;
    for(int i = 0;i<arr.size(); i++)
    {
        if(res < up[i]+down[i])
            res = up[i]+down[i];
    }
    return res;
}

A: 請你解釋一下這個演算法的時間複雜度和空間複雜度
B:
Time complexity O(n)
Space complexity O(n)

A: 那你可以想出一個方法讓他的空間複雜度為O(1)
B: 那這邊我會用另一個方法，因為我們在算這個答案的時候，一定是先往上在往下，因此我這邊的目標是先找出他的左山腳在找出他的右山腳，並且下一個山的左山腳會是前一個山的右山腳

  2 1 4 7 3 2 5

A:

int LongerstMontain(vector<int> arr)
{
    int n = arr.size();
    int l = 0, r = 0;
    int res = 0;
    while(l+1<n)
    {
        r = l+1;
        if(arr[r]>arr[i])
        {
            while( r+1<n && arr[r+1]>arr[r])
            {
                r++;
            }
            if(arr[r+1]<arr[r]){
                while( r+1<n && arr[r+1]<arr[r])
                {
                    r++;
                }
                res = max(res,l-r+1);
            }
        }
        l = r;
    }
    return res;
}

互評

  • 26:38 7 為什麼是 2 沒有講清楚，這邊應該要說明 up 存的數值代表連續上升的 length
  • 26:23 這也是經典的sliding window 或是DP 的演算法，如果打從一開始就知道這個演算法，可以直接跟interviewer 講，跟他溝通為甚麼要這樣做，如此一來這題目就沒有一定要寫出來的必要了。再加上，在描述你的做法的時候並沒有提到approach是甚麼
  • 27:20 沒有解釋為什麼要反過來算
  • 28:21 沒有解釋為何兩者相加再加 1 就是答案。可以說『up[i] 代表由左至右到第 i 個數的連續上升長度，down[i] 代表到第 i 個數的連續下降長度，兩者相加再加上 1 (自己) 就是每個 element mountain 的長度』，還要補充說明，必須判斷第 i 個數是否為 mountain 的頂峰 (即 up[i], down[i] 都不為零) 才可以選這個數
  • 28:58 沒有溝通使用的程式語言，而且你 hackmd 上面是標注 C語言，但你使用 C++ 的 vector
  • 31:32 150, 151 行寫錯了，應該是
up[i] = (arr[i] > arr[i-1]) ? up[i-1] + 1 : 0;
down[arr.size() - i -1] = (arr[arr.size() - i - 1] > arr[arr.size() - i]) ? down[arr.size() - i] + 1 : 0;
  • 32:54 看起來有很大的問題，考慮測資
arr  4 5 4 4 3 2 1 0
up   0 1 0 0 0 0 0 0
down 0 1 0 4 3 2 1 0

sum  0 2 0 4 3 2 1 0

按照上面的程式會回傳 4 但正確答案為 2。而且最後應該回傳

return (res == 0) ? res : res + 1;
  • 34:21 『左山腳』會讓人聽成『左三角』，可以講 『左邊山的界線』我覺得會比較好懂
  • 37:31 177 行打錯，應該是 if (arr[r+1] > arr[r])
  • 40:45 你的程式碼如果放在 leetcode 跑是不會過的，幾個問題: max(res, l-r+1) 這邊 l 應該會小於 r，所以長度計算就錯了，還有很多的問題你自己找吧，感覺這邊沒有用心做，我附上我的版本，這邊我儘量在不改變太多你的實作方法的情況下讓測資過。其中我假設 l, r 是包含在 mountain 的(所以我寫 max(res, r - l + 1)

int longestMountain(std::vector<int>& arr) {

    int n = arr.size();
    int l = 0, r = 0;
    int res = 0;
    // 因為主要是 r 在前進所以我用 r 當作 stoping criteria
    while(r+1 < n)
    {
        if(r+1 < n && arr[r+1]>arr[r])
        {
            while( r+1<n && arr[r+1]>arr[r])
            {
                r++;
            }
            if(r+1 < n && arr[r+1]<arr[r]){
                while( r+1<n && arr[r+1]<arr[r])
                {
                    r++;
                }
                res = std::max(res,r-l+1);
            }
        }
        // 如果是平坦或是平坦後的下坡就讓 r 前進
        if (r + 1 < n && arr[r] >= arr[r+1])
          r++;
        l = r;
    }
    return res;
}

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [1]
Output: [1]

1 2 3 4
2 1 3 4


















struct ListNode
{
    int val;
    ListNode* next;
};

ListNode* swapPair(ListNode* head)
{
    if(head==nullptr||head==nullptr) return head;
    ListNode* tmp = head;
    head = head -> next;
    tmp->next = head->next;
    head->next = temp;
    head->next-next = swapPair(head->next-next);
    
    return head;
}

ListNode* swapPair(ListNode* head)
{
    if(head==nullptr||head->next==nullptr) return head;
    ListNode* cur = head;
    ListNode* next = head->next;
    ListNode* pre = nullptr;
    head = head->next;
    while(cur && next)
    {
        if(pre)
        {
            pre->next = next;
        }
        cur->next = next->next;
        next->next = cur;
        pre = cur;
        cur = cur->next;
        if(cur)
        {
            next = cur->next;
        }
    }
    
    return head;
}

互評

  • 43:52 你應該是想打 if (head == nullptr || head->next == nullptr) 吧
  • 45:32 應該要打 head->next->next = swapPair(head->next->next);
  • 45:34沒有做 REACTO 的 T
Last changed by 
 
sysprog
System Software Programming
0
104
Published on HackMD