Solve four algorithmic problems
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.
Citadel
Sep 6, 2025, 12:00 AM
Software Engineer
Take-home Project
Coding & Algorithms
0
0
Answer the following independent algorithmic questions:
- 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.
- 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
-
- sum(s
-
- sum(s
-
- 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.
- 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|.
- 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.