Google Interview Question for SDE1s


Country: India




Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
    }
}

- Popeye February 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this line is while (teamLength <= queue.size()) // just a correction

- Popeye February 12, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Gopal B February 15, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry, this line is while (teamLength <= queue.size()) // just a correction

- Anonymous February 15, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone help me with this problem ?

- crowdx February 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- saty February 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- hb February 14, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

check my solution at github
/dsalgoazra/dsalgorithm

it has better time complexity.

- azrarabbani February 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

sorry forgot to mention the class name /dsalgoazra/dsalgorithm/src/algorithm/DP/FindMaximumTeams.java

- azrarabbani February 12, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

+ 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.

- helloWorld February 13, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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())

- PeyarTheriyaa February 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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--;
		}
 
	}
}

- sj February 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));

}

}

- Guru February 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
		
	}

}

- Guru February 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
*/

- guilhebl February 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def pick(L, head, K):
    if len(head) == K:
        yield head
    else:
        for i in range( len(L) ):
            h = L[i]
            nL = L[:i] + L[i+1:]
            for t in pick(nL, head + [h], K):
                yield t

if __name__ == '__main__':
    for t in pick( ['US', 'RU', 'FL', 'CA', 'IR', 'NK', 'SK', 'UK'], [], 3):
        print (t)

- Anonymous February 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Anonymous February 16, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Nisha Agrawal February 16, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Nisha Agrawal February 16, 2019 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More