Google Interview Question SDE1s
Country: India
+ Since we are required to pick each player from different country, the number of ways to pick a single player from n players is nC1 = n
+ Now it boils down to generating combinations of N countries with k size and accumulating the result of all.
+ for k = 3 and if selected countries have players {3} {2} {5}, number of teams one can build is = 3C1* 2C1* 5C1 = 3*2*5 = 30
+ generate all country combinations of size k using back and accumulate the resule using above formula.
you can probably follow this greedy approach:
sort all the numbers.
try to form teams from the lowest index towards the highest index.
ex:13 11 9 3 2 2 1 and k = 3,
then, in first move
form 1 team from 2 2 1,
array is now: 13 11 9 3 1 1 0,
then form 1 team from 3 1 1,
the array now is 13 11 9 2 0 0 0.
form 2 teams from 11 9 2
the array now is 13 9 7 0 0 0 0.
form 7 teams from 13 9 7,
the array now is 6 2 0 0 0 0 0. now stop as no more teams can be formed.
total teams formed = 1 + 1 + 2 + 7 = 11
This is not the correct answer for the given example.
Start from the biggest groups: 13, 11, 9. Then, distribute
the smaller groups, so you get: 13, 11+2, 9+3+1 and
the remaining 2 players unassigned. The answer is 13
teams.
Actually, this example falls into the case where the total
number of players (41) is sufficient to create 41 / 3 = 13
teams, which is not less than the maximal group. Thus,
the players from each country can be distributed to
different teams.
public class MyClass {
public static void main(String args[]) {
//call getNoOfTeams method
}
private int getNoOfTeams(Country[] countries, int teamLength) {
int result = 0;
if(countries == null || countries.length ==0 || teamLength < 1)
return result;
List<Country> list = new ArrayList<>();
PriorityQueue<Country> queue = new PriorityQueue<>(new Comparator<Country>(){
public int compare(Country c1, Country c2) {
return c2.no - c1.no;
}
});
for(Country c : countries) {
queue.offer(c);
}
while (teamLength > queue.size()) {
for(int i=0; i<teamLength; ++i) {
Country temp = queue.poll();
temp.no = temp.no-1;
if(temp.no > 0) {
list.add(temp);
}
}
++result;
for(Country item : list)
queue.offer(item);
list.clear();
}
return result;
}
}
class Country {
String name;
int no;
public Country(String name, int no) {
this.name = name;
this.no = no;
}
}
Won't it get stuck in the while loop in getNoOfTeams method if teamLength is greater than queue size? Because uour teamLength remains same throughout the execution, only queue size varies. Please clear my doubt
sorry forgot to mention the class name /dsalgoazra/dsalgorithm/src/algorithm/DP/FindMaximumTeams.java
I kinda did it using Kotlin, but Java should be really similar,
order the countries in descending by no of players
for K slots fill each country in one slot where the min total players is the lowest
(when the no of total players in slot clashes no of countries in the slot must be lowest)
this should give us minimum difference between the slots and the max number of teams is the min total of the slots
import java.util.*
import kotlin.collections.ArrayList
private val input = Scanner(System.`in`)
fun main(args: Array<String>) {
print("Enter no of countries N : ")
val n = input.nextInt()
val arr = ArrayList<Int>()
repeat(n) { i ->
print("Enter count of Players of Country[${i + 1}] : ")
arr.add(input.nextInt())
}
arr.sortDescending()
print("Enter size of Team K : ")
val k = input.nextInt()
val slots = ArrayList<Slots>()
repeat(k) { slots.add(Slots()) }
arr.forEach {
slots.sortedBy { it.sArr.size }
.sortedByDescending { it.total }
.minBy { it.total }?.apply {
total += it
sArr.add(it)
}
}
print("Max possible No of teams is ${slots.minBy { it.total }?.total}")
}
class Slots(var total: Int = 0, val sArr: ArrayList<Int> = ArrayList())
class Team
{
public static void main (String[] args) throws java.lang.Exception
{
int nosCountries = 5;
int nosPlayers = 5;
int teamSize = 3;
int[][] mat = new int[nosPlayers][nosCountries];
List<Integer> list = new ArrayList<>();
int[] out = {0};
int teamCount = 0;
for (int r = 0; r < mat.length; r++) {
int currTeamPlayerCount = 0;
dfs(mat, r, 0, currTeamPlayerCount, out, teamSize);
teamCount += out[0];
out[0] = 0;
}
System.out.println(teamCount);
}
public static boolean isValid(int[][] mat, int p, int c) {
return p >= 0 && c >= 0 && p < mat.length && c < mat[0].length;
}
public static void dfs(int[][] arr, int p, int c, int currTeamPlayerCount, int[] output, int k) {
if (!isValid(arr, p, c)) {
return;
}
if (currTeamPlayerCount == k - 1) {
output[0]++;
return;
}
for (int j = c + 1; j < arr[0].length; j++) {
currTeamPlayerCount++;
dfs(arr, p, j, currTeamPlayerCount, output, k);
currTeamPlayerCount--;
}
}
}
import java.util.*;
public class GetMaxTeamsPossible {
public static int GetMaxTeams(int[] sizeOfTeams, int K)
{
if(sizeOfTeams == null || sizeOfTeams.length == 0)
{
return -1;
}
int tempK =0;
int result = 0;
PriorityQueue<Integer> visitedTeams = new PriorityQueue<Integer>(sizeOfTeams.length, Collections.reverseOrder());
PriorityQueue<Integer> unVisitedTeams = new PriorityQueue<Integer>(sizeOfTeams.length, Collections.reverseOrder());
for(int i = 0 ;i < sizeOfTeams.length ; ++i)
{
unVisitedTeams.add(sizeOfTeams[i]);
}
while(!unVisitedTeams.isEmpty())
{
while(!unVisitedTeams.isEmpty() && tempK < K)
{
int t = unVisitedTeams.remove();
--t;
if(t > 0)
{
visitedTeams.add(t);
}
++tempK;
}
if(tempK < K)
{
break;
}
tempK=0;
++result;
unVisitedTeams.addAll(visitedTeams);
visitedTeams.clear();
}
return result;
}
public static void main(String[] args)
{
int[] teamSizes = new int[] { 3, 5, 7, 3};
System.out.println("" + GetMaxTeams(teamSizes, 3));
}
}
import java.util.*;
public class GetMaxTeamsPossible {
public static int GetMaxTeams(int[] sizeOfTeams, int K)
{
if(sizeOfTeams == null || sizeOfTeams.length == 0)
{
return -1;
}
int tempK =0;
int result = 0;
PriorityQueue<Integer> visitedTeams = new PriorityQueue<Integer>(sizeOfTeams.length, Collections.reverseOrder());
PriorityQueue<Integer> unVisitedTeams = new PriorityQueue<Integer>(sizeOfTeams.length, Collections.reverseOrder());
for(int i = 0 ;i < sizeOfTeams.length ; ++i)
{
unVisitedTeams.add(sizeOfTeams[i]);
}
while(!unVisitedTeams.isEmpty())
{
while(!unVisitedTeams.isEmpty() && tempK < K)
{
int t = unVisitedTeams.remove();
--t;
if(t > 0)
{
visitedTeams.add(t);
}
++tempK;
}
if(tempK < K)
{
break;
}
tempK=0;
++result;
unVisitedTeams.addAll(visitedTeams);
visitedTeams.clear();
}
return result;
}
public static void main(String[] args)
{
int[] teamSizes = new int[] { 3, 5, 7, 3};
System.out.println("" + GetMaxTeams(teamSizes, 3));
}
}
Using a greedy algorithm approach:
1. Build a Max Heap of Country sorting by number of players, countries with most players will be picked first
2. fill priority queue with input list
3. while queue not empty: iterate collecting players from each country in each cycle until a bucket of size K is filled
4. return num of cycles executed
Implementation of the above idea in Scala:
case class Country(players: Int, name: String)
object SplitKBuckets {
def main(args: Array[String]): Unit = {
println(maxGroupsK(
List(
Country(4, "USA"),
Country(6, "CHI"),
Country(6, "IND"),
Country(3, "BRA"),
Country(2, "AUS"),
Country(1, "CAN")),
3
))
}
def sortByPlayers(c: Country) = c.players
def maxGroupsK(countries: List[Country], k: Int): Int = {
val priorityQueue: PriorityQueue[Country] = PriorityQueue()(Ordering.by(sortByPlayers))
priorityQueue ++= countries
def cycle(): Boolean = {
if (priorityQueue.isEmpty) {
false
} else {
val list = ListBuffer.empty[Country]
var count = 0
while (priorityQueue.nonEmpty && count < k) {
val c = priorityQueue.dequeue()
if (c.players > 1) {
list += Country(c.players - 1, c.name)
}
count += 1
}
priorityQueue ++= list
count == k
}
}
@tailrec def numCycles(count: Int): Int = {
if (!cycle()) count
else numCycles(count + 1)
}
numCycles(0)
}
}
/*
output: 7
*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin>>N;
int A[N];
for(int i=0; i<N; i++)
{
cin>>A[i];
}
int K;
cin>>K;
if(K > N)
{
return 0;
}
sort(A, A+N);
int carry = 0;
int sum = 0;
for(int i=0; i<=N-K; )
{
sum = sum + A[i] - carry;
int j = i+1;
while(j < i+ K && j < N && A[j] == A[i])
{
j++;
}
if(j == i + K)
{
carry = 0;
}
else
{
carry = A[i];
}
i = j;
}
cout<<sum<<endl;
}
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin>>N;
int A[N];
for(int i=0; i<N; i++)
{
cin>>A[i];
}
int K;
cin>>K;
if(K > N)
{
return 0;
}
sort(A, A+N);
int carry = 0;
int sum = 0;
for(int i=0; i<=N-K; )
{
sum = sum + A[i] - carry;
int j = i+1;
while(j < i+ K && j < N && A[j] == A[i])
{
j++;
}
if(j == i + K)
{
carry = 0;
}
else
{
carry = A[i];
}
i = j;
}
cout<<sum<<endl;
}
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin>>N;
int A[N];
for(int i=0; i<N; i++)
{
cin>>A[i];
}
int K;
cin>>K;
if(K > N)
{
return 0;
}
sort(A, A+N);
int carry = 0;
int sum = 0;
for(int i=0; i<=N-K; )
{
sum = sum + A[i] - carry;
int j = i+1;
while(j < i+ K && j < N && A[j] == A[i])
{
j++;
}
if(j == i + K)
{
carry = 0;
}
else
{
carry = A[i];
}
i = j;
}
cout<<sum<<endl;
}
int countOfTeams(int* countries, int N, int K)
{
if (K == 0 || K>N) return 0;
priority_queue<int, vector<int>> maxheap;
for (int i = 0; i < N;i++)
maxheap.push(countries[i]);
vector<int> team(K);
int sum = 0;
while (K <= maxheap.size())
{
for (int i = 0; i < K; i++)
{
team[i] = maxheap.top();
maxheap.pop();
}
int count = team.back();
sum += count;
for (int i = 0; i < K; i++)
{
team[i] -= count;
if (team[i] > 0)
maxheap.push(team[i]);
}
}
return sum;
}
The overall time-complexity on average is O(N(N-K)), independent of A[i].
int main( int argc, char * argv[] ){
int n,k ; cin >> n >> k;
vi v(n); input(v);
if( k > n ) return -1; // number of countries > k
if( count_if( v.begin(), v.end(), [](int x){ return x > 0; } ) < k ) return -1; // number of non-zero players countries > k.
int ans = 0;
do{
// get top K countries with maximum players
nth_element(v.begin(), v.begin()+k, v.end(), greater<int>());
ans += v[k];
// form v[k] teams, where v[k] is the smallest among top k countries.
for_each(v.begin(), v.begin()+k, [y=v[k]](int & x){ x-= y; });
}while(v[k]>0);
cout << ans << '\n';
return 0;
}
An O(nlogn) solution in C++, when the team size << total number of players:
#include <iostream>
int getTeams(vector<int> &players, int teamSize)
{
if (players.empty()) return 0;
int counter = 0;
priority_queue<int> pq(players.begin(), players.end());
stack<int> tmpStack;
int n = 0;
while (pq.size() >= teamSize)
{
n = 0;
while (n < teamSize && !pq.empty())
{
tmpStack.push(pq.top() - 1);
pq.pop();
++n;
}
if (n == teamSize) ++counter;
while (!tmpStack.empty())
{
int t = tmpStack.top();
tmpStack.pop();
if (t > 0) pq.push(t);
}
}
return counter;
}
int main()
{
vector<int> v = {5, 3, 3, 5};
std::cout << getTeams(v, 3) << std::endl;
}
Use a maximum heap to store the countries, poll one country's player count each round and decrease by 1.
If there are players left, add the country back after this round (Note⚠️: not add it immediately after the poll, or it might be counted more than once in a single round).
If the size of heap is less than k, return the number of rounds.
public int maxNumberOfTeams(int[] countries, int k) {
if (countries == null || countries.length == 0 || k <= 0) return 0;
PriorityQueue<Integer> candidatePool = new PriorityQueue<>(((o1, o2) -> o2 - o1));
for (int country : countries) {
if (country <= 0) return -1;// Invalid input should be warned
candidatePool.offer(country);
}
int res = 0;
Stack<Integer> stack = new Stack<>();
while (candidatePool.size() >= k) {
for (int i = 0; i < k; i++) {
int country = candidatePool.poll();
if (--country > 0) stack.push(country);
}
while (!stack.empty()) candidatePool.offer(stack.pop());
res++;
}
return res;
}
*copied from leet code
As per my understanding, the algo should be like the following
- Saurabh March 23, 2019a) Sort the array in descending order of Player left
b) Keep pick 1 player each from the start and deduct it till index K-1
c) Resort (optimize by using insertion sort style starting from Index K onwards).
d) Repeat when the index K-1 reaches 0.