wizard_18's blog

Google Interview Question...Help me to solve it
By wizard_18, history, 5 years ago, In English

Link of the question There are N countries. The ith country has A[i] number of players. You want to create new teams such that : 1. No two members from the same team are from the same country i.e. every member from a team should be from a different country 2. Teams should be exactly of size K Your task is to write a program to calculate the maximum number of teams that can be made. Input First line contains two integers N and K Second line contains N integers, denoting the number of players from each country Output Print one number equal to the maximum number of teams that can be made Notes 1 ≤ N, K ≤ 200 All values of A[i] fit in 32-bit integers. Sample Input 0 4 3 2 4 3 6 Sample Output 0 4

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can you share the source of these problems??

→ Reply
»
5 years ago, hide # |
← Rev. 6  
Vote: I like it +1 Vote: I do not like it

First of all, sort the terms in descending order.
There seem to be 3 cases to consider here:
1) N < K: Output would be 0 as no teams can be formed.
2) N == K: Output would be the minimum term.
3) N > K: All the terms after the kth term are extras, which can be used to 'fill in the gaps' in the first K terms (in descending order). The output would be the Kth term formed after 'filling some gaps' with the extra terms.

A Possible Solution which uses a priority queue:
Example:

Edit: The above solution's based on a greedy approach which most probably won't work for all the test cases.
Note: Each extra term's values can only be used to fill in one column (nation) at most.

→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    This won't work. Your extras can be possibly used to create more teams not using the first K nations.

    → Reply
    • »
      »
      »
      5 years ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      But multiple extra columns can be used to 'replenish' a single pre-existing column, so new teams can be formed well after the original columns have been used up.
      Columns should be appended from the left of the extra set to the right of the original K set.
      Haven't proven it yet, but seems intuitive and at least worth a try.

      → Reply
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Pick $$$k$$$ countries which currently have the highest number of players and remove 1 player from each of them. Do this until you can no more select $$$k$$$ players(i.e. there are less than $$$k$$$ countries with atleast 1 player left). Also, please share the resource/link to the problem and maybe other similar problems.

→ Reply
»
5 years ago, hide # |
← Rev. 3  
Vote: I like it +6 Vote: I do not like it

You can use binary search here
https://atcoder.jp/contests/abc143/tasks/abc143_f
Also similar question on binary search.com
https://binarysearch.com/problems/K-Distinct-Groups

→ Reply
»
5 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

The problem is similar to
We have n groups with group size a[i] and we can merge two or more groups together. There should be k groups at the end and we have to maximize the minimum of group sizes.

We can do binary search on the number of teams possible. Now, to check if a given number of teams is possible or not, we can sort the array in descending order and can do two-pointer approach. Initially left=0 and right=n-1. Now, if the current nation has size greater than or equal to the required number of teams then, increment the left pointer and also the count of completed groups otherwise add the value of a[right] to a[left] and decrease the right pointer.

Code
→ Reply
»
5 years ago, hide # |
 
Vote: I like it +23 Vote: I do not like it

Binary Search on the answer, Now how to check if we can make M teams of K size each

Note that we need a total of M * K members

now from each country, we can take a maximum of M members, so if the summation of Min(A[i],M) overall "i" is greater than or equal to M * K then we can form M teams of K size each, otherwise not.

→ Reply
»
5 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

A possible solution which uses a priority queue (based on my comment above):

Code

Edit: This is based on a greedy approach and won't work for all the test cases.

→ Reply