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

contributer: 哈囉-Hi
video: 1, 2, 3

imterviewer interviewee

Maximum Average Subarray l

: Hi , I'm Jo. Here's a question for you . Given an integer array num consisting of n elements , and an integer k. Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value . Any answer with a calculation error less than 10^-5 will be accepted

: You means that I got an array and an integer , then I need to do the calculation to find the continuous part that contains four elements?

: Yeah , I think that's a great explaination .

: Well , I would like to use two for loop , one for the iteration of the entire array , the other for the calculation to sum up the elements in the subarray

All right. It sounds reasonable.

: Ok , I would like to start with giving some examples

Input : nums = [1,12,-5,-6,50,3] , k = 4

there are three subarray
[1,12,-5,-6] , [12,-5,-6,50] , [-5,-6,50,3]

with the sum be 
2 , 51 , 42

with avg be 
0.5 , 12.75 , 10.5

: I am wondering if there's a quicker solution?

: Umm…maybe I could use the sliding window to remove the first element in the current subarray and add the next element behind the last one in current subarray

程式碼

1.original

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double Max = 0; //max for the biggest value
        double part = 0; //part for the sum of each loop

    //loop through the array to find the max
        for(int i=0; i<= nums.size()-k ;i++){

            part = 0;

            for(int j=i; j<k ; j++){
                part+= nums[j];
            }
            
            if(part>Max)
                Max = part;

        }

        return Max/k;

    }
};

2.sliding window

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double Max = 0; //max for the biggest value
        double part = 0; //part for the sum of each loop

    //loop through the array
        for(int i=0; i<= nums.size()-k ;i++){

            if(i==0){
                for(int j=0; j<k ; j++){
                    part+= nums[j];
                }

                Max= part;
            }
            else{
            // slide the calculation window
                part = part - nums[i-1] + nums[i+k-1];
            
                if(part > Max)
                    Max = part ;
            }
        }

        return Max/k;

    }
};

Search in a Binary Search Tree

: The next question is about Binary Search Tree . Now , you are given the root of a binary tree (BST) and an integer val. Please find the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist , return null.

: Ok , so I am given a value and a root of a binary tree . Then , I need to search if there's any node that correspond to the value . If it exists , I should just output the root and the following node with preorder traversal .

: All right , please go on.

: Let me try to do it with some examples

in this photo , we find the corresponding value 2 in the trees , and then output the value based on the root with preorder traversal

: Yeah , it make sense

:Besides , since a BST would have bigger node in the left hand part , and smaller one in the right hand part , so we could use a if else to help it find the targer node quicker

程式碼

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {

        if(root == NULL)
            return NULL;

        if (root->val == val)
            return root;
        else if (root->val >val)
            return searchBST(root->left , val);
        else
            return searchBST(root->right , val); 
        
    }
};

Delete the Middle Node of a Linked List

:There is the final question . Given the head of a linked list . Delete the middle node , and return the head of the modified linked list. The middle node of a linked list of size n is the [n/2]^th node from the start using 0-based indexing , where [x] denotes the largest integer less than or equal to x.

: Ok , so I got a size n linked list , and I need to get rid of its middle node ?

: Yeah , it sounds reasonable .

: All right , let me start with some examples.

this is the example for odd counts of elements

this is for even counts of elements

: Then , how will you code this out

: I would start from named a new Listnode as front and tail , and assign the node of head to front , then iterate through head to find the size of this linkedlist . After that , I would go to that node before our target , then link it to the node behind our target , and thus delete the node . Besides , we should keep an eye on the case when size equals to 1 , we should just return NULL .

程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        ListNode* front;
        ListNode* tail;

        int size = 0;

        front = head;

        while(head != NULL){
            size++;
            head = head->next;
        }

        head = front;

        for(int i=1 ; i<size/2 ; i++){
            head = head->next;
        }

        if (size == 1)
            return NULL;
        else
            tail = head->next->next;

        head->next = tail;

        return front;

    }
};

初步檢討

interviewer

• 引導解題的方式不夠深入
  對於演算法的精進可以適度給予提示 ，或是引導interviewee去分析不同演算法的時間與空間複雜度，甚至是應用場景的細節
• 延伸原本問題的技巧
  若是能跳脫原本問題的框架，以延伸的想法與interviewee互動，或許更能挖掘出自己想要的人才

interviewee

• 寫程式時說話音量太小
  要保持interviewer聽得清楚的音量 ，或是盡量在coding前的解釋補充得更清楚 ，就不需再coding時分心解釋
• 表達流暢度的精進
  會有過多語助詞以及窮詞的狀況，若能流利地表達能給interviwer自己是 well-prepared and confidence 的印象

---

第二次作業-他評 01

關於 interviewer

• 優點

• 咬字清楚
• 舉例簡潔

• 可改進的地方

• Part 3 00:20: 與其照著 LeetCode 原題來描述，不如針對應用場景，說明為何要找出單向鏈結串列中間的節點 (並釋放記憶體)

  以 FreeRTOS 來說，就用鏈結串列來表示動態建立的任務

• Part 3 3:10: 避免只說 "How will you code this out?"，這樣的互動太草率，應該回顧 interviewee 提出的方法後，在適當的分析後，才說 "reasnable"
• Part 3 9:54: 避免過早說 "That's all"，聽起來太敷衍，應該針對程式碼討論，掌握 REACTO 流程，特別是 Test 及 Optimization
• Part 3 10:08: 避免過早說 "Look forward"，這樣可能會帶來非必要的暗示，應該給予評論和延伸問題

關於 interviewee

• 可改進的地方

• Part 3 1:53: 作為 interviewee，不該直接提及 LeetCode 及其範例，應該要能夠呼應 REACTO 流程
• Part 3 2:10: 在 Google Docs (或者協作的頁面) 中，一邊解說案例，一邊寫下，屆時開發程式時，可對照運用
• Part 3 2:18: 採用 0-based indexing，依據範例應該是左邊 (或右邊) 起算的第 4 個節點，不該說 "the third node"。可用類似以下說法:

  In a singly-linked list, when we use 0-based indexing, the first node is considered to be at index 0, the second node at index 1, the third node at index 2, and so on.
  So, in the example: 1 -> 2 -> 3 -> 4 -> 5
  The first node (index 0) is 1.
  The second node (index 1) is 2.
  The third node (index 2) is 3.

• Part 3 2:09: 應區分 node 和 element
  • A node is a fundamental building block of a linked list. It consists of two components:
    • Data: This is the actual information or value that you want to store in the linked list.
    • Reference (or Link): This is a pointer/reference to the next node in the sequence (in a singly-linked list) or both the next and previous nodes (in a doubly-linked list).
  • An element in the context of a linked list generally refers to the actual data or value stored within a node. It's what you retrieve or manipulate when you work with the linked list.

  Elements are the meaningful pieces of information that you are storing and managing using the linked list data structure. ChatGPT

• Part 3 2:48: 若及早定義 middle，並用偶數奇數來解釋，就可及早切入程式碼。4 / 2 = 2 的讀法是 "four divided by two equals two"
• Part 3 3:26: 字元太小，應適度放大，有利於後續討論。面試的場合通常不會用 LeetCode 網頁
• Part 3 4:04: front 和 tail 應該宣告在同一行，便於一面解說一面打字
• Part 3 5:01: "We might not… we cannot do the next progress" 聽起來過於武斷，究竟不記錄鏈結串列的長度到底會怎樣？
• Part 3 5:22: 避免頻繁地搖頭，可能會讓人誤會你在多個電腦螢幕之間切換視線，或者旁邊有人給你提示
• Part 3 5:50: 頻繁搖動滑鼠，很討厭，無助於溝通
• Part 3 6:07: "I forget that" 這句話不用說，應該強化 REACTO 流程，讓方法可對應到程式碼
• Part 3 7:35: 關於特例的討論，應該在 REACTO 的 Approach 階段提出

若用 Linux 風格的 cicular doubly-linked list 撰寫，優雅許多:

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *slow, *fast;
    slow = fast = head->next;
    for (; fast != head && (fast = fast->next) != head; fast = fast->next)
        slow = slow->next;
    element_t *element = list_entry(slow, element_t, list);
    list_del(&element->list);
    q_release_element(element);
    return true;
}

第二次作業-他評 02

interviewer

• 優點

• 用字簡潔

• 可改進的地方

• 介紹題目的時候，可以不完全把題目條件講清楚（測資範圍等），讓面試者自行思考極端情況、問清楚條件
• interviewee 完成題目後，可以請對方對演算法做分析，像時間複雜度，或是哪裡可以改進等 (Optimization)

interviewee

• 優點

• 有把範例用註解寫下來

• 可改進的地方

• 注意 coding style，固定使用大/小寫當作變數開頭（可能有面試官會在意）