PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • medium
  • Citadel
  • Coding & Algorithms
  • Software Engineer

Solve four algorithmic problems

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

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.

Input: ('000', 5)

Expected Output: 3

Explanation: Every prefix has zero ones, so we can append 5 ones followed by a zero to create exactly 5 subsequences.

Input: ('111', 2)

Expected Output: 2

Explanation: Prefixes with 1 or 2 ones can reach k = 2; the prefix with 3 ones cannot add a positive amount less than 3.

Input: ('10', 0)

Expected Output: 1

Explanation: Prefix '1' already has 0 "10" subsequences, but prefix '10' already has 1.

Hints

  1. Track, for each prefix, the current number of '1' characters and the current number of "10" subsequences.
  2. 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.

Input: ([1, -2, 3, -4],)

Expected Output: 10

Explanation: Use segments [1], [-2], [3], [-4], giving 1 - (-2) + 3 - (-4) = 10.

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

Expected Output: 6

Explanation: Put the whole array in a positive-sign segment.

Input: ([-5, -1],)

Expected Output: 6

Explanation: Put the whole array in a negative-sign segment, giving -(-6) = 6.

Hints

  1. Rewrite the expression using prefix sums and the three boundary positions.
  2. 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.

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

Expected Output: 5

Explanation: All developers can be chosen.

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

Expected Output: 1

Explanation: Any team of size 2 would give someone a lower- or higher-skilled teammate, which is not allowed.

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

Expected Output: 2

Explanation: A valid team of size 2 exists, but no valid team of size 3 exists.

Hints

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

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

Expected Output: [0, 1, 3]

Explanation: MEX 2 is impossible because the value 2 is stuck, but 0, 1, and 3 are achievable.

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

Expected Output: [0]

Explanation: Value 0 can never be created, so only MEX 0 is achievable.

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

Expected Output: [0, 1]

Explanation: We can achieve MEX 0 by increasing the 0, or MEX 1 by leaving 0 present. Value 1 cannot be created.

Hints

  1. To achieve MEX m, every value 0 through m - 1 must be constructible from distinct elements by only increasing values.
  2. The only value that cannot be moved upward is n - 1, so it creates a special obstruction when trying to make MEX n - 1.
Last updated: Jul 6, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Top-K Largest Elements in Every Sliding Window - Citadel (medium)
  • Find the Index Range of a Target in a Sorted Array - Citadel (medium)
  • Implement a single-producer multi-consumer ring buffer - Citadel (medium)
  • Sort a Nearly Sorted Array - Citadel (hard)
  • Compute BBO and NBBO from order data - Citadel (medium)