Search

vishyblog

Category

Uncategorized

Assignment Problem (Hungarian Algorithm)

I was searching for Assignment problem a lot and was not getting it .I tried to solve using Hungarian Algorithm but somehow no online code was available for it. Topcoder has provided with code snippets and implementation but it never worked out for me.

Here is best implementation for it.

 

Hungarian Algorithm.

#include <bits/stdc++.h>

using namespace std;

#define bug() printf(“BUG\n”)
#define bug1(n) cout<<“bg1 “<<n<<endl;
#define bug2(a,b) cout<<“bg2 “<<a<<” “<<b<<endl;
#define bug3(a,b,c) cout<<“bg3 “<<a<<” “<<b<<” “<<c<<endl;
#define MOD 1000000007
#define ll long long
#define vi vector< int >
#define vll vector< long long >
#define vvi vector< vector< int > >
#define vvll vector< vector< long long > >
#define pi pair< int, int >
#define pll pair< long long, long long >
#define vpi vector< pair< int, int > >
#define vpll vector< pair< long long, long long > >
#define pb(n) push_back(n)
#define mp(a,b) make_pair(a,b)
#define printA(a,n) for(int lolol = 0;lolol < n;++lolol) cout<<a[lolol]<<” “; cout<<endl;

int lines[55][55];

void print2A(int a[][55],int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
printf(“%d “,a[i][j] );
}
printf(“\n”);
}
}

int linesRequired(int a[55][55], int n)
{
int lll = (int)pow(2,2*n);
int mask[100] = {0};
int cpy[55][55];
int tlines[55][55] = {0};
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cpy[i][j] = a[i][j];
}
}
int miny = INT_MAX;
for (int i = 1; i <= lll; ++i)
{
int cnt = 0;
for (int k = i,j = 0; k > 0 && j < 2*n; k/=2,j++)
{
if (k%2 == 0)
mask[j] = 0;
else
{
mask[j] = 1;
cnt++;
}
}
if (cnt > n)
{
continue;
}
for (int k = 0; k < n; ++k)
{
if (mask[k] == 1)
{
for (int j = 0; j < n; ++j)
{
cpy[k][j] = 1; //row k
tlines[k][j] -= 1;
}
}
}
for (int k = n; k < 2*n; ++k)
{
if (mask[k] == 1)
{
for (int j = 0; j < n; ++j)
{
cpy[j][k-n] = 1; //column k-n
tlines[j][k-n] -= 1;
}
}
}
for (int x = 0; x < n; ++x)
{
for (int y = 0; y < n; ++y)
{
if (cpy[x][y] == 0)
{
goto here;
}
}
}
if (miny > cnt)
{
miny = cnt;
for (int x = 0; x < n; ++x)
{
for (int y = 0; y < n; ++y)
{
lines[x][y] = tlines[x][y];
}
}
}
if (miny < n)
{
return miny;
}
here:
{}
for (int x = 0; x < n; ++x)
{
for (int y = 0; y < n; ++y)
{
cpy[x][y] = a[x][y];
tlines[x][y] = 0;
}
}
}
return miny;
}

int minAlloc(int a[55][55],int actual[55][55],int n)
{
stack< pi >st;
vector< pair < int,pi > >m;
for (int i = 0; i < n; ++i)
{ //m[a,0] = 0 -> row a is assigned, m[a,0] = 1 -> row a is not assigned
m.pb(mp(0,mp(i,0))); //row
m.pb(mp(0,mp(i,1))); //column
}
int d = 1,prev = 1; //d = 1 -> forward, d = -1 -> backward
int xx = 0; //it has got some importance
int mask[55][55] = {0};
for (int i = 0,j; st.size() != n; ++i)
{
int flag = 0;
if (d == 1)
{
if (prev == -1)
{
j = xx;
}
else
j = 0;
for (; j < n; ++j)
{
if (a[i][j] == 0)
{
int po1 = find(m.begin(),m.end(),mp(0,mp(i,0))) – m.begin();
int po2 = find(m.begin(),m.end(),mp(0,mp(j,1))) – m.begin();
if (po1 < m.size() && po2 < m.size())
{
flag = 1;
st.push(mp(i,j));
m[po1].first = 1;
m[po2].first = 1;
goto here;
}
}
}
here:
{}
if (flag == 0)
{
if (prev == -1)
{
i–;
}
d = -1;
}
else
prev = 0;
}
if (d == -1)
{
prev = -1;
pi p = st.top();
st.pop();
int po1 = find(m.begin(),m.end(),mp(1,mp(p.first,0))) – m.begin();
int po2 = find(m.begin(),m.end(),mp(1,mp(p.second,1))) – m.begin();
m[po1].first = 0;
m[po2].first = 0;
mask[p.first][p.second] = 0;
i = p.first – 1;
xx = p.second + 1;
d = 1;
}
}
int ans = 0;
while(!st.empty())
{
pi p = st.top();
st.pop();
ans += actual[p.first][p.second];
}
return ans;
}

int main()
{
int n;
scanf(“%d”,&n);
int a[55][55];
int copy[55][55];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
scanf(“%d”,&a[i][j]);
copy[i][j] = a[i][j];
}
}
int miny;
for (int i = 0; i < n; ++i)
{
miny = a[i][0];
for (int j = 0; j < n; ++j)
{
miny = min(miny,a[i][j]);
}
for (int j = 0; j < n; ++j)
{
a[i][j] -= miny;
}
}
for (int i = 0; i < n; ++i)
{
miny = a[0][i];
for (int j = 0; j < n; ++j)
{
miny = min(miny,a[j][i]);
}
for (int j = 0; j < n; ++j)
{
a[j][i] -= miny;
}
}
int l = linesRequired(a,n);
while (l != n)
{
int minr = INT_MAX; //min of remaining.
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (lines[i][j] >= 0)
{
minr = min(minr,a[i][j]);
}
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (lines[i][j] >= 0)
{
a[i][j] -= minr;
}
if (lines[i][j] == -2)
{
a[i][j] += minr;
}
}
}
for (int i = 0; i < 55; ++i)
{
for (int j = 0; j < 55; ++j)
{
lines[i][j] = 0;
}
}
l = linesRequired(a,n);
}
int ans = minAlloc(a,copy,n);
cout<<ans<<endl;
return 0;
}

 

Input:-

3
4 15 20
7 10 19
7 20 4

Output:-

18

description:-

as 1->4,

2->10,

3->4

 

Advertisements

Microsoft Rejection Story

hello guys,

Its been long time didn’t write anything here.Its because I may have taken  microsoft rejection seriously.Now its fine.Let me descirbe how it went.

On the day of interview I went to pesit college with full enthusiasm that i will crack it.

first round: Group Fly 

They came in and asked 2 Q;

  1. find lowest common ansestor of 2 given node.I gave a solution they checked it with all test cases and corrected me they were helpful.(find distance of 2 given nodes recursively from root to downwards if you couldnt find distance return its parent.)
  2. given 2 arrays find kth minimum element among those 2 array.                                           ex:A1: 0 1 1 2 3 3 4                                                                                                                                          A2:1 2 7 8 6 7 9                                                                                                                                  so 5th smallest element will be  2                                                                                                       (use merge sort)I wrote this on paper he was so happy that he selected me for next round.

secod round:Interview

I was called then it went well. she was very much calm and experienced  but too helping in  nature.(I advide you guys to ask help they will definately help you).She asked me directly Q no intro nothing.

  1. find 2 number in an array of billion numbers such that their sum equal to given number.                                                                                                                                                       Ex. A: 1,2,3,4,6,734,2,342,3,25,452,3425,………….                                                                                 sum =40    find x,y in array such that x+y=sum.                                                                      Do it using keeping another array of size sum ..I guess you guys got it
  2. find maximum contenious sub array sum problem.( I knew this problem as i had solved this in hackerearth its KADANE’s Algorithm)

she was happy with the way i explained to her.

third Round:Interview

I was nervous about this interview.He took me in and asked me my intro.then I was able to say proerly .He asked me Q

  1. fold of linked list. I explained  him then he asked me to code it.I did it but couldnt see all boundary casess so he was not happy with it.I still regret y i didnt write proper code.
  2. next he asked me oops concept i explained him.Then asked me ooverrinding in deep.With code I explained him but did a mistake in creating pointer to base class.Again a point for sadness
  3. he asked me a linked list puzzle .extra Random pointer one.I dindt get it then he helped me to over come it .then asked him few Q like what he do in microsoft then what statergy they use in microsoft to solve problem and build project.Then i justified him how i would code 1st Q he asked according to answer given by him.He said me at end to have strong basic as i flumblled at base class pointer.

At this point only 5 were left.

Fourth round :Interview

I didnt had any clue what this round going to be.Then came a heavy specs guy.He was Busy with his laptop gave me a problem which seemed to me as some heavy strikning thing.It was to find diameter of BT.I tried my best and gave a solution but as I wrote code too long it was not recognizable.Thats it he checked for corner cases and said you have to do this and said me you can do it but thill then i was rejected.

thats it guys I was Rejected .Hope you guys had greate expirence reading it.Read GeekForGeeks thats more than enough.

Thank you.

And ya it is my 18th Rejection

 

Microsoft interview 1st and 2nd round for developer

hello guys,

I am posting here my today’s experience of microsoft interview.

today microsoft came to our college for developer post.will explain briefly down below.

first i needed to take permission from manager where i was intern,I dropped her an email stating that i can’t come due to project synopsis issue(other reason  :-p)(even my manager would have made an excuse if she would have got an opportunity like microsoft).But sadly she didn’t agree  for it.                                                                             then asked my mentor to send her(manager) a mail.at last my mentor helped me(it was so nice of her).then comes rounds.

it was hosted on cocubes.

1st round:-(30 minutes 15 Q):

all Question were on output recognisation,one was trick one

*) 2 3d cumbes joined from one point on each other.we needed to find number of ways between 2 points .points were poles apart.

*)most were on linked list so get your linked list knowledge more.(circular linked list)

*)some process and test question.

they selected arround 170 from 200 so it was like selecting almost all.                                In next round our pass key was not working (2 of us) so they gave new candidate key and pass key.Hope so that wont miss calculate our scores.

2nd round(60 minues 2 Q):

it had mostly different for different students.

1st Q)find maximum difference of index j-i in an array A given with length N such that A[j]>A[i] and j>i;

ex A= 22 3 2 30 36 3

A[4]>A[0] ans is (4-0)   4

it was easy so could clear it.

2nd Q)find sum of boundary value in a Binary  tree given a Binary Tree.

it was trick Question,

I solved it by calculating sum of left node data value and sum of right node data value and sum of leaf data value.I luckily got it at 58th minute (phew).

solution GFG :-http://www.geeksforgeeks.org/boundary-traversal-of-binary-tree/

Now waiting for them to conduct next round.Till then preparation time.

 

coding Q4

Alex Larson has an amount $X. She wants to distribute the amount among her N friends. Find the number of ways in which she can distribute this amount such that each friend gets at least $1. As the number of ways can be large so print it modulo 10 +7.   You have to complete the function count_ways that receives two integers X and N as arguments and returns the total number of ways.   Constraints 1 ≤ X ≤  10 1 ≤ N ≤  50   Note The order of distribution does not matter. If X=3 and N=2 then ﴾1, 2﴿ and ﴾2, 1﴿ are considered same.   Sample Input 0
6  3
Sample Output 0
3
Explanation X=6, N=3 There are 3 ways of distributing Rs 6  among 3 daughters, (1,1,4) ,(1,2,3) and (2,2,2).

Sample Input 1
10  5
Sample Output 1
7

 

 

 

solution
want one
I know it can be solved by (n+r-1)C(r-1) but i tried not able to get the desired output..

If anyone solved it please post the answer..

coding Q3

3.
Utkarsh and Ancestor Queries
Max. Marks 100

Utkarsh was playing with a rooted tree of N nodes. Each node is numbered from 1 to N. Assume 1 as the root. Each node i has two integers Ai an Bi associated with it.

You need to answer Q queries of 2 types
1 v x : update Av = x
2 v : Tell how many nodes p are there such that p is an ancestor of v and Ap ≤ Bv

Note: P is an ancestor of v if P = v or P is ancestor of parent of v.

Input:
First line contains two integers N and Q.
Following N-1 lines contains pair of integers a b denoting there is an edge between a and b.
Next line contains N integers denoting the Array A
Next line contains N integers denoting the Array B
Next Q lines describe Q queries.

Output:
For each query of type 2 output the required answer.

Constraints:
1 ≤ N ≤ 6104
1 ≤ Q ≤ 8
104
1 ≤ Ai, Bi, x ≤ 105


Sample Input

(Plaintext Link)

10 10
2 1
3 1
4 3
5 1
6 3
7 6
8 6
9 2
10 8
4 2 2 2 4 2 1 4 2 1
3 5 3 2 5 3 3 2 3 2
2 3
1 9 5
1 6 4
1 3 2
2 6
1 8 5
1 6 2
1 7 3
2 9
2 1
Sample Output

(Plaintext Link)

1
1
1
0

 

 

no answer

Coding Q2

Roy and Alfi are playing a game with three 1000-sided dice. Each die has 1000 faces and all the faces are marked from 1 to 1000 on each die.

Alfi rolls all three dice together and sums up the score on all three dice. Total score of Alfi is denoted by A. Now it is Roy’s turn to roll them. Let us denote Roy’s score as R, which is sum of scores on all 3 dice.

You have to find the number of ways in which R ≥ A.

Input:
First line contains T – number of test cases.
Each of the next T lines contains a single integer A – total score of Alfi.

Output:
For each test case output the result in a new line.

Constraints:
1 ≤ T ≤ 10
3 ≤ A ≤ 3000


Sample Input

(Plaintext Link)

3
3
4
3000
Sample Output

(Plaintext Link)

1000000000
999999999
1

Explanation

For three 1000-sided dice, the sample space would consist of 1000000000 ways.
These ways are (1,1,1), (1,1,2), (1,2,1), (2,1,1), … , … , … , (1000,1000,1000).

Test #1:
Sum of three dices such that it is greater than equal to 3.
This is satisfied by all the ways in the sample space. So the answer is 1000000000.

Test #2:
Sum of three dices such that it is greater than equal to 4.
This is not satisfied by only way (1,1,1) out of 1000000000 ways. So the answer is 1000000000 – 1 = 999999999.

Test #3:
Sum of three dices such that it is greater than equal to 3000.
Only way that satisfied this is (1000,1000,1000). Hence the answer is 1.

 

 

 

my answer

#include<bits/stdc++.h>
using namespace std;

#define ll long long int

int findWays(int m, int n, int x)
{

int table[n + 1][x + 1];
memset(table, 0, sizeof(table)); // Initialize all entries as 0

for (int j = 1; j <= m && j <= x; j++)
table[1][j] = 1;

for (int i = 2; i <= n; i++)
for (int j = 1; j <= x; j++)
for (int k = 1; k <= m && k < j; k++)
table[i][j] += table[i-1][j-k];

/* Uncomment these lines to see content of table
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= x; j++)
cout << table[i][j] << ” “;
cout << endl;
}*/
return table[n][x];
}
double solve(int m, int n, int x) //m : range; n , dices, x threshold.
{
if (x > m*n || x < n)
return 0;
vector<vector<int>> dp(2, vector<int>(m * n + 1));
for (int i = 0; i <= m * n; ++i)
dp[0][i] = min(i, m);
for (int i = 1; i < n; ++i)
{
fill(&dp[i%2][0], &dp[i%2][i], 0);
for (int j = i; j <= m * n; ++j)
dp[i%2][j] = dp[i%2][j – 1] + dp[(i – 1)%2 ][j – 1] – dp[(i – 1)%2 ][j – 1 – min(j – 1 , m)];
}
return double(dp[(n – 1)%2][m*n] – dp[(n-1)%2][x]) / dp[(n – 1)%2][m*n];
}

int main()
{

ll n,a,r,sum=0;
cin>>n;
while(n–)
{
cin>>a;
if(a==3000)
{
cout<<1<<endl;
continue;
}
for(int i=0;i<a;i++)
{
sum+=findWays(1000,3,i);
}
cout<<solve(1000,3,a);
cout<<1000000000-sum<<endl;
}

return 0;
}

 

 

coding questions

Shil and Hill Climbing
Max. Marks 100

Shil decided to go for hill climbing on this weekend, but he doesn’t have the map of all the hills. However he can make his own map.
There are N hills arranged on a line, each in the form of a vertical line segment with one endpoint on the ground. The hills are numbered with numbers from 1 to N from left to right. The i-th hill has height hi.

Beautiful set S is set of hills such that for any hi, hj present in set S , (hi * hj)%p != 1. Note that here i can be equal to j. Here p is any prime integer. To make the map, Shil needs maximum possible size of Beautiful Set.

Note that two sets are considered different if they contain atleast one point which is different. Two sets are considered same if they contain same points.

Input:
The first line of input contains two integers N, the number of hills and prime number p. The next N lines contains the height of the hills.

Output:
Print maximum possible size of Beautiful Set possible.

Constraints:
2 ≤ N ≤ 105
1 ≤ hi ≤ 1018
2 < p < 105
All the given hi are such that hi % p != 0


Sample Input

(Plaintext Link)

5 5
2 3 4 22 33
Sample Output

(Plaintext Link)

2
Explanation

The two possible Beautiful Sets are {2, 22} and {3, 33}. Here 4 can’t be in any beautiful set because (4 * 4) % 5 = 1. Also 2 and 3 can’t be in any beautiful set because (2 * 3) % 5 = 1. Also note that (2 * 22) % 5 != 1 and (3 * 33) % 5 != 1.

 

 

 

my answer

 

n,p=map(int,raw_input().split())
r=map(int,raw_input().split())
count=0
k=[]
for i in range(n):
if((r[i]*r[i])%p!=1):
k.append(r[i])
for i in range(len(k)):
for j in range(len(k)):
if((k[i]*k[j])%p!=1):
if(i!=j):
#print k[i],k[j]
count+=1
print count/2

 

 

 

My Failure

I am getting very frustrated due to  recent failure don’t know how to deal with it,

first one,

applied GATE exam but i am not able to prepare for that on top of it pressure from aunts and uncle to crack it dont know what will happen.

second one,

not getting into good company,getting rejected by lots lots of companies previously i used to clear aptitude exm but now that also not happening lots of companies rejected me

 

 

let me list them accordingly,

1->thorougood

was not preppared with proper memory arragment in operating system,threads was not prepared.

2->morgenstanly

was not prepared with basic c++ concept – oops concept,function pointer,and database was not cleared.

3-> cisco

couldnt clear first round

4-> akamai

couldnt clear first round

5->unisis

they were worst they made us wait till late evening and rejected.

6->tesco

coudnt write because of unisis.

7->redbus

couldnt clear thier written test.

 

8->cisco

they took only selected persons with cgpa between  8.5-9 i was above it so missed it.

9 ->akamai testing

i coundlnt write it because i was stuck with pavit bus .these assholes couldnt reach to banglore at right time.

10->Direct i

i wrote it i cleared it with 3rd rank . but they never came back again to take interwiew.Dont know y they did it like that.(still waiting for them).

11->knowlarity

i knew how to code but thier compiler was too much fucked up that it coudlnt display the output for the code we wrote.

12->adobe

it was for consultant job so i was not interested (now regreting it).

13->juniper

i wrote it cleared it but just because of 1mark they were planning to give me testing job so I rejected it.

14->SAP labs

my dream company wrote it properly but due to negligency of placement department the labs which CSE people were seated were not considered for evaluation.( was depressed)

15->oracle

their paper was so lengthy that i wasnt able to read them in one sitting somehow i wrote it but couldnt clear it.

16->Microsoft GTSE

cleared first round in group discussion was not selected due to lack of interest.I was in an urge of crying….

17->yahoo

was not prepared well and lost this one also….

18->huewie

cleared 1st round,cleared second round ,but in third round was rejected because i didnt knew much about pointers…dead by now

19->SAPLABS

again they came today now i did well hoping to clear this.too much desparate to get this.please god save me………please please

 

still lots to come hope i dont loose hope.

First Intro


Hello Everyone,

Myself vishwanath Kulkarni, born and brought up in gulbarga,Karnataka,India.did my High school at MTEMS School with 88% and intermediate at Shree Guru school with 89.67%.Both are located at Gulbarga.completed Bachelors of Engineering Degree at M S Ramaiah Institute of Technology(2016) with flying colours and good amount of cgpa(9.16).My Major is Computer Science.

Attended many hackathons and won few but didn’t loose hope still participate in many hackathons. Have interest in IOT and competitive programming.my hobby being table tennis.

This is all for the rechord.Will be coming back with my great adventures experience.Hope to see you soon.

Create a free website or blog at WordPress.com.

Up ↑