Google Interview Question Software Engineers
Country: United States
Interview Type: In-Person
I don't think this will work for all the cases. Imagine input slices set as {2, 3, 10, 15} and number of people is 5. The smallest number of slices in the list is 2. But this is not max number of slices a person could get (which is 5 in this case).
And what is time complexity for your solution? O(NLgN) to sort the input set and Lg(min(Slice(i)))*N to find a right number of slices.
I think, the second part can be solved in linear time (O(N)).
Actually I think it made more sense before. Specifically there is no spec for type of pie in the question so how could you posibly deduce which pies are of a given type.
Before after some thought i read that final condition as each person is allowed slices from however many pies they want as long as they dont take from all the pies. Essentially they are allowed up to a max of slices from n-1 pies.
So tou can start out your algorithm by tossing the edge case of 1 or fewer pies since 1 - 1 pies is 0 pies and no pies, no slices for you...
After that there is an easy way which I am sure is wrong, but assuming you were allowed to completely exclude a pie its a simple sort, total (minus the min) and divide by people for slices (in int to drop any remainder slice).... Well there is another question... What are we to do with any remainder slices... Probably were to only count whole slices but thats another worthwhile question.
//Time Complexity: O(nLogK) where n is the number of people and K is the number of slices in the smallest pie.
//Space Complexity:O(1)
public int countMaxSlices(int[] pie,int n)throws NullPointerException
{
if(pie==null)
{
throw new NullPointerException();
}
if(pie.length==0||n<=0)
{
return 0;
}
int end=pie[0];
int maxPerPerson=0;//max slices per person overall
int start=1;
//Iterate through the list of slices for each pie and find the pie that has the minimum total slices
for(int i=1;i<pie.length;i++)
{
end=Math.min(end,pie[i]);
}
//Use binary search to find optimal number of slices
while(start<=end)
{
int mid=(start+end)/2;
if(isFeasible(mid,pie,n))//Check if "mid" slices per person is feasible
{
maxPerPerson=mid;
start=mid+1;
}else
{
end=mid-1;
}
}
return maxPerPerson;
}
private boolean isFeasible(int perPerson,int[] pie, int n)
{
//distribute the pie slices in a greedy manner.
int slice=pie[0];//total number of slices in first pie (note this will never be greater than the total slices in the smallest pie)
int p=1;//first person to be served
int idx=0;
while(p<=n)//while there are people to be served
{
slice-=perPerson;//deduct slices from the current pie
p++;//prepare to serve next person
if(slice<perPerson)//if the current pie doesn't have enough slices (it is less than the value in perPerson)
{
idx++;//go to the next pie.
if(idx==pie.length)//if there is no more pies left.
{
break;
}
slice=pie[idx];//select current pie for next batch of slices.
}
}
return p>n;//if this condition is true, then all n people can be served with perPerson slices for each person.
}
Slices per person will be bound to either:
1. Total Number of pies / n
2. Min Pie Size.
Start with slices per person as pies/n (optimal scenario). Then try allocating on each pie
that qty. If not all people got served then decrement slices per person.
Code:
public class NumPies {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(6);
list.add(4);
list.add(6);
list.add(1);
System.out.println(getMaxSlices(list, 8));
}
public static int getMaxSlices(List<Integer> pieSlices, int n) {
if (pieSlices == null || pieSlices.isEmpty()) {
return -1;
}
int totalSlices = 0;
int minPieSize = Integer.MAX_VALUE;
for (Integer i : pieSlices) {
minPieSize = Math.min(minPieSize, i);
totalSlices += i;
}
if (n > totalSlices) {
return -1; // impossible to satisfy all
}
int slicesPerPerson = totalSlices / n;
if (slicesPerPerson >= minPieSize) {
return minPieSize;
}
int pies = 0;
while(pies < n && slicesPerPerson > 0) {
for (Integer i : pieSlices) {
pies += i / slicesPerPerson;
}
if (pies < n) {
pies = 0;
slicesPerPerson--;
}
}
return slicesPerPerson;
}
}
The idea of my solution is to sum the amount of total slices, and divide it by the number of people - this is the maximum possible amount of slices a person can get. Then - I go through the list of slices, check how many people can eat from each pie and sum it up.
If the number I got is bigger/ equal to nPeople then this is the answer, otherwise I decrease the maximum possible by 1 and so on..
public class Main {
public static void main(String[] args) {
List<Integer> list1 = Arrays.asList(5,7,4,3,13);
List<Integer> list2 = Arrays.asList(30,45,18,1);
int a = getMaxSlices(list1, 1);
int b = getMaxSlices(list1, 3);
int c = getMaxSlices(list1, 10);
int d = getMaxSlices(list2, 5);
}
public static int getMaxSlices(List<Integer> slices, int nPeople){
int sum = getSumOfSlices(slices);
int maxSlices = sum/nPeople;
while(maxSlices > 0){
if (getNumOfPeople(slices,maxSlices) >= nPeople ){
return maxSlices;
}
maxSlices--;
}
return 0;
}
private static int getNumOfPeople(List<Integer> slices, int maxSlices) {
int res = 0;
for (Integer i : slices){
res += (i/maxSlices);
}
return res;
}
private static int getSumOfSlices(List<Integer> slices) {
int result = 0;
for (Integer i : slices){
result += i;
}
return result;
}
}
I might be missing something, but this seems to be a straightforward solution. It's runtime is O(n) where n is the number of pies.
def getMaxSlices(pieSlices, nPeople):
person= 0
serving = 0
for slices in pieSlices:
if slices >= nPeople:
answer += 1
else:
person += slices
if person >= nPeople:
person %= nPeople
answer += 1
return answer
public int getMaxSlices(List<Integer> pieSlices, int nPeop) {
int bounded_sum = 0;
if (pieSlices.size() == 0 || nPeop <= 0) return 0;
for(i=0;i<pieSlices.size();i++){
if(pieSlices[i] < 0) continue;
bounded_sum += min(nPeop,pieSlices[i]);
}
int results = bounded_sum%nPeop;
return resulst;
}
I agree with above author - should be pies > nPeople (at least 1 pie per person)
Than we select from pies list amount of pies == nPeople with the maximum number of slices.
The answer would be: the maximum number of slices one could have from one pie is == the lowest number of slices among sorted pies with highest slices.
## python
import heapq
pies = [2, 7, 8, 22]
persons = 3
if len(pies) < persons:
print('We could not serve %s with %s pies' % (persons, pies))
else:
max_pieces = heapq.nlargest(persons, pies) # [22, 8, 7]
print('Max pieces from one pie %s every %s person could have' % (max_pieces[-1], persons))
Using the smallest pieslices might give you a wrong answer. See last two test cases. Use largest pieslice. Use binary search over that.
#include <algorithm>
/**
* Method to check whether iCount slices can be distributed to iNPeople.
* T = O(N) where N i the number of slices.
*/
bool canDistribute(vector<int> iSlices, int iNPeople, int iCount)
{
int sum=0;
for (vector<int>::const_iterator itr=iSlices.begin(); itr!= iSlices.end(); ++itr)
{
sum += (*itr)/iCount;
if (sum >= iNPeople)
return true;
}
return false;
}
/**
* Method to determine the number of slices that each person can get.
* Uses binary search on the canDistribute method.
* T = O(N * log(K)) where is N is the number of slices and K is the number of slices in the maximum pie.
*/
int getMaxSlices(vector<int> iSlices, int nPeople)
{
int m= *(max_element(iSlices.begin(), iSlices.end()));
if (canDistribute(iSlices, nPeople, m))
return m;
int low = 0, high = m, mid=(low+high)/2, prevMid=-1;
while(mid != prevMid)
{
if (canDistribute(iSlices, nPeople, mid))
low = mid;
else
high = mid;
prevMid = mid;
mid = (low + high)/2;
}
return mid;
}
int main(int argc, char *argv[])
{
int v1[] ={3, 4, 5, 6};
vector<int> sl1(v1, v1+4);
assert(3 == getMaxSlices(sl1, 5));
int v2[] = {10, 10, 10, 10, 1};
vector<int> sl2(v2, v2+5);
assert(5 == getMaxSlices(sl2, 8));
int v3[] = {50, 50, 3};
vector<int> sl3(v3, v3+3);
assert(25 == getMaxSlices(sl3, 3));
return 0;
}
If N = number of pies, and K = number of people, this solution is
O(N + K lg N) in time, and O(N) in space
I am fairly certain this is a near optimal solution. It also works for cases that many of the other solutions don't seem to work for, such as when you have more people than pies
import heapq
""" This is a solution to, you have K people and N pies. each pie has a different number
of slices. each person can only take from 1 pie. find the number of slices that the person
who gets the least slices will get. Maximize that number
each person can only take integer number of slices
The solution to this problem uses a greedy algorithm, and a heapq to keep track of
which pie has the most slices available if 1 more person joins that pie
it runs in O(N + K lgN) time where
N = time to heapify the pies
K = time to loop through each person with the greedy algorithm
lg N = time to siftup each pie in the heap after a new person consumes from it
it uses O(N) space, to store extra info about each pie
"""
def getslices(num_people,pies):
if (num_people == 0 or len(pies) == 0):
return 0
""" use a greedy algorithm to get the number of slices per person"""
pie_info = []
# generate a max heap (not a min heap which is default in python)
heapq._heapify_max(pies)
pie_info = []
for pie in pies:
# store this information in each pie
# number of slices per person if we add 1 more person
# number of slices in this pie total
# number of people currently consuming this pie
pie_info.append([pie,pie,0])
min_slices = float('inf')
for i in range(0,num_people):
pie = pie_info[0]
# add 1 more person to this pie
pie[2] = pie[2] + 1
# number of slices everyone currently gets
current_slices = int(pie[1] / pie[2])
# number of slices people will get if another person joins
pie[0] = pie[1] / (pie[2]+1.0)
# see if this is the new min number of slices
if (current_slices < min_slices):
min_slices = current_slices
# this might not be the best pie for the next person anymore
# sift it up in the heap
heapq._siftup_max(pie_info,0)
for pie in pie_info:
print pie
return min_slices
if __name__ == "__main__": # main program
num_people = 7
pies = [10,3, 5,2]
num_slices = getslices(num_people,pies)
print
print
print
print '***** ',num_slices
#include<bits/stdc++.h>
using namespace std;
#define MAX 100005
int a[MAX],b[MAX];
int n;
int check(int x){
for(int i = 0;i<n;i++)
b[i] = a[i];
int y = n;
int i = 0;
while(y>0 && i<n)
{
if(b[i]>=x)
{
b[i]-=x;
y--;
}
else{
i++;
}
}
return y==0;
}
int bs(int start,int end)
{
if(start>end)
return 0;
if(start==end){
if(check(start))
return start;
else
return 0;
}
int mid = (start) + (end-start)/2;
//cout<<mid<<endl;
if(check(mid)){
//cout<<check(mid+1)<<endl;
if(mid+1<=end && check(mid+1))
return bs(mid+1,end);
return mid;
}
else
return bs(start,mid-1);
}
int main(){
cin>>n;
int maxi = 0;
for(int i = 0;i<n;i++)
{
cin>>a[i];
maxi = max(maxi,a[i]);
}
//cout<<check(8)<<endl;
cout<<bs(0,maxi)*n<<endl;
return 0;
}
def getMaxSlices(pieSlices, nPeople):
if len(pieSlices)==0 or nPeople==0: return None
tempSlices = sorted(pieSlices, reverse=True)
estPies = sum(tempSlices)//nPeople
for i in range(estPies, 0, -1):
k = nPeople
for j in range(len(pieSlices)):
k = k-pieSlices[j]//i
if k==0: return i
return None
p = 4
pieSlices = [x+2 for x in range(p)]
print(pieSlices)
people = 2
res = getMaxSlices(pieSlices, people)
print(res)
def getMaxSlices(pieSlices, nPeople):
if len(pieSlices)==0 or nPeople==0: return None
tempSlices = sorted(pieSlices, reverse=True)
estPies = sum(tempSlices)//nPeople
for i in range(estPies, 0, -1):
k = nPeople
for j in range(len(tempSlices)):
k = k-tempSlices[j]//i
if k==0: return i
return None
p = 4
pieSlices = [x+2 for x in range(p)]
print(pieSlices)
people = 2
res = getMaxSlices(pieSlices, people)
print(res)
#include "stdafx.h"
#include <vector>
using namespace std;
int getMaxSlices(const vector<int> & pies, int numberOfPeople) {
int totalSlices = 0;
auto itr = pies.cbegin();
while(itr != pies.cend()) {
totalSlices += *itr;
++itr;
}
int maxSlices = totalSlices /numberOfPeople;
while(maxSlices > 0) {
auto itr = pies.cbegin();
int peopleWhoGotSlices = 0;
while(itr != pies.cend()) {
peopleWhoGotSlices += *itr / maxSlices;
++itr;
}
if(peopleWhoGotSlices >= numberOfPeople) {
return maxSlices;
}
--maxSlices;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
vector<int> pies;
pies.push_back(8);
pies.push_back(10);
pies.push_back(12);
pies.push_back(14);
pies.push_back(16);
for(int i =1; i<=20;i++) {
int maxSlices = getMaxSlices(pies, i);
printf("%d\n", maxSlices);
}
getchar();
return 0;
}
static class Pizza{
int slices;
int slicesPerPerson;
int peopleAlloted=0;
Pizza(int slices){
this.slices = slices;
this.slicesPerPerson= slices;
}
}
private static int findMaxSlices(List<Pizza> pizzas, int numPeople) {
if(pizzas.size() ==1){
return pizzas.get(0).slices/numPeople;
}
PriorityQueue<Pizza> slicesMaxHeap = new PriorityQueue<>((Pizza a, Pizza b) -> -Integer.compare(a.slicesPerPerson, b.slicesPerPerson));
slicesMaxHeap.addAll(pizzas);
int minSlices = Integer.MAX_VALUE;
for (int people = 0; people < numPeople; people++) {
Pizza maxSlices = slicesMaxHeap.remove();
Pizza maxSlicesForSec = slicesMaxHeap.remove();
int updatedSlices = maxSlices.slices / (maxSlices.peopleAlloted+1);
int updatedSlices2 = maxSlicesForSec.slices / (maxSlicesForSec.peopleAlloted+1);
if(updatedSlices >= updatedSlices2){
maxSlices.peopleAlloted++;
maxSlices.slicesPerPerson = maxSlices.slices/ maxSlices.peopleAlloted;
minSlices = Math.min(minSlices,maxSlices.slicesPerPerson);
}else{
maxSlicesForSec.peopleAlloted++;
maxSlicesForSec.slicesPerPerson = maxSlicesForSec.slices/ maxSlicesForSec.peopleAlloted;
minSlices = Math.min(minSlices,maxSlicesForSec.slicesPerPerson);
}
slicesMaxHeap.add(maxSlices);
slicesMaxHeap.add(maxSlicesForSec);
}
return minSlices;
}
static class Pizza{
int slices;
int slicesPerPerson;
int peopleAlloted=0;
Pizza(int slices){
this.slices = slices;
this.slicesPerPerson= slices;
}
}
private static int findMaxSlices(List<Pizza> pizzas, int numPeople) {
if(pizzas.size() ==1){
return pizzas.get(0).slices/numPeople;
}
PriorityQueue<Pizza> slicesMaxHeap = new PriorityQueue<>((Pizza a, Pizza b) -> -Integer.compare(a.slicesPerPerson, b.slicesPerPerson));
slicesMaxHeap.addAll(pizzas);
int minSlices = Integer.MAX_VALUE;
for (int people = 0; people < numPeople; people++) {
Pizza maxSlices = slicesMaxHeap.remove();
Pizza maxSlicesForSec = slicesMaxHeap.remove();
int updatedSlices = maxSlices.slices / (maxSlices.peopleAlloted+1);
int updatedSlices2 = maxSlicesForSec.slices / (maxSlicesForSec.peopleAlloted+1);
if(updatedSlices >= updatedSlices2){
maxSlices.peopleAlloted++;
maxSlices.slicesPerPerson = maxSlices.slices/ maxSlices.peopleAlloted;
minSlices = Math.min(minSlices,maxSlices.slicesPerPerson);
}else{
maxSlicesForSec.peopleAlloted++;
maxSlicesForSec.slicesPerPerson = maxSlicesForSec.slices/ maxSlicesForSec.peopleAlloted;
minSlices = Math.min(minSlices,maxSlicesForSec.slicesPerPerson);
}
slicesMaxHeap.add(maxSlices);
slicesMaxHeap.add(maxSlicesForSec);
}
return minSlices;
}
public static int getMaxSlices(List<Integer> pieSlices, int nPeople){
//first i want to turn both into a map so i can ensure duplicates get found
HashMap<Integer, Integer> piesAndSlides = new HashMap<Integer, Integer>();
//add the pies and their slies
int i = 0;
int totalSlices= 0;
int maxSlides = 0;
int minSlides = pieSlices.get(0);
for(Integer slices: pieSlices){
piesAndSlides.put(i, slices);
if (slices>maxSlides){
maxSlides = slices;
if(slices<minSlides){
minSlides = slices;
}
}
i++;
totalSlices += slices;
}
double piesPerPerson = (double) pieSlices.size()/nPeople;
//so we know the ratio of pies per person.
//so now we can go through each pie, and hand out those slices * piesPerPerson.
//we can't hand out more than the minSlices divided by the perPerPerson Ratio
//so... hand out ==
int handout = (int) (minSlides * piesPerPerson);
System.out.println("max slices per person:" + (handout));
return handout;
}
Let's assume that people are in queue. once person get one slice he will move to end of the queue. So we can say that slice will be distributed in following way.
Say there are 3 people A,B and C. then distribute slices in this sequence A,B,C,A,B,C,A,B,C........... and maintain counter of number of distributed slices at the end perform int(counter/nPeople) which will be ans.
Observation: if number of slices is >nPeople then we can assign slice to each person only once, So we can add nPeople in counter directly.
Python code
def getMaxSlieces(pieSlieces, nPeople):
sliece_count = 0
for ps in pieSlieces:
sliece_count += min(nPeople, ps)
return int(sliece_count/nPeople)
First, find out all pies with more slices than N. Each such pie will just add 1 to the final answer and the extra slices are of no use.
Then, you can just sum up the slices of the rest, divide that by N and that's how many slices each person can get off of those. Imagine people forming a line, grab a slice from the current pie and move to the back of the line. No one will get more than one slice from the same pie because none will last for N people.
This seems to be a trick question. As soon as you see the key point it's very obvious. (There's actually a more rigorous proof to step one for why those pies can't contribute more than 1 to the final answer, but I'm too tired to type.)
package test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SliceOfPie {
public static void main(String[] args) {
// TODO Auto-generated method stub
List<Integer> pieSlices = new ArrayList<Integer>();
pieSlices.addAll(Arrays.asList(3,1,6,4,3,3,3,3));
System.out.println("Max slice=" + getMaxSlices(pieSlices, 4));
}
public static int getMaxSlices(List<Integer> pieSlices, int n) {
int slice = 0;
int sumOfSlices = 0;
for (int i = 0; i < pieSlices.size(); i++) {
if (pieSlices.get(i) >= n) {
slice++;
} else {
sumOfSlices +=pieSlices.get(i);
}
}
return slice + sumOfSlices / n;
}
}
package test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SliceOfPie {
public static void main(String[] args) {
// TODO Auto-generated method stub
List<Integer> pieSlices = new ArrayList<Integer>();
pieSlices.addAll(Arrays.asList(3,1,6,4,3,3,3,3));
System.out.println("Max slice=" + getMaxSlices(pieSlices, 4));
}
public static int getMaxSlices(List<Integer> pieSlices, int n) {
int slice = 0;
int sumOfSlices = 0;
for (int i = 0; i < pieSlices.size(); i++) {
if (pieSlices.get(i) >= n) {
slice++;
} else {
sumOfSlices +=pieSlices.get(i);
}
}
return slice + sumOfSlices / n;
}
}
public int getMaxSlices(List<Integer> pieSlices, int nPeople) {
// Must be at least 1 pie per person
if (pieSlices.size() < nPeople) {
return 0;
}
// Sort the values (smallest to biggest)
Collections.sort(pieSlices);
int maxPieSize = pieSlices.get(pieSlices.size() - nPeople);
return (maxPieSize > nPeople) ? nPeople : maxPieSize;
}
public int getMaxSlices(List<Integer> pieSlices, int nPeople) {
// Must be at least 1 pie per person
if (pieSlices.size() < nPeople) {
return 0;
}
// Sort the values (smallest to biggest)
Collections.sort(pieSlices);
int maxPieSize = pieSlices.get(pieSlices.size() - nPeople);
return (maxPieSize > nPeople) ? nPeople : maxPieSize;
}
I think that a solution could be as follows (IF, as Denis said, the correct question says "Did not get slices from more than one pies"):
- Klaus O. May 09, 2016We start by taking the smallest number of slices s from the list (which is the max number of slices a person can get). For example, if the list = {8,15,12,10} then s = 8. Let's also assume that nPeople = 15.
Having arrived at this value for s (8) means that we could give each of these persons a maximum of 8 slice(s); any number below that would be valid but we need to calculate which of these numbers answers the question.
To get an O(logN) solution I would create an array of integers S with size = s. Applying the concept of the binary search algorithm we start by dividing s by 2 and look if this number of slices is the correct one. So, if we divide each item from the list by s/2, i.e. 4, the first element gives us 2 slices, the 2nd 3 and so on (results: 2, 3, 3, 2) and if we sum all of them we get 10, which means that if we give each person 4 slices, only 10 persons would get pie. As this result is less than we need, we can discard the upper half of slices (5, 6, 7 and 8) as they will give us even lower results. Before going to the next step, we store this value under S[4] = 10.
Now, we look in the lower half starting with our current s and we divide it further by 2 which gives us 2. The results for this s would be (4, 7, 6, 5) which summed up give us 22, and, as this result is more than we need, we can discard the lower half of slices (1 and 2) as they will give us even higher results. Once again, we store this result in our array: S[2] = 22.
The number left in this example is 3. If s = 3 the results would be (2, 5, 4, 3) which summed up give us 14, which will only feed 14 persons, not what we need.
So the only result that satisfies the problem in this example is 2, two slices for each person will give each person the same amount of slices not from more than one pie. 3 slices would only feed 14 persons and 4 would feed only 10.
What do you think about this approach?