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.

Q: 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.

Q: What difficulty level is this interview question?

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

Q: What role is this question designed for?

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

Question

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

Comments (0)