Solve four algorithmic problems
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Answer the following independent algorithmic questions:
1) Count extendable prefixes for '10' subsequences: Given a binary string s and an integer k, you may append '0' or '1' to the end any number of times. A non-empty prefix p of s is valid if there exists some sequence of appends to p such that the total number of subsequences equal to "10" in the resulting string is exactly k. Here a "10" subsequence is a pair of indices (i, j) with i < j, s[i] = '1', and s[j] = '0'. Return the number of valid non-empty prefixes of s.
2) Maximize alternating four-segment sum: Given an integer array a[1..n], choose three cut indices 1 ≤ i1 ≤ i2 ≤ i3 ≤ n+1 to form four contiguous (possibly empty) segments s1 = a[1..i1-1], s2 = a[i1..i2-1], s3 = a[i2..i3-1], s4 = a[i3..n]. Define value = sum(s
1) - sum(s
2) + sum(s
3) - sum(s
4). Cuts may coincide and may be at the array ends. Compute the maximum possible value. You may assume n ≤ 3·10^3.
3) Select the largest agreeable developer team: There are n developers with skill i for 1 ≤ i ≤ n. Given arrays lowerSkill[1..n] and higherSkill[1..n], choose the largest subset T such that for every i ∈ T, at most lowerSkill[i] members of T have skill less than i and at most higherSkill[i] members of T have skill greater than i. Return |T|.
4) Find all achievable MEX values with bounded increments: You have n memory blocks memoryBlocks[0..n-1]. You may repeatedly choose an index x and increase memoryBlocks[x] by 1 only while memoryBlocks[x] < n - 1. After any number of operations, the MEX of the array is the smallest non-negative integer absent from it. Return all distinct MEX values that are achievable, in ascending order.
Quick Answer: This multi-part question evaluates algorithmic problem-solving skills across combinatorics and subsequence counting, array partitioning with prefix-sum or dynamic programming optimization, constrained subset selection and feasibility reasoning, and reachable-state/MEX analysis under bounded operations, alongside complexity analysis and efficient algorithm design. It is commonly asked in Coding & Algorithms interviews because it probes reasoning about constructive sequence operations, optimization under constraints, and achievable-state characterization while balancing time and space complexity, and it tests both conceptual understanding and practical application.
Part 1: Count Extendable Prefixes for '10' Subsequences
Given a binary string s and a non-negative integer k, consider each non-empty prefix p of s. You may append any number of characters, each either '0' or '1', to the end of p. A prefix is valid if there exists some sequence of appends such that the final string contains exactly k subsequences equal to "10". A "10" subsequence is a pair of indices (i, j) with i < j, string[i] = '1', and string[j] = '0'. Return the number of valid non-empty prefixes of s.
Constraints
- 0 <= len(s) <= 200000
- s contains only characters '0' and '1'
- 0 <= k <= 10^18
Examples
Input: ('', 0)
Expected Output: 0
Explanation: There are no non-empty prefixes.
Input: ('1010', 2)
Expected Output: 2
Explanation: Prefixes '1' and '10' can be extended to have exactly 2 "10" subsequences.
Hints
- Track, for each prefix, the current number of '1' characters and the current number of "10" subsequences.
- Appending a '0' adds exactly the current number of ones to the "10" count; appending '1's first lets you choose any larger contribution.
Part 2: Maximize Alternating Four-Segment Sum
Given an integer array a, choose three cut positions that split the array into four contiguous, possibly empty segments s1, s2, s3, and s4. The cuts may coincide and may be placed before the first element or after the last element. The value of a split is sum(s1) - sum(s2) + sum(s3) - sum(s4). Return the maximum possible value.
Constraints
- 0 <= len(a) <= 3000
- -10^9 <= a[i] <= 10^9
- Segments may be empty
Examples
Input: ([],)
Expected Output: 0
Explanation: The only split has four empty segments.
Input: ([-7],)
Expected Output: 7
Explanation: Place the single element in a negative-sign segment, giving -(-7) = 7.
Hints
- Rewrite the expression using prefix sums and the three boundary positions.
- If P[x] is a prefix sum, the value can be written as 2 * (P[i1] - P[i2] + P[i3]) - total_sum.
Part 3: Select the Largest Agreeable Developer Team
There are n developers with distinct skills 1 through n. Developer i has skill i. You are given arrays lowerSkill and higherSkill, where lowerSkill[i - 1] is the maximum number of chosen team members with skill less than i that developer i can accept, and higherSkill[i - 1] is the maximum number of chosen team members with skill greater than i that developer i can accept. Choose the largest subset T such that every chosen developer's limits are satisfied. Return the maximum possible size of T.
Constraints
- 0 <= n <= 200000
- len(lowerSkill) == len(higherSkill) == n
- 0 <= lowerSkill[i] <= n
- 0 <= higherSkill[i] <= n
- Developer skills are ordered by array index: developer i has skill i + 1
Examples
Input: ([], [])
Expected Output: 0
Explanation: There are no developers.
Input: ([0], [0])
Expected Output: 1
Explanation: A single developer has no lower- or higher-skilled teammates.
Hints
- For a proposed team size m, the j-th selected developer in increasing skill order has exactly j lower-skilled teammates and m - 1 - j higher-skilled teammates.
- Check whether size m is feasible greedily from low skill to high skill, then binary search the answer.
Part 4: Find All Achievable MEX Values with Bounded Increments
You are given an array memoryBlocks of length n. In one operation, you may choose an index x and increase memoryBlocks[x] by 1, but only while memoryBlocks[x] < n - 1. Thus values can be increased, but no value can be increased beyond n - 1. After any number of operations, including zero operations, compute the MEX of the resulting array. The MEX is the smallest non-negative integer absent from the array. Return all distinct MEX values that are achievable, in ascending order.
Constraints
- 0 <= n <= 200000
- If n > 0, 0 <= memoryBlocks[i] <= n - 1
- Operations may be performed any number of times, including zero
Examples
Input: ([],)
Expected Output: [0]
Explanation: The empty array has MEX 0.
Input: ([0],)
Expected Output: [1]
Explanation: The only value is already 0 and cannot be increased, so the only MEX is 1.
Hints
- To achieve MEX m, every value 0 through m - 1 must be constructible from distinct elements by only increasing values.
- The only value that cannot be moved upward is n - 1, so it creates a special obstruction when trying to make MEX n - 1.