2022 資訊科技產業專案設計第四次作業

--- ###### tags: `資訊科技產業專案設計` --- # 2022 資訊科技產業專案設計第四次作業 [影片](https://youtu.be/jOx_k-f6ONk) ## 期末檢討在這次的作業中，模擬了真實和面試官互動的過程，從中學到的是需要大量練習才能克服實際寫 code 時的緊張感，在已知題目的情況下都很難完成把想法表達了，更何況是實際的面試。同時當面試官也是一們學問，要如何和面試者互動以及提供資訊都需要有很多的練習才能達成，在和 parter 演練時失敗了超級多次，也花了很多時間在重複錄相同的題目，很感謝有這次的作業讓我們練習面試。 **15.3sum** + [2:37](https://youtu.be/jOx_k-f6ONk?t=157) 應先用一些測資來輔助描述想法 + [4:23](https://youtu.be/jOx_k-f6ONk?t=263) 這邊在描述 start, end 的時候可以用上面測資來輔助示範，例如以下，接著嘗試推演如何找出合適的 triplet ``` -4, -1, -1, 0, 1, 2 s e ``` + [5:43](https://youtu.be/jOx_k-f6ONk?t=343) I forgot to set the ... 可以改為更肯定的語句，例如: in order to XXX, I have to create a variable to XXX + [8:20](https://youtu.be/jOx_k-f6ONk?t=500) 面試官可以要求面試者推演舉例一些極端測資，不然太草草結束了 **2130. Maximum Twin Sum of a Linked List** + 缺少 READ 步驟 + [14:11](https://youtu.be/jOx_k-f6ONk?t=851) 打錯了， j 應該是 < col, i < row，因為在前面 row 和 col 已經是 `nums1.size()+1` 和 `nums2.size()+1` + [16:06](https://youtu.be/jOx_k-f6ONk?t=966) 在描述解法的時候，可以先 action 再去實作程式碼 ## [15. 3Sum](https://leetcode.com/problems/3sum/) 👨🏻‍💼 : You are given an integer array. You have to return all the triplets such that the sum of triplets is zero and all index of triplet are different. Notice that the solution set must not cantain duplicate triplets. In example 1, an integer array is [-1,0,1,2,-1,-4]. There are three solution set as follow. 1. [-1,0,-1] 2. [-1,2,-1] 3. [0,1,-1] But set 1 and set 3 contain duplicate triplet,so you only return [[-1,0,-1],[-1,2,-1]] In example 2, an integer array is [0,0,0,0,0,0], you only return [[0,0,0]] > So can we assume that two triplets are duplicates because the elements inside are equal, even if these elements come from different positions in the original array? > Yes, Do u have any idea of this question > The brute force solution uses three indexes to loop over all the index combinations and checks whether the triplet sum is zero. 👨🏻‍💼 : This is quite intuitive, can you please analyze the time complexity? > The time complexity of this method is $O(N^3)$ (big-o-of n to the three) , which is not the best solution. 👨🏻‍💼 : Please improve your code so that the time complexity can be reduced to below $O(N^3)$ (big-o-of n to the three) > I think I can turn this question into fixing the first element of a triplet and finding the other two numbers after it. > We are going to start by sorting this array in order to jump over the duplicate first elememt. > for example > ``` > [-4 -1 -1 0 1 2 ] > [-4 -1 -1 0 1 2 ] # sort > ``` > I can fix the first element -4 and find the other two numbers after it. I would set a variable to indicate what the sum of the second and third elements must be. > Then I'll set 2 variables, start and end as the index of the other two numbers. If the sum of two variable is less than need, increment star. Otherwise, decrement end. When start+end is equal to need, it means we found the triple that the elements sum is zero. > But this solution has a problem, duplicate triplet would not be skipped. So I'll move the start and end index to the next position, and make it point to the next number that is not the same as the current point. 👨🏻‍💼 : Your explanation is very clearly, and you also answer this question. You have pass this interview ## [718. Maximum Length of Repeated Subarray](https://leetcode.com/problems/maximum-length-of-repeated-subarray/) [reference solution](https://leetcode.com/problems/maximum-length-of-repeated-subarray/solutions/127407/maximum-length-of-repeated-subarray/?orderBy=most_votes) 👨🏻‍💼 : You are given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays. > My initial idea is to use a dynamic programming. let dp[i][j] be the longest common prefix of nums1 [0:i] and nums2[0:j]. Whenever nums1[i] == nums2[j], we know dp[i][j] = dp[i-1][j-1] + 1. Also, the answer is max(dp[i][j]) over all i, j. for example: [1, 2, 3] [2, 3] 畫表格 👨🏻‍💼 : The idea is very good, and it is a typical dp application, please start to implement your code. > If I want to prevent index out-of-range error when IM reading d[i-1][j-1], I have to check if it's the edge or not. This will make the code massive. Instead of checking this, I'll just pad zero at the first row and column. > So first, I will create a two-dimensional array with row=length of nums1+1 and col = length of nums2+1. Then I'll fill this dp table and update the maximun common subarray length. 👨🏻‍💼 : You have used a two-dimensional array to record the cumulative length of the subarray, and a variable to record the maximum length, but can you reduce the memory usage? Your current program only uses the state of the previous row, and there is a way to save the space from a long time ago Can you save it? > I know exactly what you’re saying. I only use the prevous row to update current row, so i can use two array to store the current and previous state. 👨🏻‍💼 : Your explanation is very clearly, and you also answer this question. You have pass this interview ## [2130. Maximum Twin Sum of a Linked List](https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/) 👨🏻‍💼 : interviewer 👨🏻‍💻 : interviewee 👨🏻‍💻 : I just really want to understanding the problem before I start doing a massive code Briefly speaking, the definition of pair in this question is that the first and last are a pair, the second and the penultimate are a pair, and then the total If there are n nodes, there will be n/2 pairs. In these n/2 pairs, we will find the maximum value of these pairs. > Exactly right, any idea for the solution? 👨🏻‍💻 : My current idea is to use the fast and slow pointer to traverse the entire linked list first. Slow pointer and fast pointer are simply the names given to two pointer variables. The only difference is that, slow pointer travels the linked list one node at a time where as a fast pointer travels the linked list two nodes at a time.The slow pointer will store the value of the passed node in the vector. Then, the slow pointer will continue to travel the second part of linked list. When the slow pointer travels to the new node, I'll pair it with the node we have stored in the vector. I will also compare maximum values at the same time. :::info Then, the slow pointer will continue to travels the second part of ==linked list. When the slow pointer travels to the new node, I'll pair it with the node we have stored in the vector. 當慢速指針移動到新節點時，我會將它與我們存儲在向量中的節點配對。 ::: :::success Slow pointer and fast pointer are simply the names given to two pointer variables. The only difference is that, slow pointer travels the linked list one node at a time where as a fast pointer travels the linked list two nodes at a time. [Fast and slow pointer technique in Linked List ](https://iq.opengenus.org/fast-and-slow-pointer-technique/) ::: > I think you’re on the right track here, you use the fast and slow pointers to travel the first and second part of the linked list, and also when you make new pairs, you are going to update the max pair sum. 👨🏻‍💻 : Exactly yes > What are the time complexity and space complexity of your solution. 👨🏻‍💻 : Since the slow pointer visits the entire linked list, the time complexity is O(n), and because I use vector to store the values of the nodes, so the space complexity is O(n). > What would you do if I wanted to limit the space complexity to O(1)? I mean, without using an array to store the first half linked list. 👨🏻‍💻 : I think I can reverse linked list to replace vector. At the beginning, I still use the fast and slow pointer to traverse the entire linked list, In example 1 [5,4,2,1], slow pointer will point to node 2 at the end. I will reverse the second part of linked list. So,after reversing the second part of linked list, linked list will be [5,4,1,2]. There are two pointer such as head pointer point to node 5 and head2 pointer point to node 1.When head1 and head2 traverse the linked list Now I can add two node and compare the max value of pair node. :::info I think I can reverse the second part of the linked list. Then I'll use two pointers to point to the head and the start of reversed linked list. When they travel together, the two nodes of pointers point to would be a pair. In example 1 [5,4,2,1], slow pointer will point to node 2 at the end. I will reverse the second part of linked list. So,after reversing the second part of linked list, linked list will be [5,4,1,2]. ::: # 參考 [Google Coding Interview With A College Student ](https://www.youtube.com/watch?v=3Q_oYDQ2whs&ab_channel=Cl%C3%A9mentMihailescu) ## 實用的對話 ### Interviewer Here is an example, and feel free to ask me anything you want [18:55](https://youtu.be/3Q_oYDQ2whs?t=1135) Let's take quick step back because I think you're on the right track here {確認解題者的想法}, does that make sence? ### Interviewee So can we assume that {題目假設} [7:52](https://youtu.be/3Q_oYDQ2whs?t=472) So I think my initial kind of idea is {對題目的初步想法}. What I want to do then is {針對初步想法的做法} [10:50](https://youtu.be/3Q_oYDQ2whs?t=650) That't say I can generate my list that look like ... [12:44](https://youtu.be/3Q_oYDQ2whs?t=764) So what i think now i need to do is ... [14:26](https://youtu.be/3Q_oYDQ2whs?t=866) We are going to start by {作法} [17:50](https://youtu.be/3Q_oYDQ2whs?t=1070) .. does that answer your question? Exactly yes [20:59](https://youtu.be/3Q_oYDQ2whs?t=1259) {聽完 interviewer 建議的想法後 } I know exactly what you're saying [22:35](https://youtu.be/3Q_oYDQ2whs?t=1355) I just really want to understanding the problem before I start doing a massive code.