Question

Goldman Sachs OA 2021 | Set - 38

Answer 1

So, only discussing coding section here:-

 

Q1. Magic Parent
A person X has M different flavor of candies(An array of size M was given with quantity of each candy of particular flavor) and there are N childrens, X has to distribute maximum number of candies among children and every child has the condition that it will only take candies of a particular flavor only ( it is also possible that child may not take any candy at all) and also the other children will get jealous if some children get maximum candies, you have to find the minimum jealously( maximum amount of candy given to a child/children ).

 

T.C:- N=7 M=5
flavors=[2,6,6,4,4];
ans:- 4
Disribution of candies was like :- 2,3,3,4,4,3,3

 

Q2. Fashion Promo Something
There is a scheme in a shop that if you buy a group of 3 dress , you will get the dress with the least price totally free, So the prices of N number of dresses were given , you have to find the maximum discount(least price) you can get. You are free to make group of 3 dresses as you like and you have to buy all the dresses.

 

T.C:- Didn't looked as question was just too easy.

 

Do upvote if you want me to post question from another section as well !!

 

Link to other sections questions (Won't able to post so many images on LC )
https://drive.google.com/drive/folders/1vvVBAT5fjZs7LdxSk-Y0_Of2SyREmjrX

Answer 2

Q2 

public class ThreeVariantSumGreedy {
public static void main(String[] args) {
List problem = Arrays.asList(0, 2, 3, 5, 7, 11);

 

    hasThreeSumOptimal(problem, 80);
}

private static boolean hasThreeSumOptimal(List<Integer> problem, int requiredSum) {
    Collections.sort(problem);
    //greedily pick the first item from last
    for (int j = problem.size() - 1; j >= 2; j--) {
        int remaining = requiredSum - problem.get(j);
        if (remaining > 0) {
            Pair<Integer, Integer> res = twoSumOptimal(problem, remaining, j - 1);
            if (!res.getKey().equals(res.getValue())) {
                //we found a solution
                System.out.println(res.getKey() + " " + res.getValue() + " " + j);
                break;
            }
        }
    }
    return false;
}

//calculates optimal value two numbers.
private static Pair<Integer, Integer> twoSumOptimal(List<Integer> problem, int requiredSum, int endIndex) {
    int i = 0;
    int j = endIndex;

    int returnIndexI = -1;
    int returnIndexJ = -1;

    while (i < j) {  // does not include equals since the condition is such.
        int currentSum = problem.get(i) + problem.get(j);
        int currentDifference = requiredSum - currentSum;
        if (currentDifference == 0) {
            return new Pair(i, j);
        } else if (currentDifference < 0) {
            j--;
        } else {
            returnIndexI = i;
            returnIndexJ = j;
            i++;
        }
    }
    return new Pair(returnIndexI, returnIndexJ);
}

 

}

Answer 3

1)binary search

 

def envylevel(N,M,arr):
    import math
    def helper(k):
        count=0
        for i in arr:
            count+=math.ceil(i/k)

        return count<=N
    l=0
    r=max(arr)
    ans=-1
    while l<=r:
        mid=(l+r)//2
        if helper(mid):
            r=mid-1
            ans=mid
        else:
            l=mid+1
    return (ans)