Quick Overview

This question evaluates algorithm design and combinatorial optimization skills by combining array-partition sum maximization with constrained subset selection, focusing on reasoning about interval sums, feasibility under per-item constraints, and trade-offs in selecting indices or team members.

Solve two DS&A optimization problems

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

Problem 1 — Maximize alternating-sum over four array partitions: Given an integer array arr[1..n] (1-based). Choose indices a, b, c with 1 ≤ a ≤ b ≤ c ≤ n+1. For any half-open interval [l, r), define sum[l, r) as the sum of arr[l..r−1], with sum[l, l) = 0. Cutting at a, b, c partitions the array into four contiguous segments in order: S4 = sum[1, a), S1 = sum[a, b), S2 = sum[b, c), S3 = sum[c, n+ 1). Define grossValue(a, b, c) = S1 − S2 + S3 − S4. Compute the maximum possible grossValue over all valid (a, b, c). State your algorithm and its time/space complexity; handle edge cases where cuts coincide or lie at the ends. Problem 2 — Select largest team under lower/higher‑skill constraints: There are n developers with distinct skill levels 1..n (developer i has skill i). Arrays lowerSkill[1..n] and higherSkill[1..n] are given. A developer i will join the team only if at most lowerSkill[i] chosen teammates have skill lower than i, and at most higherSkill[i] chosen teammates have skill higher than i. Find the maximum possible team size (and optionally one valid team) such that every selected developer’s constraints are satisfied. Describe the algorithm and analyze its complexity.

Quick Answer: This question evaluates algorithm design and combinatorial optimization skills by combining array-partition sum maximization with constrained subset selection, focusing on reasoning about interval sums, feasibility under per-item constraints, and trade-offs in selecting indices or team members.

Part 1: Maximum Alternating Value from Four Array Partitions

Given an integer array arr of length n, choose cut positions i, j, k such that 0 <= i <= j <= k <= n. These cuts split the array into four contiguous half-open segments [0, i), [i, j), [j, k), and [k, n). Let: - A = sum(arr[i:j]) - B = sum(arr[j:k]) - C = sum(arr[k:n]) - D = sum(arr[0:i]) Your score is A - B + C - D. Return the maximum possible score over all valid choices of i, j, and k. Cuts may coincide, so any segment is allowed to be empty.

Constraints

  • 0 <= n <= 2 * 10^5
  • -10^9 <= arr[i] <= 10^9
  • Use 64-bit integer arithmetic in languages other than Python.

Examples

Input: []

Expected Output: 0

Explanation: The array is empty, so the only valid choice is i = j = k = 0 and the score is 0.

Input: [7]

Expected Output: 7

Explanation: Choose i = j = k = 0, so A = 0, B = 0, C = 7, D = 0 and the score is 7.

Hints

  1. Write the score using prefix sums P[x] = sum(arr[0:x]). The expression collapses to a formula involving only P[i], P[j], P[k], and the total sum.
  2. For each middle cut j, you want the best prefix value on the left and the best prefix value on the right. Precompute prefix minima and suffix minima.

Part 2: Largest Valid Developer Team

There are n developers with distinct skill levels 1 through n. The developer with skill s corresponds to index s - 1 in the arrays. You are given two arrays: - lowerSkill[s - 1]: the maximum number of chosen teammates with lower skill than s - higherSkill[s - 1]: the maximum number of chosen teammates with higher skill than s If a team is chosen and listed in increasing skill order, the member at position t (1-indexed) has exactly t - 1 chosen teammates with lower skill and team_size - t chosen teammates with higher skill. A developer joins only if both limits are respected. Return the maximum possible team size.

Constraints

  • 0 <= n <= 2 * 10^5
  • len(lowerSkill) == len(higherSkill) == n
  • 0 <= lowerSkill[i], higherSkill[i] <= n - 1
  • Developer at index i has skill i + 1

Examples

Input: ([], [])

Expected Output: 0

Explanation: There are no developers, so the maximum valid team size is 0.

Input: ([0], [0])

Expected Output: 1

Explanation: The only developer has no lower-skilled or higher-skilled teammates in a team of size 1, so they can be chosen.

Hints

  1. For a fixed target team size m, think about choosing the team from lowest skill to highest skill. If a developer can serve as the next chosen member, greedily taking them is safe.
  2. Feasibility is monotonic: if a team of size m exists, then any smaller size also exists. That suggests binary search on the answer.

Loading coding console...