I wrote up my Citadel interview experience around this time last year too, and it was pretty easy back then. This time I got the OA invite and just went ahead and did it, and I ended up not finding the optimal solution for either problem, haha. If anyone has ideas, let's discuss.
Problem 1
Given an array arr of n integers, for a triplet of 1-based indices i[1], i[2], i[3] (1 ≤ i[1] ≤ i[2] ≤ i[3] ≤ n+1),
grossValue(i[1], i[2], i[3]) = sum[i[1], i[2]) - sum[i[1], i[2]) + sum[i[2], i[3]) - sum[i[3], n+1)
Here, sum[l, r) (1 ≤ l ≤ r ≤ n + 1) uses half-open interval notation. It means that the interval includes index l but is exclusive of index r. Note that by definition, in the special case where l = r, sum[l, r) is 0, and arr[l, r) is empty.
Find the maximum gross value of any valid triplet.
Basically you cut the array into four segments and ask for the max of sub1 - sub2 + sub3 - sub4 (the cuts are allowed to be at the same position, or at the very start or very end of the array — there are a lot of edge cases). n is up to 3*10^3. I maintained a preSum and a postSum and enumerated the cut positions, O(n^3), which only passed 60% of the cases. I had no idea how to optimize it further.
Problem 2
There are n developers, where the skill level of the iᵗʰ developer is given by i, for 1 ≤ i ≤ n.
The task is to form a team of developers for a hackathon.
A developer agrees to be on the team only if certain conditions are met.
Given two arrays, lowerSkill and higherSkill, the iᵗʰ developer will join the team if at most lowerSkill[i] team members have a lower skill level than them, and at most higherSkill[i] team members have a higher skill level than them.
The objective is to select the largest possible team such that every developer on the team agrees with the team composition based on these conditions.
Example
Given n = 5,
lowerSkill = [1, 3, 2, 2, 2]
higherSkill = [2, 2, 1, 1, 3]
It is optimal to select developers with skill levels 1, 3, and 4.
For the developer with skill level 1, there are two developers with higher skill levels and higherSkill[1] = 2.
For the developer with skill level 3, there is one developer with a lower skill level and one with a higher skill level (lowerSkill[3] = 2, higherSkill[3] = 1).
For the developer with skill level 4, there are two developers with lower skill levels.
Thus, all three developers are content. Hence, the number of developers selected for the hackathon team will be 3.
Basically, for each position in the array, if that developer wants to join, at most lowerSkill people to their left can have joined, and at most higherSkill people to their right can join. n is up to 2*10^5. I used top-down DP with memoization, solve(pre, post, index), where pre is how many people have already been selected, post is how many more can be selected afterward, and index is the current decision position. Time complexity O(n^3), which only passed 33% of the cases, and the ones that failed just blew up the recursion stack. (I tried constant-factor pruning, which did absolutely nothing.)
Bottom-up DP would probably pass more cases, but O(n^3) is still nowhere close to passing everything. My gut feeling is the optimal solution should be O(n log n), using binary search on the answer plus a greedy O(n) check — but I couldn't figure out the greedy strategy, since there are constraints on both sides, which makes it really hard to be greedy.
Discussion
Loading comments…