Can you please clarify why all occurrences of a particular element is clubbed in same array?

Entering edit mode

**Role:** Software Engineer Intern

**Stipend:** BTech 65k per month, MTech 70k per month.

**Benefits:** Intern housing, Airfare and Insurance.

**Eligible Courses and Branches:**

B.Tech, M.Tech: CS, EC, EI, EE

**Eligibility:**

*No URs and Backlogs*

**CGPA** >= *7*

**Number if Rounds:** 2

**Round 1:** **Coding Round**

There were two problems which were medium level, based on hashing and the second one based on hashing + string + sorting, which I have solved in 10 min. The Coding Round tool place in Hackerrank platform.

15 were shortlisted after Coding Round.

**Round 2:** **Technical + HR**

Two questions were asked in the technical round.

First one: Array Partition

Click here to Practice

Submit Problem to OJ

In above question, I told the exact logic behind it, because there is a lot of edge cases in this question, so i told all the logic/edge cases, but was not able to code it.

Other question was a medium level one, I solved it in a very fast manner, with the complete code, means including header file, take input and every other minute detail.

Then they focused on my project and were asking a lot of questions on project like How you did your project, what is the logic behind it, what was your role and many other things, wherein I discussed my project, in a very detailed manner, I told all the API that i have made in my project, and how it is working.

At the end some basic HR questions were also asked. And that is how the interview concluded.

**Verdict:** Selected

**Tips:** Don't be in a comfortable position in the interview.

Entering edit mode

Given an array, partition it into two arrays A and B, such that A intersection B is empty set, A union B gives the whole array back, the sum of values in set A must be strictly greater than sum of values in set B, and number of elements in set A must be minimal.

In first look, this problem looks easy, but greedy approach won't work.

Here are some test cases:

```
[2,5,5,9] => [2,9] (we won't necessarily take the largest values)
[2,2,4,5,5,11] => [4,11] (we won't necessarily take the smallest values either)
[5,5,5,10,10,10,11] => [10,10,10] (and we won't even necessarily take any largest value)
```

Hence, this is a knapsack problem.

- We have to put all occurrences of an element in either A or B, hence we will club them.
- Create an array of {element, num of occurrences}, lets name this array arr2
- For eg, array
`[2,3,2,1,4,1,4]`

will convert to`[{1,2},{2,2},{3,1},{4,2}]`

(sorted the array too)

- For eg, array
- We will maintain
`DP(i,j)`

, where i denotes we have checked until i in arr2, and j means the sum till now is j, and`DP(i,j)`

denotes minimum number of elements till i to make sum j. - While transitioning, we will also maintain a parent array, to recreate the array.

```
vector<int> solve(vector<int> a)
{
vector<pair<int,int>> v;
map<int,int> m;
int s=0;
for(auto x:a)
m[x]++,s+=x;
for(auto x:m)
v.push_back({x.first,x.second});
sort(v.begin(),v.end());
int n=v.size();
const int inf=1e9;
vector<vector<int>> dp(n+1,vector<int>(s+1,inf));
vector<vector<int>> prev(n+1,vector<int>(s+1,-1));
dp[0][0]=0;
for(int i = 1;i <= n;i++)
{
int curr=v[i-1].first*v[i-1].second;
for(int j = curr;j <= s;j++)
{
if(dp[i-1][j-curr]+v[i-1].second < dp[i][j])
{
dp[i][j]=dp[i-1][j-curr]+v[i-1].second;
prev[i][j]=j-curr;
}
}
for(int j = 0;j <= s;j++)
{
if(dp[i-1][j] < dp[i][j])
{
dp[i][j]=dp[i-1][j];
prev[i][j]=j;
}
}
}
vector<pair<int,int>> anstemp;
int mn=inf,ind=-1;
for(int j=s/2+1;j<=s;j++)
{
if(mn > dp[n][j])
{
mn=dp[n][j];
ind=j;
}
}
int iind=n;
while(prev[iind][ind]!=-1)
{
if(prev[iind][ind]==ind)
{
iind--;
continue;
}
anstemp.push_back(v[iind-1]);
ind=prev[iind][ind];
iind--;
}
vector<int> ans;
for(auto x:anstemp)
for(int i = 0;i < x.second;i++)
ans.push_back(x.first);
sort(ans.begin(),ans.end());
return ans;
}
```

Time Complexity: `O(N*S)`

, where S is the sum of the array.

Loading Similar Posts

Bro I have some doubt can i get your number/contact details