A recruiter reached out to me after coming across my profile, and I showed interest.

After a quick call with them, they scheduled a 1-hour technical phone interview with an engineer.

They usually determine a suitable role for you after all interviews, identifying which skills you are strong at and your interest in different projects.

I did not make it to the onsite interview, but the phone call experience was good, and it felt like they were moving fast without any delays.

Task Description

Diamond Mine is your new favorite game. Its map is represented as a square matrix. The board is filled with cells, and each cell will have an initial value as follows:

• A value ≥ 0 represents a path.
• A value of 1 represents a diamond.
• A value of −1 represents an obstruction.

The basic rules for playing Diamond Mine are as follows:

• The player starts at (0, 0) and moves to (n−1, n−1) by moving right (→) or down (↓) through valid path cells.
• After reaching (n−1, n−1), the player must travel back to (0, 0) by moving left (←) or up (↑) through valid path cells.
• When passing through a path cell containing a diamond, the diamond is picked up. Once picked up, the cell becomes an empty path cell.
• If there is no valid path between (0, 0) and (n−1, n−1), then no diamonds can be collected.
• The ultimate goal is to collect as many diamonds as you can.

For example, consider the following grid:

0 1 -1 0

Start at the top left corner. Move right one, collecting a diamond. Move down one to the goal. Cell (1, 0) is blocked, so we can only return on the path we took initially. All paths have been explored, and 1 diamond was collected.

Function Description

Complete the function collectMax in the editor below. It must return an integer denoting the maximum number of diamonds you can collect given the current map.

collectMax has the following parameter(s):

• mat[mat[0],...mat[n-1]]: an array of integers describing the game grid map

Constraints

• 1 ≤ n ≤ 100
• −1 ≤ mat[i][j] ≤ 1

Input Format for Custom Testing

Sample Case 0 Sample Input 0 3 3 0 1 -1 1 0 -1 1 1 1

Sample Output 0 5

Explanation 0 You can collect a maximum of 5 diamonds by taking the following path: (0, 0) → (0,1) → (1,1) → (2, 1) → (2, 2) → (2, 1) → (2, 0) → (1, 0) → (0, 0)

Sample Case 1 Sample Input 1 3 3 0 1 1 1 0 1 1 1 1

Sample Output 1 7

You can collect all 7 diamonds by following the path:

0 1 1 ↑ ↓ 1 0 1 ↑ ↓ 1 ← 1 ← 1

Sample Case 2 Sample Input 2 3 3 0 1 1 1 0 -1 1 1 -1

Sample Output 2 0

Explanation 2 The cell at (2, 2) is blocked, so you cannot collect any diamonds.