Page Contents

*Five Star Seller/Maximum Average Pass Ratio Solution*

*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] = [pass`

. You know beforehand that in the _{i}, total_{i}]`i`

class, there are ^{th}`total`

total students, but only _{i}`pass`

number of students will pass the exam._{i}

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.

Also See: Amazon OA Online Assessment 2021 Questions and Answers

**Example 1:**

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

= 2Output:0.78333Explanation: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`

= 4Output:0.53485

**Constraints:**

`1 <= classes.length <= 10`

^{5}`classes[i].length == 2`

`1 <= pass`

_{i}<= total_{i}<= 10^{5}`1 <= extraStudents <= 10`

^{5}

*Solution*

*Solution*

** Program C++**:

*Maximum Average Pass Ratio in C++, Priority Queue and Greedy Solution*

There are few incorrect approaches:

- Choosing the smallest class size
- Choosing the smallest pass size
- 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**.

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 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 Java**:

*Maximum Average Pass Ratio in Java, Priority Queue and Greedy Solution*

**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(n**^{2}**)**, but we can reduce it to **O(nlogn)** using **PriorityQueue (max heap)**.

**Time Complexity:** O(elogn)*, where e = n*o. 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 Python*

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

- 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`

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

Also See: AMCAT Study Materials, Preparation Guide

Also See: Microsoft Online Assessment Questions and Solution

**Amazon Online Assessment Questions:**

*Robot Bounded in Box**Number Game**Find All Combination of Numbers Sum to Target / Shopping Options**Fill the Truck**Music Pairs**Slowest key**Five Star Seller**Split String Into Unique Primes**Storage Optimization**Minimum Difficulty of a Job Schedule**Autoscale Policy, Utilization Check**Optimal Utilization**Merge Two Sorted Lists**Two Sum Unique Pairs**Shopping Patterns**Reorder Data in Log Files**Top K Frequent Words**Trees Height**Counting Binary Substrings Amazon OA Solution**Grid Connections Amazon OA Solution**Shipment Imbalance Amazon OA Solution**Max Profit Amazon OA Solution**Find Lowest Price Amazon OA Solution**Simple Cipher Amazon OA Solution**Decode String Frequency Amazon OA Solution**Valid Discount Coupons Amazon OA Solution**Count Maximum Teams Amazon OA Solution**Minimum Coin Flips Amazon OA Solution**Stock Price Amazon OA Solution*

Bro can you please also give brief explanation of your solutions. That will be of great help.

Yes, we are already working on Amazon OA List by next week all solutions with explanation will be updated.

Thank You,

CYBER GEEK TEAM