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 Take-home Project rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Find max consecutive elements with sum below target

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given: - An integer array `nums` of length `n`, sorted in non-decreasing order. - An integer `index` such that `0 ≤ index < n`. - An integer `target`. Starting from position `index`, you may take a contiguous sequence of elements going to the right: `nums[index], nums[index + 1], ..., nums[index + k - 1]` for some integer `k ≥ 0`. You want the sum of the chosen elements to be **strictly less than** `target`: \[ \sum_{i=index}^{index + k - 1} nums[i] < target. \] Find the **maximum possible value of `k`** (the maximum number of consecutive elements starting from `index` whose sum is `< target`). If even `nums[index] ≥ target`, then the answer should be `0`. Design an efficient algorithm to compute this maximum `k`. You may assume: - `1 ≤ n` - `nums` is sorted in non-decreasing order. Describe the algorithm you would implement and its time and space complexity.

Quick Answer: This question evaluates algorithmic problem-solving with arrays, including reasoning about contiguous subsequences, handling sorted inputs and edge cases, and analyzing time and space complexity.

You are given an integer array `nums` of length `n`, sorted in non-decreasing order, an integer `index` with `0 <= index < n`, and an integer `target`. Starting from position `index`, you may take a contiguous run of elements going to the right: `nums[index], nums[index+1], ..., nums[index+k-1]` for some integer `k >= 0`. You want the sum of the chosen elements to be **strictly less than** `target`: nums[index] + nums[index+1] + ... + nums[index+k-1] < target Return the **maximum possible value of `k`** (the maximum number of consecutive elements starting from `index` whose running sum stays strictly below `target`). If even `nums[index] >= target`, return `0`. Note: because the array may contain negative or zero values, you cannot simply stop at the first element that is large; walk the prefix sum and count how many elements you can include before the running sum reaches `target`. **Example:** `nums = [1, 2, 3, 4, 5]`, `index = 0`, `target = 7`. Running sums are 1, 3, 6, 10. The first three (1+2+3=6) stay below 7, but adding 4 gives 10 >= 7, so the answer is `3`.

Constraints

1 <= n (n = len(nums))
nums is sorted in non-decreasing order
0 <= index < n
nums may contain negative, zero, or positive integers
The chosen run is contiguous and starts exactly at index, extending to the right
The sum must be STRICTLY less than target (sum == target does not count)

Examples

Input: ([1, 2, 3, 4, 5], 0, 7)

Expected Output: 3

Explanation: Running sums 1, 3, 6 are < 7; adding 4 gives 10 >= 7, so k = 3.

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

Expected Output: 3

Explanation: From index 2: 3, 7, 12 all < 100 and the array ends, so all 3 remaining elements are taken; k = 3.

Input: ([5, 6, 7], 0, 5)

Expected Output: 0

Explanation: nums[0] = 5 is not < 5, so even the first element cannot be included; k = 0.

Input: ([1, 1, 1, 1], 0, 3)

Expected Output: 2

Explanation: Sums 1, 2 are < 3; the third sum 3 is not < 3, so k = 2 (ties handled correctly).

Input: ([10], 0, 5)

Expected Output: 0

Explanation: Single element 10 >= 5, so k = 0.

Input: ([2], 0, 5)

Expected Output: 1

Explanation: Single element 2 < 5, so the whole array is taken; k = 1.

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

Expected Output: 4

Explanation: Running sums -3, -4, -4, -2 are all < 1; adding 4 gives 2 >= 1, so k = 4. Negative values mean you cannot stop early on the first large element.

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

Expected Output: 0

Explanation: From index 2: nums[2] = 3 is not < 3 (strict comparison), so k = 0.

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

Expected Output: 1

Explanation: From index 2: 3 < 4, then the array ends; k = 1.

Hints

Walk forward from `index`, maintaining a running sum. Increment a counter each time the running sum is still strictly below target.
Stop the moment the running sum reaches or exceeds target — adding more elements can never reduce it back below target only if all values are non-negative, but since the array is sorted non-decreasing, once you stop you are done.
Edge case: if `nums[index] >= target` the loop stops before incrementing the counter, so the answer is 0.
Because the array is sorted, you could also binary-search the prefix-sum array for the first prefix that reaches target, giving O(log n) after an O(n) prefix-sum precompute — but the simple linear scan is already optimal at O(k).

Quick Overview

This question evaluates algorithmic problem-solving with arrays, including reasoning about contiguous subsequences, handling sorted inputs and edge cases, and analyzing time and space complexity.