Media.net | SDE Intern | DSA Round | Rejected
Round: Online Interview (DSA)
Duration: 60 min
Question
Given an integer array a, in one operation you can pick 3 consecutive elements that form an Arithmetic Progression and remove them. After removal, the left and right parts join, so new elements can become adjacent.
Perform any number of operations. Return the minimum possible length of the array.
Example
Input: a = [1, 5, 6, 7, 4, 7]
Output: 0
Explanation:
[1, 5, 6, 7, 4, 7] → remove (5, 6, 7) → [1, 4, 7]
[1, 4, 7] → remove (1, 4, 7) → []
How it went
- Started with brute force: take / not-take recursion + memoization.
- The interviewer pushed for optimization. The catch is that removals can nest: elements far apart become adjacent after inner removals, so a simple index-based DP doesn't capture it.
- The intended solution was Interval DP, but I couldn't come up with it on the spot.
Verdict: Rejected
Saw a comment once saying "if they ask you this, they don't want to hire you" and now I get it