# 2023 年「資訊科技產業專案設計」課程作業4

> 🧔：interviewer (Mason)
👶：interviewee (Richard)

[Mock Interview Video](https://youtu.be/L7ZVkQ7Zzj0)
[Expereince as an interviewer](https://hackmd.io/@GwGdlFb3S6mTM1qElX_NiQ/info2023-homework4)

## Leetcode 70
[Video link](https://www.youtube.com/watch?v=L7ZVkQ7Zzj0)

🧔: Hi, it's great to have you here for this interview today. We're going to discuss a pretty interesting programming problem that involves some fundamental algorithmic knowledge. But before we dive in, I want to make sure you're comfortable and ready. If you have any questions or need a break at any point, just let me know.

🧔: Alright, let's get started. Today's problem is about climbing stairs. Imagine you're facing a staircase with `n` steps, and you can climb either `1` or `2` steps at a time. Our task is to figure out how many unique ways there are to reach the top of the staircase. It seems simple, but it actually encompasses a lot of interesting points to ponder.

🧔: Before we delve deeper, I want to make sure we have a common understanding of the problem. Could you repeat the problem in your own words? Maybe give me an example to illustrate your understanding.

👶: Yes, I'll get a number `n` representing the number of stairs, and each time I can only climb `1` or `2` stairs, I need to find out how many different ways I can use to climb up to the top of stairs.

🧔: Great, it sounds like you've got a good grasp of the problem. How would you begin to tackle this problem? Let’s talk about your general approach before jumping into coding.

👶: I think this problem can be thinking like this, we can define a function $T(n)$, means the number of different methods we have when we're given `n` stairs.
If we take 1 stair at the first step, then we have `n-1` stairs left behind, which we can use $T(n-1)$ methods to climb up, otherwise when we take 2 stairs at the first step, we have `n-2` stairs left so we have $T(n-2)$ methods to use.

👶: This way, we can write down a recursion like the following, $T(n) = T(n-1) + T(n-2)$, once we have the recursion, we can solve it in Dynamic Programming.

🧔: That sounds like an interesting approach! Can you translate the method you just described into code? Furthermore, make sure that you program in C language.

👶 : Here's my solution in C

int climbStairs(int n) {
    int *methods = calloc(sizeof(int), n + 1);
    methods[0] = 0;
    methods[1] = 1;
    methods[2] = 2;
    for (int i=3; i<=n; i++) {
        methods[i] = methods[i-1] + methods[i-2];
    }
    return methods[n];
}

🧔:
The code looks good! Next, let’s test this code together. What are some scenarios that we should consider?

👶: (Test code with examples...)

🧔: We have a great starting point now. Let's discuss if there's room for optimization. Do you think there's a more efficient way to solve this problem?

👶 : I think the array `methods` waste too much space, now the space complexity of my solution is $O(n)$, I can try to reduce it to $O(1)$.
👶 : We can simply change `methods` into an array of length 3 and treat it like a circular array.

int climbStairs(int n) {
    int methods[3] = {0};
    methods[0] = 0;
    methods[1] = 1;
    methods[2] = 2;
    for (int i=3; i<=n; i++) {
        methods[i % 3] = methods[(i-1) % 3] + methods[(i-2) % 3];
    }
    return methods[n % 3];
}

🧔: That's great, I really appreciate your approach and thought process. Before we wrap up this part, do you have any other thoughts or questions to discuss? Or, do you have any different solutions to this problem?

👶: No, thank you.

🧔: Thanks for joinning us in the interview!

## Leetcode 101
[Video link](https://youtu.be/L7ZVkQ7Zzj0?t=1127)

🧔: Hi, thank you so much for joining us for the interview today. We're going to discuss an interesting problem about binary trees. This question tests not only your knowledge of data structures but also your logical thinking skills. Before we start, I want to make sure you're relaxed and comfortable. Feel free to tell me if you need to pause or have any questions.

🧔: You're given the root node of a binary tree, and your task is to check whether the tree is symmetric, meaning it's a mirror of itself around its center. This might seem straightforward, but there are some challenges in its implementation. Let's look at these two diagrams in the Google document. With the first diagram, as an example, we can see that the tree with the root of 1 has symmetrical left and right subtrees. However, in the second diagram, the left and right subtrees are not symmetrical, as the node opposite to the 3 on the left is null. Based on this rule, I would like you to write a boolean function. This function should take a series of numbers as parameters and determine whether they form a symmetric tree.

🧔: Before we start addressing this problem, I want to make sure we have the same understanding of it. Could you please restate the problem in your own words? Maybe give me a simple example to illustrate your understanding.

👶: As my understanding, you're going to give me the root of a binary tree. I'm going to show you whether the tree is symmetric or not. I want to make sure that the meaning of *symmetric* here, means that the left subtree is like the mirror of the right subtree?

🧔: Yes and great, let's talk about your solution. How do you plan to check whether a tree is symmetric? Before you start coding, let's discuss your thought process.

👶: Since the left subtree of the root should be the mirror object of the right subtree of the root, I think I'm going to compare the left subtree of `root->left` with the right subtree of `root->right`, and compare the right subtree of `root->left` with the left subtree of `root->right`, they should all be the mirror of each other when they're symmetric.

🧔: That's a good start! Now, let's translate your idea into code. Remember, clear and organized coding is very important. And while coding, feel free to explain your thought process to me.

👶 :
First of all I'll define the node structure for the tree

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

The following is my solution

bool Sym(struct TreeNode *leftR, struct TreeNode *rightR) {
    if (!leftR && !rightR)
        return true;
    if (!leftR || !rightR)
        return false;
    if (leftR->val != rightR->val)
        return false;
    return Sym(leftR->left, rightR->right) && Sym(leftR->right, rightR->left);
}

bool isSymmetric(struct TreeNode* root) {
    return Sym(root->left, root->right);
}

🧔: It looks like your code is complete! Next, let's test it together. Can you think of different scenarios to test your code?

👶: (Test code with examples...)

🧔: Your solution is quite creative. Now, let's discuss if there's room for optimization. Do you think it's possible to enhance the efficiency of the code or simplify its structure?

👶 : I know that some people might argue it's not good to write recursive function, but in this solution I use the advantage of [Tail Call Recursion](https://en.wikipedia.org/wiki/Tail_call), which can effectively reduce the overhead of accumulation of function stack.

🧔: Thank you very much for your participation and sharing today. Before we conclude this part, do you have any other thoughts or questions? Regarding this problem, do you think there are any other solutions?

👶: I have no problem, it's a great interview thank you.

🧔: Thank you, bye!