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 Citadel.

What role is this question designed for?

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

Solve two DS&A optimization problems | Citadel Coding Question

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.

Input: [1, 2, 3]

Expected Output: 6

Explanation: Choose i = j = k = 0, so the whole array is in the final positive segment: 0 - 0 + 6 - 0 = 6.

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

Expected Output: 14

Explanation: One optimal choice is i = 0, j = 1, k = 3. Then A = 4, B = -5, C = 5, D = 0, so the score is 4 - (-5) + 5 - 0 = 14.

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

Expected Output: 6

Explanation: Choose i = j = k = 3. Then A = B = C = 0 and D = -6, so the score is 0 - 0 + 0 - (-6) = 6.

Solution

def solution(arr):
    n = len(arr)

    prefix = [0] * (n + 1)
    for idx, value in enumerate(arr, 1):
        prefix[idx] = prefix[idx - 1] + value

    pref_min = [0] * (n + 1)
    pref_min[0] = prefix[0]
    for i in range(1, n + 1):
        pref_min[i] = min(pref_min[i - 1], prefix[i])

    suff_min = [0] * (n + 1)
    suff_min[n] = prefix[n]
    for i in range(n - 1, -1, -1):
        suff_min[i] = min(prefix[i], suff_min[i + 1])

    total = prefix[n]
    best = -10**30

    for j in range(n + 1):
        # score = total + 2 * prefix[j] - 2 * prefix[i] - 2 * prefix[k]
        # For fixed j, choose the minimum prefix[i] for i <= j
        # and the minimum prefix[k] for k >= j.
        score = total + 2 * prefix[j] - 2 * pref_min[j] - 2 * suff_min[j]
        if score > best:
            best = score

    return best

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

Hints

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.
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.

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

Expected Output: 4

Explanation: All four developers can be selected in increasing skill order, and each one exactly matches the required counts.

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

Expected Output: 1

Explanation: Any single developer works, but no pair works because one member would need to tolerate one lower-skilled teammate and another would need to tolerate one higher-skilled teammate.

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

Expected Output: 3

Explanation: A valid team is formed by skills 1, 3, and 5. No team of size 4 satisfies all constraints.

Solution

def solution(data):
    lowerSkill, higherSkill = data
    n = len(lowerSkill)

    def feasible(m):
        if m == 0:
            return True

        chosen = 0
        for i in range(n):
            # If developer i + 1 becomes the next selected member,
            # they would have 'chosen' lower-skilled teammates and
            # 'm - 1 - chosen' higher-skilled teammates.
            if lowerSkill[i] >= chosen and higherSkill[i] >= m - 1 - chosen:
                chosen += 1
                if chosen == m:
                    return True
        return False

    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if feasible(mid):
            lo = mid
        else:
            hi = mid - 1

    return lo

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

Hints

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.
Feasibility is monotonic: if a team of size m exists, then any smaller size also exists. That suggests binary search on the answer.

Quick Overview