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

> 貢獻者
> 艾瑞克 - Eric, 狄雲 - Louis
> [面試錄影 1](https://youtu.be/o7lG0KtWNis)
> [面試錄影 2](https://youtu.be/P1nmfCAj_jo)

## [Leetcode: 64. Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/description/)

**Interviewer:** Hello, I’m your interviewer,.Today I’ve prepared a coding problem, I hope you can discuss the solution with me.

**Interviewee:** Hi, Louis. Nice to meet you.

**Interviewer:** So, here’s the problem: You're developing a 2D adventure game. In the game, the main character starts at the top-left corner of the grid and needs to navigate to the bottom-right corner. Each grid cell has a number representing the stamina cost(所需體力) to step on it. The character can only move either right or down at any given time. You wonder how to get the path that allows the character to reach the destination with the minimum stamina expenditure.

**Interviewee:** So I would like to clarify the problem. The input will be a 2D array, and I would have to output an integer indicating the minimum cost of stamina.

**Interviewer:** Exactly.

**Interviewee:** Are there any constraints I should keep in mind, such as the grid size or the range of the numbers in the grid?
Interviewer: We’ll assume the grid size is reasonably small, say up to 100x100, and the stamina values are non-negative integers within a reasonable range, such as 0 to 1000.

**Interviewee:** Understood! I’ll rephrase the problem to confirm my understanding. We have a grid where each cell represents a stamina cost, and the character can move only right or down. Our goal is to find the minimum stamina required to traverse from the top-left to the bottom-right.
For example, given the grid [[1,3,1],[1,5,1],[4,2,1]], the optimal path would cost 7. Another example is [[1,2,3],[4,5,6]], where the optimal path would cost 12. Is that correct?
Interviewer: You’re right.
Interviewee: Then I’d approach this using dynamic programming. The idea is to build a DP table where each cell represents the minimum stamina required to reach that point. Starting from the top-left, we can iteratively calculate the minimum cost to reach each cell by considering the costs from the top and left neighbors.

**Interviewer:** Good. Can you tell me what the time complexity is?

**Interviewee:** Since the program traverse through every grid, the time complexity will be proportion to the grid size, which we assume to be m*n. So the time complexity is O(m*n). The space complexity is also O(m*n) since a dp table is used.

**Interviewer:** Great. Let’s see how you implement it.

**Interviewee: **

#include <vector>
#include <algorithm>
using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    int rows = grid.size();
    int cols = grid[0].size();
    vector<vector<int>> dp(rows, vector<int>(cols, 0));

    dp[0][0] = grid[0][0];

    // Fill the first row
    for (int col = 1; col < cols; ++col) {
        dp[0][col] = dp[0][col - 1] + grid[0][col];
    }

    // Fill the first column
    for (int row = 1; row < rows; ++row) {
        dp[row][0] = dp[row - 1][0] + grid[row][0];
    }

    // Fill the rest of the DP table
    for (int row = 1; row < rows; ++row) {
        for (int col = 1; col < cols; ++col) {
            dp[row][col] = min(dp[row - 1][col], dp[row][col - 1]) + grid[row][col];
        }
    }

    return dp[rows - 1][cols - 1];
}

## [Leetcode: 102. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/description/)

**Interviewer:** Hi, I'm Louis from Google. Today we'll be doing a coding interview. I'll share a problem with you and we can discuss your solution.

**Interviewee:** Hi Louis, nice to meet you. I'm ready.

**Interviewer:** Great. Here's the problem: Imagine you're developing a corporate organizational structure system. Every company has a tree-like organizational structure, starting with the CEO, followed by department heads, and each department head has their own team members. We need to implement a feature that generates an "employee list sorted by job level," specifically:First level is the CEO, Second level contains all department heads, Third level contains all team leads, and so on...
We need to ensure that within each job level, employees are arranged from left to right according to their departments. This way, HR can clearly see all personnel at each level when doing level-related planning. What do you think about this scenario? Would you like to try solving this problem?

**Interviewee:** Let me confirm the requirements. Essentially, I need to implement a function that takes the root node of an organizational tree (like the CEO) as input, and returns a 2D array where each subarray represents employees at a particular job level, arranged from left to right according to their departments. Is that correct?

**Interviewer:** Yes, that's exactly right.

**Interviewee:** Let me provide some examples. Consider this tree:

    3
   /  \
  9   20
      / \
     15  7

The output should be: [[3], [9,20], [15,7]]
Another example would be an empty tree:
The output should be: []

**Interviewer:** Good examples. How would you approach solving this problem?
interviewee: I'll use BFS (Breadth-First Search) with a queue to store nodes at each level. Here's my approach:
Create a queue and push the root node
While the queue is not empty:
Get the size of the current level
Collect values from these nodes to form the current level result
Add their left and right children (if they exist) to the queue
Repeat step 2 until the queue is empty
This ensures we process nodes level by level and from left to right.
Interviewer: Sounds like a solid approach. Can you code it up?

**Interviewee:** Sure, I'll implement it in C++:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;
        
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                currentLevel.push_back(node->val);
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            result.push_back(currentLevel);
        }
        
        return result;
    }
};

Time complexity is $O(n)$ where n is the number of nodes, as we visit each node exactly once
Space complexity is $O(n)$, mainly due to the queue which in the worst case stores all nodes of the last level

**Interviewer:** Excellent! Your solution is very thorough and you've covered all the important aspects. Now, let’s add a twist to the problem. Could you modify your code so that the traversal alternates between left-to-right for odd levels and right-to-left for even levels? For example:
Given this tree:

    3
   /  \
  9   20
      / \
     15  7

The output should now be:
[[3], [20, 9], [15, 7]].
How would you approach this change?

**Interviewee:** That’s an interesting twist! Let me update the solution. Here's my plan:
I’ll still use Breadth-First Search (BFS) with a queue.
At each level, I’ll use a flag to track whether we should traverse left-to-right or right-to-left.
If it’s right-to-left, I’ll reverse the currentLevel array before adding it to the result.
The flag will toggle at the end of each level.
Let me code this up.

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;
        
        queue<TreeNode*> q;
        q.push(root);
        bool left_to_right = true; // 初始化方向標誌，第一層為從左到右

        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                currentLevel.push_back(node->val);
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
             // 根據方向標誌處理當前層的結果
            if (!left_to_right)
            {
                reverse(currentLevel.begin(), currentLevel.end()); // 如果是從右到左，反轉結果
            }
            result.push_back(currentLevel);        // 將處理後的層結果加入最終結果
            left_to_right = !left_to_right; // 切換方向標誌
        }

            result.push_back(currentLevel);
        }
        
        return result;
    }
};

Time complexity is still $O(n)$, as we visit each node exactly once.
Space complexity remains $O(n)$, as the queue holds nodes from the last level in the worst case.

**Interviewer:** Great! This modification works perfectly. I appreciate how you adapted your solution to handle the new requirement. Thank you for your time, and we’ll follow up soon about next steps.

**Interviewee:** Thank you for the opportunity!