Started with brief introduction and then follow by this dsa ques

Problem: Maximum Coins in a Grid and Number of Optimal Paths

You are given an N × M grid, where each cell contains a non-negative number of coins. You start at the top-left cell (0, 0) and must reach the bottom-right cell (N-1, M-1).

From any cell, you can move only right or down. Whenever you visit a cell, you collect all the coins present in it, including the starting and destination cells.

Your task is to:

1. Find the maximum number of coins you can collect on any valid path from the start to the destination.
2. Count the number of distinct paths that achieve this maximum number of coins. Two paths are considered distinct if their sequences of moves differ.

Follow-up: Space Optimization

Can you optimize the space complexity of your solution while maintaining the same time complexity?

Constraints:

• 1 ≤ N, M ≤ 1000
• 0 ≤ grid[i][j] ≤ 10^6 Example:

Input: 3 3 1 2 3 4 5 1 2 2 6

Output: Maximum coins: 17 Number of optimal paths: 1

Expected Complexity:

• Initial solution: O(N × M) time and O(N × M) auxiliary space.
• Space-optimized solution: O(N × M) time and O(M) auxiliary space, excluding the input grid after then he asked about my project overview and why i used that particular tech stack and then i was asked about amazon leadership principle questions