How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Take-home Project 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.

Solve OA tasks on string, grid path, subarrays

Quick Overview

This multi-part question evaluates string manipulation, constrained grid-path optimization with sequential expression evaluation, and counting of parity-alternating subarrays, measuring competencies in algorithm design, dynamic programming or combinatorial path reasoning, and linear-time array techniques.

Company: Capital One

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Take-home Project

You are given three independent coding tasks. ## Task 1: Reverse the middle if ends are vowels Given a string `s` (ASCII letters), if **both** the first and last characters are vowels (`a,e,i,o,u` case-insensitive), return a new string where: - the first and last characters stay in place, and - the substring strictly between them is reversed. Otherwise, return `s` unchanged. **Examples** - `"apple"` → first=`a` (vowel), last=`e` (vowel) ⇒ reverse middle `"ppl"` → `"alppe"` - `"code"` → first=`c` not vowel ⇒ `"code"` **Edge cases** - If `len(s) <= 2`, there is no “middle”; return `s`. --- ## Task 2: Maximize value along a constrained grid path You are given an `m x n` grid of characters. Each cell contains either: - a digit `'0'..'9'`, or - an operator `'+'` or `'-'`. You start at the **top-left** cell `(0,0)` and must reach the **bottom-right** cell `(m-1,n-1)` by moving only: - **right**, or - **down**. As you traverse cells, you concatenate their characters to form an arithmetic expression, which is evaluated **left-to-right** (i.e., no operator precedence beyond sequential evaluation). **Validity assumption:** Any path considered must form a valid expression of the form `digit (op digit)*` (alternating digit/operator), and it must start and end with a digit. **Direction-change constraint:** Along the path, you are allowed to change direction **at most once** (i.e., the move sequence is either all rights then all downs, or all downs then all rights). **Goal:** Return the **maximum** value achievable among all valid paths satisfying the movement constraint. --- ## Task 3: Count alternating odd/even subarrays Given an integer array `nums`, count how many **contiguous subarrays** have strictly alternating parity (odd/even/odd/even... or even/odd/even/odd...). A subarray of length 1 always counts. **Example** - `nums = [1, 2, 4]` - Alternating subarrays: `[1]`, `[2]`, `[4]`, `[1,2]`, but `[2,4]` is not alternating (even, even), and `[1,2,4]` is not alternating. - Answer = `4` **Performance requirement:** Design an algorithm faster than brute force (e.g., `O(n)`).

Quick Answer: This multi-part question evaluates string manipulation, constrained grid-path optimization with sequential expression evaluation, and counting of parity-alternating subarrays, measuring competencies in algorithm design, dynamic programming or combinatorial path reasoning, and linear-time array techniques.

Part 1: Reverse the Middle When Both Ends Are Vowels

Given a string s consisting of ASCII letters, check whether both its first and last characters are vowels: a, e, i, o, u, case-insensitive. If they are, return a new string where the first and last characters stay fixed and the substring strictly between them is reversed. Otherwise, return s unchanged. If len(s) <= 2, there is no middle substring to reverse, so return s unchanged.

Constraints

0 <= len(s) <= 100000
s contains only ASCII letters when non-empty
Vowels are a, e, i, o, u, matched case-insensitively

Examples

Input: ("apple",)

Expected Output: "alppe"

Explanation: Both endpoints are vowels: a and e. Reverse the middle substring 'ppl' to get 'lpp'.

Input: ("code",)

Expected Output: "code"

Explanation: The first character c is not a vowel, so the string is unchanged.

Input: ("Aa",)

Expected Output: "Aa"

Explanation: The endpoints are vowels, but the length is 2, so there is no middle substring.

Input: ("",)

Expected Output: ""

Explanation: The empty string is an edge case and is returned unchanged.

Input: ("Abca",)

Expected Output: "Acba"

Explanation: A and a are vowels. Reverse the middle substring 'bc' to get 'cb'.

Hints

Handle strings of length 0, 1, or 2 before accessing the first or last character.
Use lowercase conversion for the endpoint vowel check, then use slicing to reverse the middle.

Part 2: Maximize Expression Value Along a One-Turn Grid Path

You are given an m x n grid represented as a list of equal-length strings. Each cell contains either a digit '0'..'9' or an operator '+' or '-'. You start at the top-left cell and must reach the bottom-right cell by moving only right or down. Along the path, concatenate the visited characters to form an arithmetic expression. A valid expression must have the form digit (operator digit)*, so it must start and end with a digit and alternate between digits and operators. Expressions are evaluated left-to-right. You may change direction at most once, so the complete route must be either all rights followed by all downs, or all downs followed by all rights. Ignore any candidate route that does not form a valid expression. Return the maximum value among valid candidate routes. The input is guaranteed to have at least one valid candidate route.

Constraints

1 <= len(grid) <= 200000
1 <= len(grid[0]) <= 200000
All rows have the same length
The total number of cells len(grid) * len(grid[0]) is at most 200000
Each grid cell is a digit '0'..'9' or one of '+' and '-'
At least one of the two candidate route shapes forms a valid expression

Examples

Input: (["7"],)

Expected Output: 7

Explanation: The single cell is already a valid expression with value 7.

Input: (["1+", "-2"],)

Expected Output: 3

Explanation: Right-then-down gives '1+2' = 3. Down-then-right gives '1-2' = -1.

Input: (["1+2-3"],)

Expected Output: 0

Explanation: There is only one row, so the only path forms '1+2-3', which evaluates to 0.

Input: (["8-3", "+0+", "2-5"],)

Expected Output: 10

Explanation: Right-right-down-down gives '8-3+5' = 10. Down-down-right-right gives '8+2-5' = 5.

Input: (["1+2", "-06", "4+5"],)

Expected Output: 2

Explanation: The right-then-down route forms '1+265', which is invalid because digits are adjacent. The down-then-right route forms '1-4+5' = 2.

Hints

With at most one direction change, there are only two possible complete route shapes from top-left to bottom-right.
While evaluating a path string, keep the current value, the pending operator, and whether the next character must be a digit or an operator.

Part 3: Count Alternating Odd-Even Subarrays

Given an integer array nums, count how many contiguous subarrays have strictly alternating parity. A subarray is alternating if every pair of adjacent elements inside it has different parity. Subarrays of length 1 always count.

Constraints

0 <= len(nums) <= 200000
-1000000000 <= nums[i] <= 1000000000
The answer may be larger than 32-bit integer range

Examples

Input: ([1, 2, 4],)

Expected Output: 4

Explanation: The alternating subarrays are [1], [2], [4], and [1, 2].

Input: ([],)

Expected Output: 0

Explanation: There are no subarrays in an empty array.

Input: ([7],)

Expected Output: 1

Explanation: A single-element subarray always counts.

Input: ([1, 2, 3, 4],)

Expected Output: 10

Explanation: The entire array alternates, so every one of the 4 * 5 / 2 subarrays counts.

Input: ([2, 4, 6],)

Expected Output: 3

Explanation: Only the three single-element subarrays count because all adjacent pairs have the same parity.

Hints

For each index, count how many alternating subarrays end at that index.
If nums[i] and nums[i - 1] have different parity, extend the previous alternating suffix; otherwise, restart with length 1.

Quick Overview