2022 年 <a href = 'https://hackmd.io/@sysprog/info2022/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FBJLSJ3ggi'>「資訊科技產業專案設計」</a>作業一

###### tags: `info2022-homework1` # 2022 年 <a href = 'https://hackmd.io/@sysprog/info2022/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FBJLSJ3ggi'>「資訊科技產業專案設計」</a>作業一 >藍寶-Rumble > :100: Interviewer :8ball: Interviewee :a: Narrator ## [20. Valid_Parenthesis](https://leetcode.com/problems/valid-parentheses) ### 模擬面試過程 :a: : Hello, welcome to my interview. Today, I'm going to show you how I deal with my interview, and as an interviewer and an interviewee, how would I deal with both of the situation that I encountered. :8ball: Trashtalk: OMG, soon it's gonna be my interview, i didn't prepared at all, i wonder how would they test me, what if I don't know the answer!! **--until 36s its all trash talk, fell free to fastforward it---** ________________________________________________________________________ :100: Hello my name is Caleb, today's interviewer, i will be conducting your interview today, and for today's interview, I will give you one question. And you will try your best to answer it, and no matter how good are you, just answer it, and we'll see how it goes, ok? Okey.. so the question goes like this : Given a string (s), containing just the character left parenthesis and right parenthesis, and braskets... and lot of stuff, and your job is to determine if the input string is valid :8ball: : hmph... let me think about this, but first, can i ask you some question? I don't think you've explained the question clear enough... So, what do you mean by "valid"? :100: : sorry I didn't quite explained myself today, today's question will be... (explaintation) :8ball: Good, so my approach would be like this, if i encountered braskets like this, I'll put it into a stack like this, ~~~ {{{}}} ~~~ and the target looks like this, keep in mind that this is a valid parenthesis, and I will give another example is not valid which is like this: ~~~ {[]]}] ~~~ so i will run a for loop, if I encountered a brasket, I'll put it on the stack, and if the second brasket is an open brasket, I'll put it on the stack too, and so on... and if i encountered the closing brasket, i'll just pop out the first stuff in the stack, and if i get the right brasket, i can keep on going until the stack is empty, if not, i'll simply return the false boolean val. :100:Ok... i'll start coding right about now, so.... ~~~ code: bool isValid_parth(char*s){ char *stack = malloc(2000*sizeof(char)); unsigned int stack_p = 0; for(int i =0;s[i]!='\0';i++){ swich(s[i]){ case'(': case'{': case'[': stack[stack_p++] = s[i]; break; case')': if(!stack_p||stack[--stack_p]!='(') return false; break; case']': if(!stack_p||stack[--stack_p]!='[') return false; break; case'}': if(!stack_p||stack[--stack_p]!='{') return false; break; } } } ~~~ :100: Ok, you've actually given a correct answer. So.. I think we'll keep in touch for the next interview, and we will see whether you can get another job done, ok see ya. ____ ### 自我面試檢討 No.1 1. 首先我要說，這幾次面試為了達成高度的真實性，在coding時，並沒有先寫稿，而是只有在腦中模擬想要講的東西，所以部分英文非常卡，而這也是我不樂見的。 2. 在技術層面上，個人覺得宣告一個2000的陣列好像有一點問題，這樣空間非常沒有效率，可以更改成Linked List based stack，如此一來，雖然實作方面會比較複雜，但如此一來就不會浪費到太多空間 3. 除此之外，在面試時，我沒有多問面試官，大約會有多少長度的String 4. <忘記打馬賽克> 5. 與其用switch case,也許可以找不同的做法，也許可以使用enum來增加可讀性，也許可以利用Recursive approach 6. REACTO 中貌似少了T的片段 _____________________________________________________________________ > :100: Interviewer :8ball: Interviewee :a: Narrator ## [876. middle-of-the-linked-list](https://leetcode.com/problems/middle-of-the-linked-list/) ### 模擬面試過程 :a: Hello my name is Rumble, here again you're in my interview, this is the second interview i recorded, this time the question will be <s>more</s> even harder than the last time, so, enjoy. ________ :100: Hey, Caleb again, you're rumble right? So last time you did a great job on given a valid parenthesis, so this time i will ask you some classic questions about linked list.. so... brace yourself for today's question. :8ball:Alright, Caleb, so... give me the stuff. :100: Ok, so the question goes like this: Given a linked list, you need to return the middle value of the linked list. :8ball: Wait... what do you mean by middle value? Do i return the middle value of that specific linked list, or i just return the whole linked list after the middle value? :100: Sorry Rumble, let me clarify the question again. so the question goes like this: I want you to return the whole linked list after the middle value "including" the middle value. :100: Alright Rumble, I will give you some examples about that linked list so.... ~~~ examples: 1->2->3->4->5 return 3->4->5 ~~~ :8ball: This question seems a little bit hard for me, so I'll give out my thought about it. So, my first approach would be: First I'll run a for loop to calculate the vertices in this specific linked list, and then I will do another for loop in order to give out the middle value of that specific linked list :100: Great, do you want to code it up? :8ball: Sure, I'll get right onto that..... ~~~ First approach: struct List*{ int val; struct List*; }; struct List* middle(struct List* head){ if(head == NULL) return NULL; else if( head->next == NULL) return head; else if(head ->next->next == NULL) return head->next; int sum_of_vertices = 0; for(struct List* temp = head; temp; temp = temp->next){ sum_of_vertices++; // after this finished, we will get the sum of the vertices in the link list } int mid = sum_of_vertices/2; struct List* temp = head; for(int i = 0;i<mid;i++){ temp = temp->next; } return temp; } O(2*n) n = the lengtlh of the linked list; ~~~ :100: you've actually did it in linear time. But, here's some question about your approach, i think your approach is a little bit too slow, your TC is O(2*n), I think you can make it faster. Think about it, and tell me your approach, or else. :8ball: hmn... let me think about this. If I... :100: You might want to hurry up, cuz our interview only has 10 mins left. :8ball: Let me think about this... Oh! if I have one single pointer and another double pointer, if the double pointer goes all the way down to the end of the linkeed list, then the single pointer will be just right in the middle of that. :100: Ok, if you'll like to hurry it up, today's interview is almost at an end. could you do it real fast? :8ball: Ok i'll get right onto that. :8ball: okey.. suppose we have... ~~~ struct List* middle_val(struct List* head){ if(head == NULL) return NULL; else if(head->next == NULL) return head; else if(head->next->next == NULL) return head->next; ////declare the pointer of single and double; struct List* single_p = head; struct List* double_p = head; struct List* temp; while(true){ single_p = single_p->next; double_p = double->next->next; temp = double_p; if(temp == NULL) break; else if(temp->next ==NULL){ single_p = single_p->next; break;} } return single_p; } O(n/2) ~~~ and it is trememdous faster than the previous sol. :100: Great job Rumble, you actually did it in the leaner time, and i think you've made it to the third interview, so brace yourself for the third one. ____ ### 自我面試檢討 No.2 1. 部分coding 時有一點jump into conclusion 的感覺，除此之外，我在後面思考時，我覺得可以在此提出找到中間點的意義 (我還沒有想出來） 2. 在Coding時，我希望下次可以提到更brute的方式，後來有想到可以直接複製一個linked list，而空間複雜度更高的做法，進而提供面試更多互動 3. 16:43 吃螺絲 4. 並沒有提供詳細的Test _____________________________________________________________________ > :100: Interviewer :8ball: Interviewee :a: Narrator ## [24. swap-nodes-in-pairs](https://leetcode.com/problems/swap-nodes-in-pairs/) ### 模擬面試過程 :a: Hello Rumble here again, today, I'm going to show you my third interview as an interviewer and an interviewee. :a: Let's bring out the interviewer. ________ :8ball: Oh I'm so nervous about the third interview, I don't think I can get in the company i always dreamed of... I think i might have a heart attack... Ok, nevermind, I need to be confident, let's face the music!! :100: Hello, Caleb here again, you're Rumble right? OK today's your third interview, today I'm going to give you even harder question than the previous question. And.. today's question will be :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 :8ball: Okey, Caleb, if you would let me clarify your question and repeat it again? It's :Given a linked list I need to swap every two nodes and return its head so if I have a linked list like this ~~~ input= 1->2->3->4 res = 2->1->4->3 ~~~ Right? :100: Correct, you need to swap every two nodes that you encountered, so what do you want to do about it? :8ball: Ok, let's go with my intuitive thought that is to input every two nodes into the function, and then, swap every two nodes recursivelly and finally return the whole list back to you! :100: Great! you can start working on it! :8ball:Ok because this is a linked list problem..... ~~~ struct ListNode { int val; struct ListNode* next; }; struct ListNode swap_two_nodes(struct ListNode* head){ //recursive function if(head == NULL || head->next == NULL) return head; struct ListNode* tmp = head->next; head->next = swap_two_nodes(tmp->next) // input will be head->next->next; temp->next = head; return head; } TC = O(N), SC = O(N)>stack ~~~ :100:Good!, so got the recursive function right, but i think the SpaceComplexity of your function is still a little bit high... Could you make it iterative? :8ball:Okey... so first i'll need to move my code down to the bottom... ~~~ struct ListNode { int val; struct ListNode* next; }; struct ListNode* swap(struct ListNode *head){ if(head == NULL || head->next == NULL) return head; struct ListNode* current = head; struct ListNode* prev; head = current->next; while(true){ if(current == NULL || current->next == NULL) return head; prev = current; current =current->next; prev->next = current->next; current->next = prev; if(current != NULL) if(current->next != NULL) prev-> = current->next; } return head; } ~~~ :100: Okey. good job, you've actually constrained your space complexity back to one by using the iterative function. So i think that's a wrap for today's interview, maybe we will inform you the detail about your work, so, see ya. ____ ## 自我面試檢討 No.3 1. 此題目同理，我並沒有提到為甚麼要swap every two nodes，我也想不到為甚麼，我想要請問老師或是同學告訴我為甚麼這問題要存在，要解甚麼樣的問題，還是就為了問而問 2. 原本要做另外一題 [200.numbers of island](https://leetcode.com/problems/number-of-islands/)，但由於我不會想不出非recursive的方式，於是我才挑選另外一提可以提供更多互動性的題目。