Maximum Area Serving Cake Google OA 2023 Solution
Given an array containing the radii of circular cakes and the number of guests, determine the largest piece that can be cut from the cakes such that every guest gets a piece of the cake with the same area. It is not possible that a single piece has some part of one cake and some part of another cake and each guest is served only one piece of cake.
Example 1:
Input: radii = [1, 1, 1, 2, 2, 3], numberOfGuests = 6.
Output: 7.0686
Explanation:
- Reason being you can take the area of the cake with a radius of 3, and divide by 4. (Area 28.743 / 4 = 7.0686)
- Use a similary sized piece from the remaining cakes of radius 2 because total area of cakes with radius 2 are > 7.0686
Example 2:
Input: radii = [4, 3, 3], numberOfGuests = 3
Output: 28.2743
Example 3:
Input: radii = [6, 7], numberOfGuests = 12
Output: 21.9911
SOLUTION
Program: Maximum Area Serving Cake solution in Python
def maximumAreaServingCake(radii, numberOfGuests):
areas = [math.pi * r * r for r in radii]
def possible(x):
k = 0
for a in areas:
k += a // x
if k >= numberOfGuests:
return True
return False
l, r = 0, max(areas)
while l + 1e-5 <= r:
x = (l + r) / 2
if possible(x):
l = x
else:
r = x
return round(x, 4)
# Example 1.
radii = [ 1, 1, 1, 2, 2, 3]
numberOfGuests = 6
print(maximumAreaServingCake(radii, numberOfGuests))
# Output: 7.0686
# Example 2.
radii = [4, 3, 3]
numberOfGuests = 3
print(maximumAreaServingCake(radii, numberOfGuests))
# Output: 28.2743
# Example 3.
radii = [6, 7]
numberOfGuests = 12
print(maximumAreaServingCake(radii, numberOfGuests))
# Output: 21.9911Program: Maximum Area Serving Cake solution in C++
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
double maximum_serving_area(vector<int> v,int k){
double l=0,m=0,x;
vector<double> A;
for(int i=0;i<v.size();i++) {
x=(double)v[i]*3.141592*v[i];
m=max(m,x);
A.push_back(x);
}
while(m-l>=1e-5){
x=(l+m)/2;
if(check(x,A,k))
l=x;
else m=x;
}
return x;
}
bool check(double &x ,vector<double>&A,int &K){
int k=0;
for(auto a : A){
k+=a/x;
if(k>=K) return true;
}
return false;
}
};
int main(){
int t,n,h,k;
string s1;
Solution s=Solution();
cin>>t;
while(t--){
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i++) cin>>v[i];
cin>>h;
double res=s.maximum_serving_area(v,h);
cout<<fixed<<setprecision(4)<<res;
cout<<endl;
}
}Program: Maximum Area Serving Cake solution in Python
import math
def getMaxCake(cakes, P):
def getArea(cake):
return math.pi * cake * cake
N = len(cakes)
dp = []
for i in xrange(0, P + 1):
dp.append([0]* (N + 1))
for i in xrange(1, N + 1):
dp[1][i] = getArea(cakes[i - 1])
for p in xrange(2, P + 1):
for i in xrange(1, N + 1):
dp[p][i] = getArea(cakes[i - 1]) / p
for j in xrange(1, P + 1):
dp[p][i] = max(min(dp[p - j][i - 1], getArea(cakes[i - 1]) / j), dp[p][i])
return dp[P][N]
print getMaxCake([ 1, 1, 1, 2, 2, 3], 6)
print getMaxCake([4, 3, 3], 3)
print getMaxCake([6, 7], 12)Related:
- Amazon OA Online Assessment 2022 Questions and Answers
- Microsoft Online Assessment 2021 Questions and Solution
