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 Technical Screen rounds at Anthropic.

What role is this question designed for?

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

Solve programming task with follow-ups | Anthropic Coding Question

Solve programming task with follow-ups

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question Pure programming problem solving: implement the core algorithmic solution, then extend it to ( 1) support a constraint of consecutive N elements and ( 2) an optimization that uses only suffix-related information.

Quick Answer: This question evaluates algorithmic problem-solving skills, including core algorithm implementation, handling a consecutive-N-element constraint, and designing an optimization that leverages suffix-related information.

Part 1: Maximum Contiguous Subarray Sum

Given an integer array nums, return the maximum possible sum of any non-empty contiguous subarray. If nums is empty, return 0.

Constraints

0 <= len(nums) <= 200000
-10^9 <= nums[i] <= 10^9

Examples

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

Expected Output: 6

Explanation: The best contiguous subarray is [4, -1, 2, 1], which sums to 6.

Input: ([1],)

Expected Output: 1

Explanation: A single element array has only one non-empty contiguous subarray.

Input: ([-5, -2, -7],)

Expected Output: -2

Explanation: When all numbers are negative, the answer is the largest single element.

Input: ([],)

Expected Output: 0

Explanation: By definition for this problem, an empty list returns 0.

Input: ([5, -1, 5],)

Expected Output: 9

Explanation: The entire array is the maximum-sum contiguous subarray.

Solution

def solution(nums):
    if not nums:
        return 0

    current = best = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best

Time complexity: O(n). Space complexity: O(1).

Hints

Track the best sum of a subarray that must end at the current index.
If extending the current subarray is worse than starting fresh at nums[i], start a new subarray there.

Part 2: Maximum Sum of Exactly N Consecutive Elements

Given an integer array nums and an integer k, return the maximum sum of any contiguous subarray of length exactly k. If k is invalid (k < 1 or k > len(nums)), return None.

Constraints

0 <= len(nums) <= 200000
0 <= k <= 200000
-10^9 <= nums[i] <= 10^9

Examples

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

Expected Output: 9

Explanation: The best window of length 2 is [4, 5].

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

Expected Output: 6

Explanation: The only valid window is the entire array.

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

Expected Output: -2

Explanation: With k = 1, choose the largest single element.

Input: ([2, 1], 3)

Expected Output: None

Explanation: No contiguous subarray of length 3 exists in an array of length 2.

Input: ([7], 1)

Expected Output: 7

Explanation: Single-element arrays work when k is 1.

Solution

def solution(nums, k):
    n = len(nums)
    if k < 1 or k > n:
        return None

    window_sum = sum(nums[:k])
    best = window_sum

    for i in range(k, n):
        window_sum += nums[i] - nums[i - k]
        if window_sum > best:
            best = window_sum

    return best

Time complexity: O(n). Space complexity: O(1).

Hints

First compute the sum of the first window of size k.
When moving the window by one step, subtract the outgoing element and add the incoming element.

Part 3: Maximum Total of Two Non-Overlapping Subarrays Using Suffix Bests

Given an integer array nums, choose two non-overlapping, non-empty contiguous subarrays so that their total sum is as large as possible. Return that maximum total. If fewer than 2 elements are provided, return None. A brute-force approach is too slow; solve it in O(n) by precomputing the best subarray sum available in each suffix.

Constraints

0 <= len(nums) <= 200000
-10^9 <= nums[i] <= 10^9

Examples

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

Expected Output: 7

Explanation: One optimal choice is [1, 3] and [2, -1, 2], for a total of 4 + 3 = 7.

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

Expected Output: -3

Explanation: The best choice is two single-element subarrays: [-1] and [-2].

Input: ([5, -1, 5],)

Expected Output: 10

Explanation: Choose the first [5] and the last [5].

Input: ([8, -1],)

Expected Output: 7

Explanation: With only two elements, the only valid answer uses both as separate subarrays.

Input: ([1],)

Expected Output: None

Explanation: It is impossible to form two non-overlapping non-empty subarrays from one element.

Solution

def solution(nums):
    n = len(nums)
    if n < 2:
        return None

    suffix_best = [0] * n
    current = nums[-1]
    suffix_best[-1] = current

    for i in range(n - 2, -1, -1):
        current = max(nums[i], nums[i] + current)
        suffix_best[i] = max(suffix_best[i + 1], current)

    left_end = nums[0]
    left_best = nums[0]
    answer = left_best + suffix_best[1]

    for i in range(1, n - 1):
        left_end = max(nums[i], left_end + nums[i])
        left_best = max(left_best, left_end)
        answer = max(answer, left_best + suffix_best[i + 1])

    return answer

Time complexity: O(n). Space complexity: O(n).

Hints

Imagine splitting the array between i and i + 1. You need the best subarray on the left side and the best subarray on the right side.
Precompute, for every index, the best subarray sum contained entirely in the suffix starting there.

Quick Overview

This question evaluates algorithmic problem-solving skills, including core algorithm implementation, handling a consecutive-N-element constraint, and designing an optimization that leverages suffix-related information.