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

貢獻者：伊娃咳夫-Ivancough
影片一
影片二

64. Minimum Path Sum

Interviewer:

Hi, welcome to the interview. My name is Ivancough, and I work as a research and development Engineer at Amazon. Let’s get the interview started.

Imagine you are part of the IT team at an e-commerce company like us. The team is trying to implement a delivery robot navigates a warehouse. The warehouse can be represented as a grid, where each cell contains a cost of traversal, and the robot can only move right or down.

So, your task is to write a function that calculates the minimum cost for the robot to navigate from the top-left corner to the bottom-right corner of the grid. And you’ll get a two-dimensional array that each element contains the cost of traversal. Do you have any questions about the problem statement?

Interviewee:
To summarize, I need to calculate the minimum cost of traversal from the top-left to the bottom-right corner of a grid right?

Interviewer:
Yes.

Interviewee:
Let me make sure. Is the cost of traversal an integer? And what is the size of this two-dimensional array?

Interviewer:
The cost of traversal is an integer, and you can assume the number of rows and columns in this matrix is m and n.

Interviewee:
OK. Let me give some examples. If I get a two-dimensional array like this:

[1,3,4]
[1,5,6]
[1,2,9] 

And I have to calculate the minimum traversal cost from left-top to right-bottom. It’s obvious that the shortest path is going down to left-bottom then go right to right-bottom. And the traversal cost will be 1+1+1+2+9=14. Is that correct?

Interviewer:
Yes, that’s right. Can you walk me through your approach?

Interviewee:
This problem can be solved using dynamic programming. I will make each element of this two-dimensional array record the minimum traversal cost from left-top to that grid. First, the first row and first column can only be reached from the left or the top, so they will be cumulative sums. And for rest of the elements, since we can only come from above or the left, so the element will be updated like this:

grid[i][j] = grid[i][j] + min(grid[i-1][j], grid[i][j-1]) 

In this way, the traversal cost from left-top to right-bottom will be stored in grid[m-1][n-1].

Interviewer:
Sounds good. Please go ahead and implement the code.

Interviewee:

int minPathSum(int** grid, int m, int* n) { 
    for(int i = 1; i < m; i++) { 
      grid[i][0] += grid[i - 1][0]; 
    } 
    
    for(int i = 1; i < n; i++) { 
      grid[0][i] += grid[0][i - 1]; 
    } 
    
    for(int i = 1; i < m; i++) { 
        for(int j = 1; j < *n; j++) { 
            grid[i][j] += grid[i - 1][j] < grid[i][j - 1] ? grid[i - 1][j] : grid[i][j - 1]; 
        } 
    } 
    
    return grid[m - 1][n - 1]; 
} 

Interviewer:
Your code looks correct. Can you explain the time and space complexity of this approach?

Interviewee:
Sure. The time complexity will be O(m * n), because we iterate through the entire grid. And The space complexity will be O(1), because it’s an in-place algorithm. We only modified the value of the given two-dimensional array. And we only used two variables for the indices. So the space complexity will be O(1).

Interviewer:
Great. That sounds correct. But I have a follow-up question: What if the grid represents the number of cargos, and the task changes to finding the maximum number of cargos the robot can carry. How would you adapt your solution to handle this situation?

Interviewee:
I think I can simply change min into max function. And the result of the maximum number of cargos the robot can carry will be store in grid[m-1][n-1].

Interviewer:
Perfect! That concludes the interview. You did a great job. Good luck with the rest of your interviews!

Interviewee:
Thank you very much! Have a nice day.

162. Find Peak Element

Interviewer:
Hello, I am currently a software engineer in the signal processing department, and I will be responsible for this interview. My name is Ivancough.

Interviewee:
Nice to meet you. My name is Kyle.

Interviewer:
Since this department focuses on signal processing, during the process of signal transmission, if a signal is too strong, it might cause damage to hardware equipment. Therefore, we need to identify the peaks within a series of signals.

The definition of a peak is that the target signal must be strictly greater than its neighbors.

Suppose you receive an array containing signal intensities. I would like you to find the peaks and return their indices. How would you approach this problem?

Interviewee:
OK. So, you would like me to identify the peaks in an array and return their indices. I would like to ask, in the case where there are multiple peaks, such as [1, 5, 2, 4, 1], which peak should I return?

Interviewer:
Both peaks are acceptable. Just make sure the indices of the peaks you return are correct.

Interviewee:
Would there be cases where peaks occur consecutively, such as [1, 2, 4, 4, 1]?

Interviewer:
Yes, but in such cases, you can return the index of any one of the peaks.

Interviewee:
To ensure I understand the problem correctly, let me give an example. If the signal array I receive is [1, 2, 4, 6, 2, 1], since 6 is the peak, I need to return its index, which is 3. Did I understand that correctly?

Interviewer:
You are right.

Interviewee:
My idea is to declare two additional variables to store the neighbors of the target signal and use if-else to check whether the target signal is greater than both neighbors. Then, I would use a for loop to traverse the entire array.

Interviewer:
That approach works, but it might consume more memory. Try to think of an alternative method that can be more memory-efficient.

Interviewee:
Actually, we can compare the target signal with the next signal, like if (nums[i] > nums[i+1]). Doing this ensures that the target signal is greater than the signal on its left because if the left signal was greater, it would have already been returned in the previous loop. So, there’s no need to consider the left signal’s value again.

Interviewer:
Your idea is correct. You can start coding now.

Interviewee:

int findPeakElement(int* nums, int numsSize) {
    for(int i = 0; i < numsSize; i++){
        if(nums[i] > nums[i+1]){
            return i;
        }
    }
    return numsSize-1;
}

The time complexity is O(n). Space complexity is O(1)

Interviewer:
Since the actual length of the signal array can be extremely large, an O(n) time complexity is still too high. Is there a way to achieve a lower time complexity?

Interviewee:
I think we can use the concept of binary search. Set a midpoint to divide the array into two halves, then compare the signal at the midpoint with the signal on its right. If the signal on the right is greater, it indicates that the peak is in the right half of the array, so we set the start point to midpoint + 1. Otherwise, we set the end point to midpoint. Keep repeating this process until the start point and end point meet, and we can determine the index of the peak.

Interviewer:
This is a great idea. You can try coding it.

Interviewee:

int findPeakElement(int* nums, int numsSize) {
    int start=0,end=numsSize-1,mid;
    while(start!=end)
    {
        mid=start+(end-start)/2;
        if(nums[mid]>nums[mid+1])
        {
            end=mid;
        } else{
            start=mid+1;
        }
    }
    return end;
}

Interviewer:
This concludes the interview. HR will follow up with you regarding the next steps. Thank you for your time.

Interviewee:
OK. Thank you very much! Have a nice day.