5th Rejection | Media.net 6M+PPO | On-Campus

Media.net | SDE Intern | DSA Round | Rejected\n\nRound: Online Interview (DSA)\nDuration: 60 min\n\n---\n\n### Question\n\nGiven 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.\n\nPerform any number of operations. Return the minimum possible length of the array.\n\nExample\n\nInput: a = [1, 5, 6, 7, 4, 7]\nOutput: 0\n\nExplanation:\n[1, 5, 6, 7, 4, 7] → remove (5, 6, 7) → [1, 4, 7]\n[1, 4, 7] → remove (1, 4, 7) → []\n\n---\n\n### How it went\n\n- Started with brute force: take / not-take recursion + memoization.\n- 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.\n- The intended solution was Interval DP, but I couldn't come up with it on the spot.\n\nVerdict: Rejected\n\nSaw a comment once saying "if they ask you this, they don't want to hire you" and now I get it\n\n---\n\n### Solution ( I just solved it on 28 Oct 11:58pm )\n\ncpp\n#include <bits/stdc++.h>\nusing namespace std;\n\n#define int long long\n#define vi vector<int>\n#define vvi vector<vector<int>>\n#define all(x) (x).begin(), (x).end()\n#define rall(x) (x).rbegin(), (x).rend()\n#define pb push_back\n#define fi first\n#define se second\n\nvoid solve(){\n int n;\n cin>>n;\n vi a(n);\n for(int i = 0; i < n; i++){\n cin>>a[i];\n }\n vvi can(n, vi(n, 0));\n // can[i][j] = 1 if i,j is all zero\n // can[i][j] = 0 if it is there\n // dependent can[i][j] = can[i+1][k-1] && can[k+1][j-1] && 2*a[j] == a[i] + a[k]\n // independent can[i][j] = can[i][k] && can[k+1][j]\n for(int i=0;i<n;i++){\n for(int j=i+1;j<n;j++){\n can[j][i] = 1;\n }\n }\n for(int i=n-1;i>=0;i--){ \n for(int j=i;j<n;j++){\n // Logic for filling the can matrix\n if(j-i+1<=2)continue;\n for(int k=i+1;k<j;k++){\n can[i][j]|=(can[min(i+1,n-1)][max(0LL,k-1)] && can[min(k+1,n-1)][max(0LL,j-1)] && 2*a[k] == a[i] + a[j]);\n can[i][j]|=can[i][k] && can[min(k+1,n-1)][j];\n }\n }\n }\n vector<int>dp(n,0); // dp[i] : no of elements left until index i \n for(int i=0;i<n;i++){\n dp[i] = (i>0 ? dp[i-1] : 0)+1;\n for(int j=i;j>=0;j--){\n dp[i] = min(dp[i] , can[j][i] ? (j>0 ? dp[j-1]:0) : dp[i]);\n }\n }\n cout<<dp[n-1]<<endl;\n}\n\nint32_t main(){\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n int t = 1;\n cin >> t;\n while(t--){\n solve();\n }\n return 0;\n}\n