Five Star Seller Maximum Average Pass Ratio Amazon OA 2023

Five Star Seller Maximum Average Pass Ratio Solution

There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array classes, where classes[i] = [passi, totali]. You know beforehand that in the ith class, there are totali total students, but only passi number of students will pass the exam.

You are also given an integer extraStudents. There are another extraStudents brilliant students that are guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents students to a class in a way that maximizes the average pass ratio across all the classes.

The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided by the number of the classes.

Return the maximum possible average pass ratio after assigning the extraStudents students. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2

Output: 0.78333

Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.

Example 2:

Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4

Output: 0.53485

Constraints:

  • 1 <= classes.length <= 105
  • classes[i].length == 2
  • 1 <= passi <= totali <= 105
  • 1 <= extraStudents <= 105

SOLUTION

Priority Queue and Greedy

There are few incorrect approaches:

  1. Choosing the smallest class size
  2. Choosing the smallest pass size
  3. Choosing the least pass ratio

Instead, the correct approach is:

Find the difference, namely the delta.

For example, even though 1/2 and 10/20 has the same ratio. However, 1/2’s delta is equal to (1+1)/(2+1)-1/2, which is much greater than (10+1)/(20+1)-10/20.

Therefore, we always greedily select the one with the greatest delta.

We can acheive this using a max heap. In C++, we can use the priority queue.

Program: Five Star Seller Maximum Average Pass Ratio Solution in C++

struct cmp{
    bool operator()(pair<int,int> a, pair<int,int> b){
        double ad = (a.first+1)/(double)(a.second+1) - (a.first)/(double)a.second;
        double bd = (b.first+1)/(double)(b.second+1) - (b.first)/(double)b.second;
        return ad < bd;
    }
};
class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        double acc = 0;
        priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> que;
        for(vector<int> i: classes)
            que.push(make_pair(i[0],i[1]));
        while(extraStudents--){
            pair<int,int> cur = que.top(); que.pop();
            cur.first++, cur.second++;
            que.push(cur);
        }
        while(!que.empty()){
            pair<int,int> cur = que.top(); que.pop();
            acc += cur.first / (double) cur.second;
        }
        return acc / (double) classes.size();
    }
};

Program: Five Star Seller Maximum Average Pass Ratio Solution in C++

At a glance the obvious choice seems like picking the class with least pass ratio each time and adding a genius student. But this only brings the lower ratio scores near the average, doesn’t try to increase the max observed score or decide where to add a student in case two classes have the same pass ratio.

So to answer the above question, we use the delta change increment in average ratio score.

The class that can show the max change is picked and a student is added there.

This way a class with max promise is always picked.

TC: O(nlogn + klogn + nlogn) ~ O((n+k)logn), n: no. of classes

class Solution {
public:
    // Computes the change seen when a new student is added to current class strength
    double delta_increment(int &pass, int &total) {
        return (double) (pass + 1) / (total + 1) - (double)pass / total;    
    }
    
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        // Max heap wrt to the delta increment each class pass ratio can achieve
        priority_queue< tuple<double, int, int>, vector< tuple<double, int, int> >> max_heap;
        
        for(auto class_score: classes) 
            max_heap.emplace(make_tuple(delta_increment(class_score[0], class_score[1]),
                                         class_score[0], class_score[1]));
        
        // Add the genius students to those classes where the ratio increment is max
        while(extraStudents--) {
            auto max_delta_class = max_heap.top();
            max_heap.pop();
            auto [delta, pass, total] = max_delta_class;
            ++pass, ++total;
            max_heap.emplace(make_tuple(delta_increment(pass, total), pass, total));
        }
        
        // Find the total avg class pass ratio
        double avg_pass = 0;
        while(!max_heap.empty()) {
            auto max_delta_class = max_heap.top();
            max_heap.pop();
            avg_pass += (double)get<1>(max_delta_class) / get<2>(max_delta_class);
        }
        return avg_pass / classes.size();
    }
};

Program: Five Star Seller Maximum Average Pass Ratio Solution in Java

Approach (Greedy): Out of all the classes, choose that which will affect the score most. It means that, we have to choose maximum of all:

(classes[i][0] + 1) / (class[i][1] + 1) – classes[i][0] / classes[i][1] // for all i

It first seems like can be done easily in O(n2), but we can reduce it to O(nlogn) using PriorityQueue (max heap).

Time Complexity: O(elogn), where e = no. of extra students

Space Complexity: O(n)

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<Pair> pq = new PriorityQueue<>((x, y) -> Double.compare(y.effect, x.effect));
        
        for(int i = 0; i < classes.length; ++i) {
            if(classes[i][0] == classes[i][1])
                continue;
            
            double effect = -(double)(classes[i][0]) / (double) (classes[i][1]) + (double)(classes[i][0] + 1) / (double) (classes[i][1] + 1);
            
            pq.add(new Pair(effect, i));
        }
        
        while(pq.size() > 0 && extraStudents-- > 0) {
            Pair p = pq.remove();
            int i = p.idx;
            ++classes[i][0];
            ++classes[i][1];
            
            double effect = -(double)(classes[i][0]) / (double) (classes[i][1]) + (double)(classes[i][0] + 1) / (double) (classes[i][1] + 1);
            
            pq.add(new Pair(effect, i));
        }
        
        double ans = 0;
        
        for(int[] a : classes) {
            double val = (double) (a[0]) / (double) (a[1]);
            ans += val;
        }
        
        return ans / (double) (classes.length);
    }
    
    class Pair {
        double effect;
        int idx;
        
        Pair(double effect, int idx) {
            this.effect = effect;
            this.idx = idx;
        }
    }
}

Program: Five Star Seller Maximum Average Pass Ratio Solution in Python

In iterative allocations of extra students, we note the following:

  1. The gain in class average (mu) from an extra students for any given class can be computed in iterative fashion with respect to iterative class sizes of k-1 and k.
    mu_{k} = mu_{k-1} + ( 1 – mu_{k-1} ) / k
  2. The maximum iterative gain in overall average of class averages corresponds to the greatest class average gain derived in step 1 scaled by n (the total number of classes).
  3. We can use a heap to quickly derive the maximum iterative gain in step 1 in log n time per iteration.

Complexity Analysis:

O(e log n); e == extraStudents; n == len(classes);

from heapq import *
class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        computeGain = lambda p, t: (1 - (p / t)) / (t + 1)
        R = [(-computeGain(p, t), p, t) for p, t in classes]
        heapify(R)
        for x in range(extraStudents):
            _, p, t = heappop(R)
            p += 1
            t += 1
            heappush(R, (-computeGain(p, t), p, t))
        return sum(map(lambda x: x[1] / x[2], R)) / len(classes)

Program: Five Star Seller Maximum Average Pass Ratio Solution in Python

We need to keep assigning the remaining extra students to the class which can experience the greatest impact.

Let see an example below, if we have following clasess – [[2,4], [3,9], [4,5], [2,10]], then the impact of assignment students to each class can be defined as,

# In simple terms it can be understood as follows,
currentRatio = passCount/totalCount
expectedRatioAfterUpdate = (passCount+1)/(totalCount+1)
impact = expectedRatioAfterUpdate - currentRatio
			
OR
# Formula to calculate impact of assigning a student to a class
impacts[i] = (classes[i][0]+1) / (classes[i][1]+1) - classes[i][0]/classes[i][1]
i.e.
impacts[0] -> (4+1)/(2+1)-4/2 
impacts[1] -> (3+1)/(9+1)-3/9 
.
.
etc.

And, once we assign a student to a class, then we need the class with “next” greatest impact. We know that heap is perfect candidate for scenarios in which you need to pick the least/greatest of all the collections at any point of time.

Hence, we can leverage that to fetch the greatest impacts in all the cases.

Note: in below code we have negated (observe – sign ), because by default python heaps are min heaps. Hence, it’s sort of a workaround to make our logic work 🙂

class Solution:
	def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
		
		n = len(classes)
		
		impacts = [0]*n
		minRatioIndex = 0
		
		# calculate and store impacts for each class in form of tuples -> (-impactValue, passCount, totalCount)
		for i in range(n):
			passCount = classes[i][0]
			totalCount = classes[i][1]
			
			# calculate the impact  for class i
			currentRatio = passCount/totalCount
			expectedRatioAfterUpdate = (passCount+1)/(totalCount+1)
			impact = expectedRatioAfterUpdate - currentRatio
			
			impacts[i] = (-impact, passCount, totalCount)  # note the - sign for impact
			
		heapq.heapify(impacts)
		
		while(extraStudents > 0):
			# pick the next class with greatest impact 
			_, passCount, totalCount = heapq.heappop(impacts)
			
			# assign a student to the class
			passCount+=1
			totalCount+=1
			
			# calculate the updated impact  for current class
			currentRatio = passCount/totalCount
			expectedRatioAfterUpdate = (passCount+1)/(totalCount+1)
			impact = expectedRatioAfterUpdate - currentRatio
			
			# insert updated impact back into the heap
			heapq.heappush(impacts, (-impact, passCount, totalCount))
			extraStudents -= 1
		
		result = 0
			
		# for all the updated classes calculate the total passRatio 
		for _, passCount, totalCount in impacts:
			result += passCount/totalCount
			
		# return the average pass ratio
		return result/n

Amazon OA 2023 Questions with Solution

  1. Shopping Patterns Solution Amazon OA 2023
  2. Reorder Data in Log Files Solution Amazon OA 2023
  3. Top K Frequent Words Solution Amazon OA 2023
  4. Trees Height Solution Amazon OA SDE 2023
  5. Counting Binary Substrings Amazon OA 2023
  6. Grid Connections Amazon OA 2023
  7. Shipment Imbalance Amazon OA 2023
  8. Max Profit Amazon OA 2023
  9. Find Lowest Price Amazon OA 2023
  10. Decode String Frequency Amazon OA 2023
  11. Simple Cipher Amazon OA 2023
  12. Valid Discount Coupons Amazon OA 2023 Solution
  13. Count Maximum Teams Amazon OA 2023
  14. Minimum Coin Flips Amazon OA 2023
  15. Max Average Stock Price Amazon OA 2023 Solution
  16. Robot Bounded In Circle Amazon OA 2023
  17. Shopping Options Amazon OA 2023 Solution
  18. Fill The Truck Maximum Units on a Truck Amazon OA Solution
  19. Maximize Score After N Operations Number Game Solution Amazon OA 2023
  20. Slowest Key Amazon OA 2023 Solution
  21. Split String Into Unique Primes Amazon OA 2023 Solution
  22. Storage Optimization Amazon OA 2023 Solution
  23. Minimum Difficulty of a Job Schedule Amazon OA 2023 Solution
  24. Autoscale Policy Utilization Check Amazon OA 2023
  25. Optimal Utilization Solution Amazon OA 2023
  26. Merge Two Sorted Lists Solution Amazon OA 2023
  27. Two Sum Unique Pairs Solution Amazon OA 2023
  28. Amazon Music Pairs Amazon OA 2023 Solution
  29. Class Grouping Amazon OA 2023 Solution
  30. Find Max products Amazon OA 2023 Solution
  31. Get encrypted number Amazon OA 2023 Solution
  32. Find Total Imbalance Amazon OA 2023 Solution
  33. Find Total Power Amazon OA 2023 Solution

2 thoughts on “Five Star Seller Maximum Average Pass Ratio Amazon OA 2023”

Comments are closed.