Group by Mean

Moderate
0/80
profile
Contributed by
0 upvote
Asked in company
Uber

Problem statement

There are multiple batches in a coding school, batch numbers start from 0 and each batch can have multiple students.

You are given an array of arrays ‘Batch’, where each array denotes the ratings of students in that batch.

You have to group the batches such that all the batches with the same mean rating are part of the same group.

Return an array of arrays where each array denotes a group of batches. All the batches should be sorted in each group, and groups should be sorted according to the first batch number in it (Refer to the example below).

For Example : 
If Batch = { { 1, 2, 3, 4, 5 }, { 4, 2, 4 }, { 2, 3, 4 }, { 1, 1, 1, 1 }, { 0, 2 } }

Then:
Batch [ 0 ] =  { 1, 2, 3, 4, 5 } has mean equal to ( 1 + 2 + 3 + 4 + 5 ) / 5 = 3
Batch [ 1 ] =  { 4, 2, 4 } has mean equal to 3.33
Batch [ 2 ] =  { 1, 1, 1, 1 } has mean equal to 1
Batch [ 3 ] =  { 2, 3, 4 } has mean equal to 3
Batch [ 4 ] =  { 0, 2 } has mean equal to 1

We will group Batch[0] and Batch[3] together, Batch[2] and Batch[4] together and Batch[1] will be grouped alone.

So we will finally return { { 0, 3 }, { 1 }, { 2, 4 } }.
(Note that we sorted the batch numbers inside each group, and then sorted all the groups by the first batch number inside each of them)
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’ denoting the number of batches.

The next line contains N integers, where M[i] denotes the number of students in the ith batch.

The next N lines each contains M[i] integers, each denoting the ratings of the batch member.
Output Format : 
For each test case, print all the groups, with each group containing batch numbers that are to be grouped together, all the groups are printed in a separate line.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 10      
1 <= N <= 200
1 <= M <= 100
0 <= Batch[i][j] <= 10^6

Time limit: 1 sec
Sample Input 1 :
2
5
5 3 4 3 2
1 2 3 4 5
4 2 4 
1 1 1 1
2 3 4
0 2
1
5
1 2 3 4 5
Sample Output 1 :
0 3
1
2 4
0
Explanation For Sample Input 1 :
For test case 1 : 
There are 5 batches, of sizes 5, 3, 4, 3, 2 respectively.
Batch [ 0 ] =  { 1, 2, 3, 4, 5 } has mean equal to ( 1 + 2 + 3 + 4 + 5 ) / 5 = 3
Batch [ 1 ] =  { 4, 2, 4 } has mean equal to 3.33
Batch [ 2 ] =  { 1, 1, 1, 1 } has mean equal to 1
Batch [ 3 ] =  { 2, 3, 4 } has mean equal to 3
Batch [ 4 ] =  { 0, 2 } has mean equal to 1
We will group Batch[0] and Batch[3] together, Batch[2] and Batch[4] together and Batch[1] will be grouped alone.
So we will finally return { { 0, 3 }, { 1 }, { 2, 4 } }.

For test case 2 : 
Batch [ 0 ] =  { 1, 2, 3, 4, 5 } has mean equal to ( 1 + 2 + 3 + 4 + 5 ) / 5 = 3
We will group Batch[0] alone.
So we will finally return { { 0 } }.
Sample Input 2 :
2
2
3 3
1 2 3
3 2 1
2
3 3
1 1 2
1 1 3
Sample Output 2 :
0 1
0
1
Hint

Try grouping all the batches with the same mean value first, sorting the final result by batch numbers can be handled separately.

Approaches (1)
Using Hash-map

Create a hash-map with the key of type ‘double’ and value of type ‘array’. For each batch calculate its mean value and insert the batch number corresponding to its mean in the hash-map.

Finally, make an array of arrays, and iterate through the hash-map and insert each array corresponding to the value in hash-map into the array of arrays (insert each array after sorting it). In the end. Finally, sort the array of arrays and return it.

 

The steps are as follows :

  • Initialize an array of arrays “ans” to store the final answer.
  • Initialize a hash-map “mp” to store the batch numbers corresponding to each mean value.
  • Iterate the input array of arrays ‘batch’, for each batch calculate its mean and insert the batch number corresponding to its mean in the hash-map.  
  • Iterate the hash-map “mp”, insert each array corresponding to a mean value into “ans” after sorting it.
  • Finally, sort “ans”, and return it.
Time Complexity

O( N * M ), where N denotes the number of batches and M denotes the maximum size of the batch.

 

We iterate through each student of every batch to calculate the mean of each batch, there can be ~N*M students in total.

Hence the time complexity is O( N*M ).

Space Complexity

O( N ), where N denotes the number of batches

 

In the worst-case scenario, if all the batches have different mean values, we will end up constructing a hash-map of size ~N.

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
Group by Mean
Full screen
Console