---
tags:
---
資訊科技產業專案設計課程作業 4
===
> Author: 盤子, Plate Man
> Partner: 伐木工, Worker
## Question 1: [Leetcode: 198. House Robber](https://leetcode.com/problems/house-robber/)
> 👤: Interviewer (盤子)
> 🐱: Interviewee (伐木工)
> [影片連結](https://www.youtube.com/watch?v=n0wXHwc20n8&ab_channel=kai)
👤: Hello, Welcome your interview today!,Let me introduce myself.I will be interviewing you today
👤: Today, we will have some questions for you, we would to understand your programming skills.And don't be nervous, it's just a discussion with you.
👤: First, May I ask you to introduce yourself?
🐱: Sure. I'm graduated from National Cheng Kung University and my major is Conputer Science. My thesis research is about Speech Recognition and Language modeling.
👤: OK,So you are the graduated student of CS at National Cheng Kung University, Then I think you'll have no problem with the questions later.
👤: Okay, let's start the first question. This is the file with question,You can open it now.
👤: This question is that you will become a robber, You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
👤:So in this question, You will be given an array nums representing the amount of money of each house, and you need to return the maximum amount of money you can rob tonight without alerting the police.
```
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
```
👤: Can you first tell me what you think about this question.and how you would like to solve it
🐱: My first idea is using Dynamic Programming. I will use a array to store the maximum value i can rob from the top n houses. And the formula would be like this.
```
T[1] = nums[1]
T[2] = max(nums[1], nums[2])
T[3] = max(T[n-2]+nums[n], T[n-1]), for 2 < n <= len
```
👤: OK I think this is possible, Can you write a code to solve problem?
🐱: OK. Do you have any prefer IDE and programming language for this interview?
👤: There are no restrictions on the language, but IDE we will use Vscode.
🐱: OK, I will use C++........Can you see my code now?
👤: Yes,Please start coding
```cpp
// T[n] = max amount of money i can rob from top n houses (including n)
// T[0] = nums[0]
// T[1] = max(nums[0], nums[1])
// T[n] = max(T[n-2]+nums[n], T[n-1]), for 1 < n < len
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
// edge case
if (len==1){return nums[0];}
vector<int> T;
T.push_back(nums[0]);
T.push_back(max(nums[0], nums[1]))
for (int i=2; i<len; i++){
int cur = nums[i] + T[i-2];
if ( cur > T[i-1]){
T.push_back(cur);
} else {
T.push_back(T[i-1]);
}
}
return T.back();
}
};
```
👤: Congratulations your code passes all of Test case. So, Can you tell me what the complexity?
🐱: Sure. About space complexity, since I use a additional vector to store the value I can rob from top n houses, so the space complexity is $O(N)$ which $N$ means the numbers of total houses. About time complexity, since I traverse the whole linked list only one time and for each iteration the operation only takes $O(1)$ time complexity, so the total time complexity is $O(N)$.
👤: I think that's right. But I think this code could be optimized, In your code, You have an array to store the robbed house numbers.But in this case, we only need you to return the maximum money, not to the house number. So, Maybe you can think a other solution without array of robbed house number to save the memory.
🐱: Hmm, I think maybe we can only use two variables which stores the value I can rob from the previous two houses and the previous houses. When I visit the current house, what I need to consider is should I rob this house? If yes, then the value I can rob would be the value of current house plus the value from the previous two houses. If ont, then the value would be the value I can rob from the previous house. So What I need to keep updating the two variables when I traverse all houses, and the two variables can replace the whole vector.
👤: I think that's great idea. please coding the new solution.
```cpp
// All I need is the aomunt of money, I dont need to trace back the house i rob
class Solution {
public:
int rob(vector<int>& nums) {
int len=nums.size();
// edge case
if (len==1){return nums[0];}
// the max aomount money i can rob from 0~prev house
int prevmax=nums[0];
// the max aomount money i can rob from 0~prev prev house
int pprevmax=Math.max(prevmax, nums[1]);
for (int i=2; i<len; i++){
// do iteration
int tmp = pprev+nums[i];
int prev=Math.max(tmp, prev);
int pprev=Math.max(prev, pprev);
}
return Math.max(prev, pprevmax)
}
};
```
👤: Great!,I can ask you last question, What is the complexity of the space.
🐱: In this case, since we only use two variables instead of a vector, so the space complexity is $O(1)$.
👤: Good,I think you answer this question very perfectly.
👤: So, We can going to next question.
## Question 2: [Leetcode: 328. Odd Even Linked List](https://leetcode.com/problems/odd-even-linked-list/description/)
> 👤: Interviewer (盤子)
> 🐱: Interviewee (伐木工)
> [影片連結](https://www.youtube.com/watch?v=C39pgF3V7HE&ab_channel=kai)
👤: OK, so there is an another problem. Given the `head` of a singly linked list, you have to group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.
👤: The first node is considered odd, and the second node is even, and so on.
👤: Note that you can not break the original order. For example
```
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
```
👤: Your output should be like `[1,3,5,2,4]`. `[1,5,3,2,4]` is not correc in this case since `3` is before `5` in ine original input. Do you have any questions?
🐱: So, What I need to do is to implement a function. The input of this function is s single linked list and this function have to group all nodes with odd indices and make these nodes linked by nodes with even indices. And the order in the group should remain as it was in the input. Am I right?
👤: Yes.
🐱: And is there any constraint about time complexity and space complexity?
👤: Yes, you have to solve this problem in time complexity in $O(N)$ which $N$ means the number of the nodes, and $O(1)$ extra space complexity.
🐱: Thanks for clarifying. Since I have to make the group with odd indice nodes followed by group with even indice nodes, so I need two pointers. The first one points the node with last even index and the second one points to the node with first odd index and I just need to make the first pointer connects to the second pointer, the result would be my answer. So there is my solution.
```cpp
/**
* 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* oddEvenList(ListNode* head) {
//edge case
if(head==NULL){return head;}
// otail: point to the node with last odd index
// ehead: point to the node with first even index
ListNode *otail=head;
ListNode *ehead=head->next;
// cur: point to the even index we current visit
ListNode *cur=head->next;
// For each iteration, we do
// 1. update the otail
// 2. connect odd to odd and even to even
while (cur!=NULL && cur->next!=NULL){
// connect odd to odd
otail->next=cur->next;
// update
otail=otail->next;
//connect even to even
cur->next=otail->next;
// move two steps forward
cur=cur->next;
}
otail->next=ehead;
return head;
}
};
```
👤: Great! it is correct. Here is another question for you. I'm going to do some slightly changes. Given the `head` of a linked list and a value `x`, partition it such that all nodes less than `x` come before nodes greater than or equal to `x`. For example
```
Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
```
👤: And note that you should preserve the original relative order of the nodes in each of the two partitions. Do you have any question?
🐱: So I have to implement a function and the input are the `head` of a single linked list and an integer `x`, and this function have to do partition such that all nodes less then `x` comes before nodes greater or equal to `x` and keeps the order unchanged. Am I right?
👤: Yes, you are right.
🐱: And should I need to consider the NULL case?
👤: Yes.
🐱: Ok. My first idea is to temprarily save two linked lists. The first linked list contains the node less then `x` and the second one contains greater than or equal to `x`. And then I will combine these two linked lists as the final result.
👤: Great, sound a good idea. Do you want to code it up.
🐱: Sure.
```cpp
/**
* 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* partition(ListNode* head, int x) {
// NULL case
if (head == NULL){return head;}
// shead is the return
ListNode *shead = new ListNode();
ListNode *bhead = new ListNode();
ListNode *stail = shead;
ListNode *btail = bhead;
// we need to update btail and stail
ListNode *cur=head;
while(cur!=NULL){
if (cur->val < x){
stail->next=cur;
stail=stail->next;
} else {
btail->next=cur;
btail=btail->next;
}
cur=cur->next;
}
stail->next=bhead->next;
btail->next=NULL;
return shead->next;
}
};
```
👤: Can you just briefly explain the time complexity and space complexity of your code?
🐱: Sure. About time complexity, since I only traverse the linked list in one pass, and for each iteration, the operation only takes $O(1)$, so the total time complexity is $O(N)$ which $N$ means the number of nodes in the linked list. About space complexity, since I use two additional nodes and two variables, so the space complexity is $O(1)$.
## Question 3: [Leetcode: 92. Reverse Linked List II](https://leetcode.com/problems/reverse-linked-list-ii/)
> 👤: Interviewee (伐木工)
> 🐱: Interviewer (盤子)
> [影片連結](https://www.youtube.com/watch?v=jOqr_t9kbFM&ab_channel=kai)
👤: Hello, Welcome to join this interview. Today we have a question for you. Do you have the document?
🐱: Should be..., Is this file right?
👤: Yes, Please open the document and let know fi you already open it.
🐱: Yes, I'm already open it.
👤: OK. Let me Explain the problem first. In this problem, you will given the head of a singly linked list and two integer `left` and `right` which `left` is less or equal to the `right`. You have implement a function to reverse the nodes of the list from position left to position right, and return the `head` of reversed list.
👤: For example. If the input is `[1, 2, 3, 4, 5]` and given `left` which value is `2`, and `right` which is `4`, and you need to reverse from position `2` to position `4`, so you need to output `[1, 4, 3, 2, 5]`. Do you have any question?
🐱: OK, let me think..., Do you have the format of the Node?
👤: Yes. Here is the format of Node.
``` python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
```
🐱: Got it, and is there any constraint about programming language?
👤: No constraint. You can use any language you want.
🐱: So Can I use python?
👤: Sure. So do you have any idea?
🐱: In this question, I think we can use list to solve it, We can store linkedlis values in a list and then use the reverse function in the list to revert the left and right values. In the end, we can save the list values to a new linkedlist and return the new linkedlist head.
👤: Sounds great, you can start coding right now.
``` python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
#if not head or not head.next: return head
values = []
while head:
values.append(head.val)
head = head.next
result = dummy = ListNode(0)
values[left-1:right] = values[left-1:right][::-1]
for v in values:
dummy.next = ListNode(val=v)
dummy = dummy.next
return result.next
```
👤: Great! it is correct. But if we want to do it in one pass, do you have any other solution?
🐱: Do it in one pass..., let me think..., if we divided the linkedlist into three linkedlist, head to left, left to right and right to end. First, we visit step by step to the left, Save the nodes named endOfFirst,Next create linkedlist named temp, when visiting left to right, save each node visited in the first position of the temp,and save the last node left to right named startOfSecond, in In the end, we set the endOfFirst next is temp, and the startOfSecond next is dummy, and then return the endOfFirst head.
👤: Sounds good. Do you want to code it up?
``` python
#class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseBetween(self, head, left, right):
if not head or not head.next: return head
result = dummy = ListNode(0)
dummy.next = head
for _ in range(left-1):
dummy = dummy.next
endOfFirst = dummy
dummy = dummy.next
startOfSecond = dummy
temp = None
for _ in range(left, right+1):
nxt = dummy.next
dummy.next = temp
temp = dummy
dummy = nxt
endOfFirst.next = temp
startOfSecond.next = dummy
return result.next
```
## 改進與本學期檢討
#### 改進
- 問問題的時候，應該可以給予適當的提示,並且在看到問題的時候,可以適時的給予建議與提示。
- 在解答問題的時候，在表達演算法上任需加強，尤其是使用英文的時候，很容易詞不達意，並寫在coding時，邊打邊說明應該要在更順暢，減少一些贅詞。
#### 本學期檢討
- 在本學期的課程中，知道了目前公司們有什麼職缺，有什麼需要努力並加強的，有哪些能力與說明是有所加分與扣分，並且對於coding面試的能力有大幅的加強，以往都太清楚白板題的時候，面試官會問什麼東西或是什麼內容，並在幾次作業中加強自我的面試能力，但自我覺得，雖然跟一開始還未練習比有所進步，但我認為還有極大的進步空間，包含表達能力與解釋能力，還有在面對未知問題時的回答都仍須加強！
Sign in with Wallet
Connect another wallet