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.

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.

Hints

  1. Track the best sum of a subarray that must end at the current index.
  2. 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.

Hints

  1. First compute the sum of the first window of size k.
  2. 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].

Hints

  1. 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.
  2. Precompute, for every index, the best subarray sum contained entirely in the suffix starting there.

Loading coding console...