Solve two DS&A optimization problems

Q: Solve two DS&A optimization problems

This is a Coding & Algorithms interview question from Citadel for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Solve two DS&A optimization problems

Comments (0)