# 2025 年「資訊科技產業專案設計」課程第 1 次作業

> Richard 理查

## Introduction

### Interviewer
Hi Richard. Thanks for joining us today. I'm Dave, ML Lead Engineer at Moogle. And I’ll be leading this interview.
We'll start with a quick chat with you, then move into some technical questions, and wrap up your questions with us.
This is a conversation, not an interrogation, feel free to think out loud.
We will use Hackmd for our interview.
So, first of all, could you tell me more about yourself and walk me through your background?

### Interviewee
Well. Thanks for having me here. My name is Richard. I just graduated from NFU (National Failure University) at Computer Science department this June. I have done several projects during my college journey. The most prominent one is ChickNovel, it currently got 10K monthly users, and it is primarily served as a next-generation social media alternative.

### Interviewer
Cool. That is a great project, looking forward to future developments. So let's move on to the next part.

## [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/description/) - Easy

### Interviewer
In this part, we are going to evaluate your programming knowledge.
Imagine this situation, we got two real-time data streams delivering sensor readings that come from two distinct servers that are based in different regions. You'll need to create a merged stream that maintains the sorted time-order for further analysis. The data streams are stored as linked list. How would you solve this problem?

### Interviewee (Repeat)
Okay. So you would like me to merge two linked lists coming from different servers into one that is sorted in ascending time-order right?

### Interviewer
Correct.

### Interviewee (Example)
Cool. So, I would like to create a dummy input like this.
Let list1 contain 1, 3, 7, and 8, and list2 contain 2, 5, and 9.

> list1 = [1, 3, 7, 8]
> list2 = [2, 5, 9]

And the dummy output would be 1, 2, 3, 5, 7, 8, 9.

> result = [1, 2, 3, 5, 7, 8, 9]

Is my assumption correct?

### Interviewer
Yes.
So, how would you approach this problem?

### Interviewee (Approach)
Okay.
So, I will try to create a basic structure for the linked list, it contains a timestamp stored as an integer, and a value that stores sensor data, and a pointer that points to the next node.
This is a singly linked list.

### Interviewer
Can you explain why you choose to use singly linked list?

### Inteviewee
Sure. The reason for choosing this approach is simplicity. If we are ever going to merge two sorted lists. It is unlikely that we need to access the previous node, so singly linked list is the most suitable for this scenario.

### Interviewer
Okay. Then, for this case, we will only consider the singly linked list approach.
Please continue with your approach.

### Interviewee
Yeah. So the next part would be how should we merge two sorted linked list.
My first intuition would be to use a temporary pointer for the head of the merged list.
Then, I would create a indirect pointer that points to the head we created.
Then, I will use a for-loop to iterate through each node in list1 and list2.
Inside the loop body, I will determine whether one node has bigger value than the other node or not. If that is true, then I will store the greater-valued node using the indirect pointer. If the statement is false, then vice versa. And after each operation, point the current stored list to the next node.

### Interviewer
Talk is cheap, show me the code.

### Interviewee (Code)
First, I will define the List struct as such:

struct ListNode {
    int timestamp;
    int value;
    struct ListNode* next;
};

Then I will create a function to merge two linked lists.

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* head = NULL;
    struct ListNode** ptr = &head;
}

### Interviewer
Wait. So why do you need an extra pointer for indirection?

### Interviewee
So the reason for this approach is that we want to avoid memory allocation for this case.
If we use malloc instead of indirect pointer, then we need to free it somewhere else, the lifetime of this object is handed to the user, which might increase memory usage if the function caller does not free the list.

### Interviewer
OK.

### Interviewee
I'll continue to complete the code.
So, I would use a while-loop where it ends when both list nodes are empty. Let's just assumes that the last node is NULL.
Inside the loop body, we first compare the timestamp for list1 and list2, if the value in list1 is bigger, then we dereference ptr and assign it to list1. Then, we move list1 to its next node.
We do the opposite if the first timestamp is greater than or equal to value2. At the end of each iteration, we move ptr to its next node.

...
    while (list1 && list2) {
        if (list1->timestamp < list2->timestamp) {
            *ptr = list1;
            list1 = list1->next;
        } else {
            *ptr = list2;
            list2 = list2->next;
        }
        ptr = &(*ptr)->next;
    }
    return head;
}

### Interviewer
Okay. So did you find any edge cases your code didn't catch?

### Interviewee (Test)
Alright. I will try to run it with my dummy input.
The input i mentioned earlier is:
> list1 = [1, 3, 7, 8]
> list2 = [2, 5, 9]

And the dummy output is:
> result = [1, 2, 3, 5, 7, 8, 9]

each number represents seconds.
so in real data, we can represents it as 20250901132501 (2025/09/01 13:25:01)
Also, this number need 64-bit int to store, but here I use int for convenience.

So, let me go thorugh each cases.

### Interviewee (Optimize)
Oh. I see a bug there, I forgot to take into account the case where the two list aren't equal in number of nodes.
So, I can add this LoC to make the code more complete. So the idea is that when it traverse all the nodes, we might have a scenario where the number of list nodes in these two lists aren't equal; therefore, we need to choose one node as the last node of the merged list.

    *ptr = list1 ? list1 : list2;

### Interviewer
So. Could you tell me the time complexity and space complexity of this mergeTwoLists function?

### Interviewee
Yes. The time complexity is O(n+m) (worst case), and space complexity is O(1).
n and m is the number of nodes in list1 and list2. Because we need to iterate through them and rewire existing nodes. So the time complexity is these two numbers combined, or O(n+m). For space complexity, since only keep a few pointers in the function, therefore, it is O(1).

### Interviewer
Okay. I think that's all for the first problem. Let's move on to the next one.

## [190. Reverse Bits](https://leetcode.com/problems/reverse-bits/description/) - Easy

### Interviewer
Okay. So for the second problem, you need to create a function that reverses bits.
In many low-level protocols, the bit order on the wire doesn’t always match the way we represent bytes in memory.
For example, the USB protocol defines each byte is transmitted least significant bit first. What this means is that if we capture the raw USB traffic, we might need to reverse the bit order to understand what was sent.
So, how would you approach this problem with the bits being a 32-bit unsigned integer?

### Interviewee (Repeat)
Okay. So I will need to create a reverse bits function for 32-bit unsigned integer, right?

### Interviewer
Correct.

### Interviewee (Example)
So for example:
| IO | Binary |
| -------- | -------- |
| Input | 00000000000000000000000000011100 |
| Output | 00111000000000000000000000000000 |

The function will reverse the bits as shown in output.

Is my assumption correct?

### Interviewer
Yes.

### Interviewee (Approach)
So, my approach to this problem is to use a for-loop that iterates through each bit then use a bitwise shift operator
to find each bit and shift it start from MSB.

### Interviwee (Code)
I will now try to code it.

uint32_t reverseBits(uint32_t n) {
    uint32_t res = 0;
    for (int i = 0; i < 32; i++) {
        res |= ((n >> i) & 1) << (31 - i);
    }
    return res;
}

### Interviewee (Test)
I will use the example to validate this function.
| IO | Binary |
| -------- | -------- |
| Input | 00000000000000000000000000011100 |
| Output | 00111000000000000000000000000000 |

### Interviewer
Great. That is a good approach to this problem.
But, can you not use for-loops in your solution?

### Interviewee (Optimize)
Okay. I will try my best to do it.
My first idea is to use bit masks.
Since the width of the input are fixed at 32 bits, we can take advantage of that.
Also, we don't need to list out 32 possiblities for reversing.
We can do as such:

First, we can swap the first 16 bits with the last 16 bits.
Then, we can swap every 8-bit chunk
Then, we can swap every 4-bit chunk
Then, we can swap every 2-bit chunk
Then, we can swap every bit with its neighbor.

For example, if we want to reverse 0100,
we can separate it into 01 and 00 and swap their position
So, the new bit order becomes 0001.
And then, we swap the bits with its neighbor.
This then turns the bits into 0010 which is the reverse of 0100.

So. I'll change the code with our new approach using bit masks.

uint32_t reverseBits(uint32_t n) {
    n = (n >> 16) | (n << 16);
    n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
    n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
    n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
    n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
    return n;
}

### Interviewer
Great. That is a solid solution. So what is the Time & Space Complexity for this function you coded?

### interviewee
This function is basically constant in time and space complexity, which means O(1). But it is more efficient than my previous for-loop solution though they are all in O(1).

### interviewer
Great. Let's move on to our final problem.

## [322. Coin Change](https://leetcode.com/problems/coin-change/description/) - Medium

### Interviewer
For our final question: you are given an integer array coins (denominations) and an integer amount (target sum), write a function that returns the minimum number of coins needed to make up that amount. If it’s not possible, return -1. You can assume infinite supply of each coin.

### Interviewee (Repeat)
So, i will need to create a fucntion that calculates the minimum number of coins required to reach the target sum. Is that correct?

### Interviewer
Yes.

### Interviewee (Example)
So, I would first create an example.

For example, if we have an array of ints like this:
[1, 3, 4, 5]
If the target sum is 7. The minumun number of coins required for this is 2, which contains the 3 and 4 denomination.
Is my assumption correct?

### Interviewer
Yes, it is correct.

### Interviewee (Approach)
So, my approach to this problem would be using dynamic programming.
I will first define an array of length amount + 1 and each element having the value of amount + 1.
The length of the array is incremented by one because we need to consider where the amount is 0, meaning the target sum is 0 so the output would be 0, which means we need 0 coins.
Next, I set each element to amount + 1 because we are calculating the minimum number of coins required. So, having a number exceeding the amount whould serve as a maximum value that no one can reach.
Take our above example we should transform this idea into code:
The idea is that we want to create a bottom-up solution using dynamic programming.
let's bring back our example: [1, 3, 4, 5]
for each element inside the array, we define it as such:

dp[0] = 0 
dp[1] = 1
dp[2] = 1 + dp[1] = 2
dp[3] = 1
dp[4] = 1
dp[5] = 1
dp[6] = min(1 + dp[5], 1 + dp[3], 1 + dp[2], 1 + dp[1]) = min(2, 2, 3, 2) = 2
dp[7] = min(1 + dp[6], 1 + dp[4], 1 + dp[3], 1 + dp[2]) = min(3, 2, 2, 3) = 2

This is a proof-of-concept of how it should operate.

### Interviewer
Okay. I can see you trying hard to solve this problem. Can you implement your approach in C?

### interviewee (Code)
Sure. I'll implement it in C.

int coinChange(int* coins, int coinsSize, int amount) {
    int dp[amount + 1];
    
    for (int i = 0; i <= amount; i++)
        dp[i] = amount + 1;

    dp[0] = 0;
    
    for (int i = 0; i <= amount; i++) {
        for (int k = 0; k < coinsSize; k++) {
            int c = coins[k];
            if (c <= i && dp[i - c] + 1 < dp[i])
                dp[i] = dp[i - c] + 1;
        }
    }
    int ans = (dp[amount] > amount) ? -1 : dp[amount];
    return ans;
}

### Interviewee (Test)
I will use the example a wrote earlier for testing.

[1, 3, 4, 5]

### Interviewer
Great. In addition to that, can you tell me the time and space complexity of this function?

### Interviewee
So the time complexity is O(coinsSize * amount) = O(mn) and the space complexity is O(amount) = O(n).

### Interviewer
Great job. That’s all for today’s interview. Thanks again for your time and effort today, it was great hearing your thought process and seeing how you approached the problems. We’ll follow up with you soon.