How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during HR Screen rounds at Capital One.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Capital One during technical interviews.

Maximize grid-path expression and count sawtooth subarrays

Q: Maximize grid-path expression and count sawtooth subarrays

This multi-part question evaluates dynamic programming and state management for constrained grid traversal with left-to-right expression evaluation, alongside parity-based array analysis and combinatorial counting of contiguous subarrays.

Problem 1: Maximize a valid expression along a grid path

You are given an m x n grid grid. Each cell contains either:

an operator: '+' or '-' , or
a single digit character '0' … '9' .

You start at the top-left cell (0,0) and must reach the bottom-right cell (m-1,n-1) by moving only:

right (r, c) -> (r, c+1) , or
down (r, c) -> (r+1, c) .

As you traverse a path, you concatenate the visited cells (in order) to form an expression.

An expression is valid if it alternates strictly between numbers and operators:

It must start with a digit.
It must then alternate: digit, operator, digit, operator, digit, ...
It must end with a digit.
Therefore, it may not contain:
- two consecutive operators (e.g., 0 ++ 1 , 3 +- 4 ), or
- two consecutive digits (e.g., 1 2 + 3 , 5 - 6 3 ).

Evaluation rule: Evaluate the expression strictly left-to-right (since only + and - are present).

Task

Return the maximum possible evaluated value among all valid paths from (0,0) to (m-1,n-1).

Assumptions / constraints (for clarity)

1 <= m, n <= 50
grid[r][c] is one of {'+','-','0'..'9'}
If no valid path exists, return an agreed sentinel (e.g., null / None / -inf ) as specified by the interviewer.

Problem 2: Count sawtooth (alternating parity) subarrays

A sawtooth sequence is a sequence of integers where adjacent elements have different parity (even/odd), i.e., it alternates between even and odd.

Given an integer array arr, count the number of contiguous subarrays that are sawtooth sequences.

Subarrays of length 1 count as sawtooth by definition.

Examples

arr = [1, 3, 5, 7, 9] → output 5 (only the 5 single-element subarrays).
arr = [1, 2, 1, 2, 1] → output 15 (all subarrays alternate parity).
arr = [1, 2, 3, 7, 6, 5] → output 12 .

Constraints (for clarity)

1 <= len(arr) <= 2 * 10^5
|arr[i]| <= 10^9

Task

Return the total number of contiguous sawtooth subarrays.

Problem 1: Maximize a valid expression along a grid path

You are given an m x n grid grid. Each cell contains either:

an operator: '+' or '-' , or
a single digit character '0' … '9' .

You start at the top-left cell (0,0) and must reach the bottom-right cell (m-1,n-1) by moving only:

right (r, c) -> (r, c+1) , or
down (r, c) -> (r+1, c) .

As you traverse a path, you concatenate the visited cells (in order) to form an expression.

An expression is valid if it alternates strictly between numbers and operators:

It must start with a digit.
It must then alternate: digit, operator, digit, operator, digit, ...
It must end with a digit.
Therefore, it may not contain:
- two consecutive operators (e.g., 0 ++ 1 , 3 +- 4 ), or
- two consecutive digits (e.g., 1 2 + 3 , 5 - 6 3 ).

Evaluation rule: Evaluate the expression strictly left-to-right (since only + and - are present).

Task

Return the maximum possible evaluated value among all valid paths from (0,0) to (m-1,n-1).

Assumptions / constraints (for clarity)

1 <= m, n <= 50
grid[r][c] is one of {'+','-','0'..'9'}
If no valid path exists, return an agreed sentinel (e.g., null / None / -inf ) as specified by the interviewer.

Problem 2: Count sawtooth (alternating parity) subarrays

A sawtooth sequence is a sequence of integers where adjacent elements have different parity (even/odd), i.e., it alternates between even and odd.

Given an integer array arr, count the number of contiguous subarrays that are sawtooth sequences.

Subarrays of length 1 count as sawtooth by definition.

Examples

arr = [1, 3, 5, 7, 9] → output 5 (only the 5 single-element subarrays).
arr = [1, 2, 1, 2, 1] → output 15 (all subarrays alternate parity).
arr = [1, 2, 3, 7, 6, 5] → output 12 .

Constraints (for clarity)

1 <= len(arr) <= 2 * 10^5
|arr[i]| <= 10^9

Task

Return the total number of contiguous sawtooth subarrays.

Maximize grid-path expression and count sawtooth subarrays

Quick Overview

Problem 1: Maximize a valid expression along a grid path

Task

Assumptions / constraints (for clarity)

Problem 2: Count sawtooth (alternating parity) subarrays

Examples

Constraints (for clarity)

Task

Submit Your Answer to Earn 20XP

Maximize grid-path expression and count sawtooth subarrays

Quick Overview

Problem 1: Maximize a valid expression along a grid path

Task

Assumptions / constraints (for clarity)

Problem 2: Count sawtooth (alternating parity) subarrays

Examples

Constraints (for clarity)

Task

Submit Your Answer to Earn 20XP