11 weeks ago

Rohit • 610

Hyderabad

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.

21 months ago

hardik kapoor 130

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] => [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)
• 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<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.