Question: VISA, Summer Internship Interview Experience in NITs, 2023
0
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

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.

2
Entering edit mode

# Solution to array partition problem

## Description

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.

## Approach

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

Here are some test cases:

``````[2,5,5,9] =&gt; [2,9] (we won't necessarily take the largest values)
[2,2,4,5,5,11] =&gt; [4,11] (we won't necessarily take the smallest values either)
[5,5,5,10,10,10,11] =&gt; [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)
• 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.

## C++ Code

``````vector&lt;int&gt; solve(vector&lt;int&gt; a)
{
vector&lt;pair&lt;int,int&gt;&gt; v;
map&lt;int,int&gt; 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&lt;vector&lt;int&gt;&gt; dp(n+1,vector&lt;int&gt;(s+1,inf));
vector&lt;vector&lt;int&gt;&gt; prev(n+1,vector&lt;int&gt;(s+1,-1));
dp=0;
for(int i = 1;i &lt;= n;i++)
{
int curr=v[i-1].first*v[i-1].second;
for(int j = curr;j &lt;= s;j++)
{
if(dp[i-1][j-curr]+v[i-1].second &lt; 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 &lt;= s;j++)
{
if(dp[i-1][j] &lt; dp[i][j])
{
dp[i][j]=dp[i-1][j];
prev[i][j]=j;
}
}
}
vector&lt;pair&lt;int,int&gt;&gt; anstemp;
int mn=inf,ind=-1;
for(int j=s/2+1;j&lt;=s;j++)
{
if(mn &gt; 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&lt;int&gt; ans;
for(auto x:anstemp)
for(int i = 0;i &lt; 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.

Entering edit mode
0

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

Entering edit mode
1

Actually, we have to put all occurrences of a particular element in either A or B, because if we don't do that, the A intersection B won't be empty set. That's why I have clubbed them.