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 medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

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

Compute sum over consecutive-step subarrays

Q: Compute sum over consecutive-step subarrays

This question evaluates proficiency in array processing, detection of consecutive-step arithmetic sequences, and accumulation of subarray sums with attention to large-integer (64-bit) arithmetic.

Company: Google

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given an integer array `a` of length `n`, call a subarray `a[l..r]` **good** if either: - it is strictly increasing by 1 at every step: `a[i+1] - a[i] = 1` for all `i in [l, r-1]`, **or** - it is strictly decreasing by 1 at every step: `a[i+1] - a[i] = -1` for all `i in [l, r-1]`. (All length-1 subarrays are good.) Define the value of a subarray as the **sum of its elements**. Return the **sum of values of all good subarrays**. ### Requirements - Time complexity: **O(n)** - Use 64-bit integer arithmetic for the result. ### Example Input: `a = [3, 5, 6, 7, 6]` Good subarrays are: - `[3]`, `[5]`, `[6]`, `[7]`, `[6]` - `[5, 6]`, `[6, 7]`, `[5, 6, 7]`, `[7, 6]` Output: `82` ### Constraints (you may assume) - `1 <= n <= 2 * 10^5` - `|a[i]| <= 10^9`

Quick Answer: This question evaluates proficiency in array processing, detection of consecutive-step arithmetic sequences, and accumulation of subarray sums with attention to large-integer (64-bit) arithmetic.

Given an integer array a, call a subarray a[l..r] good if it is contiguous and either every adjacent difference inside it is +1, or every adjacent difference inside it is -1. All length-1 subarrays are good. The value of a subarray is the sum of its elements. Return the sum of values of all good subarrays. The result should be computed using 64-bit integer arithmetic.

Constraints

1 <= n <= 2 * 10^5
-10^9 <= a[i] <= 10^9
Your algorithm must run in O(n) time
Use 64-bit integer arithmetic for the answer

Examples

Input: []

Expected Output: 0

Explanation: There are no subarrays in an empty array.

Input: [7]

Expected Output: 7

Explanation: The only good subarray is [7], whose value is 7.

Input: [20, 21]

Expected Output: 82

Explanation: Good subarrays are [20], [21], and [20, 21] with values 20, 21, and 41. Total = 82.

Input: [1, 2, 1]

Expected Output: 10

Explanation: Good subarrays are [1], [2], [1], [1,2], and [2,1]. Their values sum to 1 + 2 + 1 + 3 + 3 = 10.

Input: [-2, -1, 0, -1]

Expected Output: -12

Explanation: Good subarrays are the 4 singletons, plus [-2,-1], [-1,0], [-2,-1,0], and [0,-1]. Their values sum to -12.

Input: [1, 2, 2, 1]

Expected Output: 12

Explanation: The equal pair [2,2] breaks both patterns. Good subarrays are the 4 singletons, [1,2], and [2,1]. Total = 12.

Input: [2, 3, 4, 5, 4, 3]

Expected Output: 105

Explanation: There is an increasing run [2,3,4,5] and a decreasing run [5,4,3]. Summing all good subarrays across these runs gives 105.

Hints

Instead of enumerating all subarrays, count only the good subarrays that end at each index.
Maintain two DP states: one for subarrays ending at i with step +1, and one for step -1. If the current difference matches, extend every previous subarray in that state.

Quick Overview

This question evaluates proficiency in array processing, detection of consecutive-step arithmetic sequences, and accumulation of subarray sums with attention to large-integer (64-bit) arithmetic.