Internships

Hard
0/120
Average time to solve is 30m
profile
Contributed by
0 upvote
Asked in companies
DirectiGoldman Sachs

Problem statement

Ninja and his friends are ready to grab internships at different startups. There are ‘N’ applicants and ‘M’ internships available. Each internship has a requirement of one person and each person can be appointed for a single internship.

Given ‘N’, ‘M’ and a matrix ‘G’ of size ‘N x M’ where ‘G(i,j)’ denotes whether ‘ith’ applicant is interested in ‘jth’ internship. Find an assignment of internships such that as many applicants as possible get internships.

Output the maximum number of applicants that can get an internship.

Example : 
 N = 2
 M = 3
 G = [{ 1, 0, 1 }, { 0, 1, 1} ]

Explanation : 

One of the possible ways is first applicant gets internship 1 and second applicant gets internship 3.

Another possible way can be that the first applicant gets internship 3 and second applicant gets internship 2.

Hence, both of them can get internships.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains two integers ‘N’ and ‘M’ denoting the dimensions of the given grid.

The next ‘N’ lines contain ‘M’ integers each. Each integer is guaranteed to be ‘0’ or ‘1’.
Output format : 
For each test case, print a single integer denoting the maximum number of applicants that can be assigned an internship.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N <= 100
1 <= M <= 100   
G[i][j] = ‘0’ or G[i][j] = ‘1’ 

Time Limit : 1 sec
Sample Input 1 :
2
3 5
1 1 0 1 1
0 1 0 0 1
1 1 0 1 1
4 2
0 1
0 1
0 1
0 1
Sample Output 1 :
3
1
Explanation Of Sample Input 1 :
For test case 1 we have, 

Applicant 1 can get internship 1, Applicant 2 can get internship 2 and applicant 3 can get internship 5.

Hence, we output 3.

For test case 2 we have,

All applicants are interested in only internship 2. So, only one of them can get an internship.

So, we output 1.
Sample Input 2 :
2
2 5
1 0 1 0 0 
0 0 1 0 0 
2 4
0 1 1 1 
1 0 0 0
Sample Output 2 :
2
2
Hint

Try to recursively assign internships to all students.

 

Approaches (2)
Brute Force

 

Approach : 
 

 

  • We will recursively assign internships to students if it is available and the student is interested in that particular internship.
  • When we have exhausted all students or exhausted all set of internships , we check if this is the optimal assignment.

 

 

Algorithm : 


 

  • Initialise a vector ‘visited’ of size ‘M’ to check if the internship is available or not.
  • Maintain a global variable ‘curr’ initialised to ‘0’.
  • Start a recursive call from applicant 1.
  • Traverse from ‘i=0’ to ‘i=M-1’ over all internships :
  • If current internship is available and current applicant is interested :
    • Mark ‘visited[i]’ = 1.
    • Increment ‘curr’.
    • Recur for the next applicant.
    • After the recursive call ends, mark ‘visited[i]=0’ and decrement ‘curr’.
  • When we complete calls for all ‘N’ students, update ‘ans’ as max of ‘ans’ and ‘curr’.
  • Return ‘ans’ as the final result.

 

Time Complexity

O(M*(N^M)) , where ‘N’ is the number of applicants and ‘M’ is the number of internships.
 

We are recursively checking all assignments, so the time complexity is O(M*(N^M)).

 

Space Complexity

O(M), where ‘N’ is the number of applicants and ‘M’ is the number of internships.

 

We are maintaining a vector of size ‘M’ to check available internships, so the overall complexity is O(M).

 

Code Solution
(100% EXP penalty)
Internships
Full screen
Console