# 資訊科技產業專案設計課程作業 4

## Q1 - [house-robber](https://leetcode.com/problems/house-robber/)

### 講稿
(👤:面試負責人 🐱‍:面試者)
👤: 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.

👤: Do you have any questions about the question?
~~🐱‍: In this problem, are there any other cases? like the array is empty or has the wrong type.
👤: there may be streets without houses, and there will be no happen with has the wrong type.~~
👤: 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 the Python,.......Can you see my code now?
👤: Yes,Please start coding
🐱‍: Coding.....
👤: OK, So you have finished the Code Right?,that's see it correct or not.
👤: Checking....
👤: OK, Congratulations, it passes all of Test case.
👤: So, Can you tell me what the complexity?
🐱‍: 說明...
👤: 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.
🐱‍: 思考...
👤: I think that's great idea. please coding the new solution.
🐱‍: coding...
👤: Great!,I can ask you last question, What is the complexity of the space.
🐱‍: 說明...
👤: Good,I think you answer this question very perfectly.
👤: So, We can going to next question.
### 問題

- interviewer
- Can you introduce yourself in 1 min?
- What the complexity is in V1?
- If today have space complexity constraints,Do you have other solution?
- interviewee
- Do you have any prefer IDE and programming language for this interview?
- In this problem, are there any other cases? like the array is empty or has the wrong type.
- Are there any limit with Time and Space Complexity?

### Code

#### V1 : DP

// T[n] = max amount of money i can rob from top n houses (inclu. 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(); 
    }
};

#### V2: Space optimization

// 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)

    }
};

---

## Q2 - [Odd Even Linked List](https://leetcode.com/problems/odd-even-linked-list/description/)

### Code

### Code 2 變化題 [Partition List](https://leetcode.com/problems/partition-list/)

### 講稿

👤: 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.

🐱‍: (Coding...)

👤: (Validating...). 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.

🐱‍: (Coding...)

👤: Can you just briefly explain the time complexity and space complexity of your code?

🐱‍: (Explain...)

### 暫定綠影時間

### Code

## Q3 - [Reverse Linked List II](https://leetcode.com/problems/reverse-linked-list-ii/)
### 暫定綠影時間

### 講稿

👤: Hello, Welcome to join the 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.

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?
🐱‍: (Explain...)
👤: Sounds great, you can start coding right now.
🐱‍: (Coding...)
👤: (Validating...). 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..., what if (explain...)
👤: Sounds good. Do you want to code it up?
🐱‍: Sure. (Coding...)
👤:

### Code
#### v1

# 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

#### v2

#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
        last = None
        for _ in range(left, right+1):
            nxt = dummy.next
            dummy.next = last
            last = dummy
            dummy = nxt
        endOfFirst.next = last
        startOfSecond.next = dummy
        return result.next

1 2 3 4 5 6 7 8 9 
3 7
1 2 7 6 5 4 3 8 9
<1> <   2   > <3>