2023 年「資訊科技產業專案設計」課程第 4 次作業

秦谷底-Goody

第四次作業-他評01

• Interviewer：
  0:16不應該講說「還有其他問題嗎?」，面試者有問題會自己提出，加上這一句會顯得面試官很不耐煩
  11:45面試官講到有什麼改善空間，結果沒有看到改善了什麼，只是換了一個方法在重新實做一遍，最後時間&空間複雜度也沒有改善
• Interviewee：
  0:08可能要使用的package不只STL，應該直接詢問有什麼可以/不可以使用的套件，只詢問單一的library太過狹隘
  1:10講到worst case是要比較32次，前面面試官都詢問會發生什麼問題，面試者沒有講清楚會發生什麼問題，應該繼續講解這樣他有什麼壞處/會發生什麼事

布撥(Pawmi)

第四次作業-他評01

1:34即使費氏數列很值觀但還是要重新確定一次題目REACTO裡面少了Repeat
10:25改良方法不要把前面寫的蓋掉，直接在下面複製一個方便比較兩者差別
21:05你可以直接把fib_arr指定為global variable ，因為你每呼叫一次fib他還是會再重新計算一次，由於費事數列是固定的，那乾脆把表移到外面，可以更加減少計算冗餘

monk_interview

2295. Replace Elements in an Array

Interviewer: partner       Interviewee: me
Interviewer ：ok,so I will ask about the iterative question,and this question is about You are given a 0-indexed array nums that consists of n distinct positive integers. Apply m operations to this array, where in the ith operation you replace the number operations[i][0] with operations[i][1] and you have to return the array obtained after applying all the operations.
Interviewee： ok,does the first number in the operation must exist in nums?
Interviewer： yes
Interviewee： ok ,does the second number in the operation not exist in nums?
Interviewer： yes,alright
Interviewee： so it provides the distinct postive integers,right?
Interviewer： right
Interviewee： OK so let me repeat the question that you say ,so I have a number list and a numbers of operations and each operation's first number is in the nums array and the second number is the the first number we need to replace by right? so we need to return the modified array is that alright?
Interviewer： right
Interviewee： so let me make a example to guarantee the algorithm is right, we given the numbers array that is consist of [1,2,4,6]
and the operation is consist of [[1,3],[4,7],[6,1]],so the output answer will be [3,2,7,1],is that correct?
Interviewer： yes,that's correct
Interviewee： ok,To implement this problem first come to my mind is use 2 for loop to solve this problem and the outer for loop is for operations ,we need to iterate all the operations and inner for loop is for figure out what is need to be replaced in nums,so I will implement this method

class Solution:
    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
        for i in operations:
            for j in range(len(nums)):
                if nums[j]==i[0]:
                    nums[j]=i[1]
        return nums

Interviewer： OK,can you talk about the the time complexity and space complexity?
Interviewee： so we first define n is the size of nums and the m is the size of operations and the time complexity of this solution is O(MN) because we use two for-loop to iterate the nums and operation ,so at most gone through O(MN) times to solve this problem,and space complexit is constantly time because all the modifies in this solution is in nums array,so we don:t need to use extra space to record the numbers
Interviewer： OK, but the time complexity is not the optimal solution so can you improve the algorithm using another method?
Interviewee： OK, I can use dictionary to mapping the operations pairs and use 1 for-loop to iterate all the nums list and in each steps we just need to figure out whether the element is in the operations Dictionary and replace it,so it will cost O(N) to solve problem,is that right?
Interviewer： but if you use this approach it will be some numbers in nums be replace once if you encounter the situation that you have to iterate the numsfor two times ,this approach might not work,so canyou give another approach?
Interviewee： so you means if the nums is [1,2,4,6] and the operation will be [[1,3],[3,8]] if I use 1 for -loop to iterate numbers and 1 will only modify once I will miss the second replacement,did you means this?
Interviewer： yes
Interviewee： OK, we can change the operation from nums to operations and in each operations,we will need to use dictionary to record the nums's index,so in each step we just need to figure out the first nember in the operations' index abd replacement that index and update the second numbers index and so on,so I will return the nums,is that right?
Interviewer： yes,this approch is good
Interviewee： so I will implement this solution

class Solution:
    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
        Dict=dict()
        for i in range(len(nums)):
            Dict[nums[i]]=i
        for i in operations:
            nums[Dict[i[0]]]=i[1]
            Dict[i[1]]=Dict[i[0]]
        return nums

Interviewee： let me test this solution ,given the same example and we first build a dictionary that is equal to{1:0,2:1,4:2,6:3} and we just iterate the operations ,
in first step numwill become [3,2,4,6] and the dictionary will become {1:0,2:1,4:2,6:3,3,0}
in second step numwill become [3,2,7,6] and the dictionary will become {1:0,2:1,4:2,6:3,3,0,7:2}
in final step numwill become [3,2,7,1] and the dictionary will become {1:3,2:1,4:2,6:3,3,0,7:2}
this answer is equal to the first answer
Interviewer： OK can you talk about the time complexity and the space complexity in this method?
Interviewee： OK the the time complexity we first define M is for the size of operations,so the complexity is O(M) because we just need to use 1 for-loop to iterate the whole operations and the space complexity will be O(N) where N is the size of nums array because we need to build dictonary that consist of the numbers of nums so extra space is O(N)
Interviewer： OK,thanks for your time

21. Merge Two Sorted Lists

video

: interviewer(me)
: interviewee(partner)

: Hello, 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.

: I want to make sure I have correctly understand this question. First, I'll be given two linked list:list1 and list2, and I have to merge this two list to one sorted linked list, is that right?

: Yes, list1 and list2 will be sorted, so you don't have to worry about the unsorted condition.

: OK, I'll give a example:

list1 = [1,3,4]
list2 = [1,2,5]

output = [1,1,2,3,4,5]

: Yes.

: If it's correct, can I implement my code?

: you can speak out what you're thinking first.

: I'll use recursive method to implement my code. I'll create the function and repeatly call this function to sort these two linked list.

: OK, go ahead.

:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == NULL) return list2;
        if(list2 == NULL) return list1;
        if(list1->val < list2->val){
          list1->next = mergeTwoLists(list1->next, list2);
          return list1;
        }
        else{
          list2->next = mergeTwoLists(list1, list2->next);
          return list2;
        }
    }
};

: This is my recursive approach. And I'll use previous example to test my code.
First, it'll compare the value of list1 and list2' first value. It'll go to else condition, return list2's value to merge list. So the first value in merge list is 1. Next, pointer'll point to list2' second value:2, and the pointer in list1'll still remain value 1. This code have to compare these two value, 1 and 2. So it'll go to if condition, and return list1's first value:1. And next, first pointer'll point to 3, second pointer'll point to 2. So it'll go to else condition, and return value:2, and so on. The output will be [1,1,2,3,4,5] .

: You use recursive method to implement your code, but this method cause the problem of stack over flow. In order to avoid this problem, can you use another method to solve this problem?

: Instead of using recursive approach, I'll use iterative approach. I'll use while loop to gp through list1 and list2 to merge these two list into the merge linked list.

: OK, can you implement this method?

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* n = new ListNode(0);
        ListNode* merge = n;
        while(list1!=NULL && list2!=NULL){
            if(list1->val < list2->val){
                merge->next = list1;
                list1 = list1->next;
            }
            else{
                merge->next = list2;
                list2 = list2->next;
            }
            merge = merge->next;
        }
      if(list2 == NULL){
        merge->next = list1;
      }
      else{
        merge->next = list2;
      }
      return n->next;
    }
};

: OK, so what's the different between these two method? For example the time complexity and space complexity.

: I'll first talk about time complexity. In recursive approach, time complexity is O(n+m).

: Wait, what's n and m?

: n is number of value in list1, and m is number of value in list2. So in recursive method it have to go through list1 and list2 to merge these two linked list. Thus, time complexity in recursive method is O(n+m). And in iterative approach, its time complexity is O(n+m), too. Since it'll also go through list1 and list2.

: O(n+m) is happened in worst case?

: Yes, and in space complexity, recursive approach in worst case will be O(n+m). Because list1 and list2 is linked list, it have to store stack states. And in iterative approach, time complexity is O(1).

: OK, Thanks for you time. Good bye.

學期表現

---

我在這學期中從第一次作業開始發現到獨自刷題與將題目表達出來讓別人理解是兩件完全不同的事情，包括語速、贅字跟肢體表達一開始都我都很僵硬，但隨著自問自答的次數提升，讓我不會在面試期間腦袋一片空白，並且牢記老師的REACTO流程，讓我可以侃侃而談，我對於自己是混血非頂大電資感到自卑，對於未來找工作也深怕自己一直失敗，然而從學長姐的經歷與求學過程來看，許多的學長姐也不是一開始就非常頂尖，甚至有些學長姐還非本科，讓我認知到自己不必妄自菲薄，在未來我仍需要好好練習英文，在表達方面我仍需要好好努力包含用字遣詞與重音分配，我也希望能夠頭上外商的預聘or研替，讓自己創造出更高的價值