Maximum Area Serving Cake Google OA 2023

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

Maximum Area Serving Cake Google OA
Maximum Area Serving Cake Google OA

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

Program: 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:

Google OA 2023 Questions

Leave a Comment

11 + ten =