Find Maximum Score or the Maximum Average Score of Candidate Scores Given in Two Dim Array

Find maximum score or the maximum average score of candidate scores given in two dim array

What is the reason for reducing the time and space complexity? I strongly believe the brevity and maintainability are more important than the performance.

Since you tagged java-stream, I can suggest you the following approach.

Map<Object, Double> scoreMap = Arrays.stream(scores)
        .collect(
            Collectors.groupingBy(i -> i[0], 
            Collectors.averagingInt(i -> Integer.parseInt(i[1])
        )));

String winner = scoreMap.entrySet().stream()
    .max(Comparator.comparingDouble(e -> e.getValue()))
    .get().getKey().toString();

Thanks to @AndyTurner for the .max(..) parameter suggestion.

2D Array, best average calculator using HashMap

You could store for each student a constant amount of data :

1. the student's name
2. the sum of all the student's marks
3. the number of the student's marks

This will make the space complexity O(m) where m is the number of unique students (instead of your O(n) where n is the number of marks).

For example, you can have a Student class with these 3 properties (and store the data in a List<Student>), or you can have a Map<String,int[]> with the key being the student's name and the value being an array of two elements containing the sum of the marks and the number of marks.

You can construct this data while iterating over the input.

Now you can compute the average for each student and find the highest average.

How do I select the max score from each distinct user in this table?

In Postgres typically the fastest method is to use distinct on ()

select distinct on (user_id) *
from the_table
order by user_id, score desc;

That is definitely a lot faster then any solution using a sub-query with max() and usually still a bit faster then an equivalent solution using a window function (e.g. row_number())

---

^{I used user_id for the column name because user is a reserved word and I strongly recommend to not use that.}

Length of array longer than needed

Because you know the number of students to generated data for, you can use arrays of data for all students:

    int * all_ids = (int *)malloc(sizeof(int)*N);
    double * all_scores = (double *)malloc(sizeof(int)*N);

Then generate data as normal, keeping counts, but assign the data into the all_* arrays:

    for (int i = 0; i < N; i++)
    {
        int id = i;
        double score = round_between_m_to_n(2, 6);

        all_ids[i] = id;
        all_scores[i] = score;

        // if the score is greater than or
        // equal to 4.0...
        if (score >= acceptance_threshhold)
        {
            accepted_scores_count++;
        }
        // ... otherwise they are unaccepted.
        else
        {
            unaccepted_scores_count++;
        }
    }

Because you know the thresholds for distinguishing accepted students, you can split these later.

Now you have all the data, and the numbers of students who were accepted and not accepted. Using this information, you can allocated the arrays for the accepted and unaccepted students:

    int * accepted_ids = (int *)malloc(sizeof(int) * accepted_scores_count);
    double * accepted_scores = (double *)malloc(sizeof(double) * accepted_scores_count);

    int * unaccepted_ids = (int *)malloc(sizeof(int) * unaccepted_scores_count);
    double * unaccepted_scores = (double *)malloc(sizeof(double) * unaccepted_scores_count);

Sort the data into the accepted and unaccepted arrays as you do originally, with the for loop (minus the data generation, since that is done):

    for (int i = 0, j = 0; (i+j) < N;)
    {
        int id = all_ids[i+j];
        double score = all_scores[i+j];

        // if the score is greater than or
        // equal to 4.0...
        if (score >= acceptance_threshhold)
        {
            accepted_ids[i] = id;
            accepted_scores[i] = score;

            i++;
        }
        // ... otherwise they are unaccepted.
        else
        {
            unaccepted_ids[j] = id;
            unaccepted_scores[j] = score;

            j++;
        }
    }

After that, you continue as normal sorting and printing your data. You must remember to free the all_* arrays too.

Finding the average number/grade using data from 4 different arrays in PHP

$TestResult = [
   'Smith' => ['98', '100', '78', '91'],
   'Johnson' => ['67', '85', '92', '88']
];

$Total = array_sum($TestResult['Smith']); // We are getting the array sum.
$Average = $Total/count($TestResult['Smith']); // the average is being calculated.

echo $Average;

https://3v4l.org/U3gCA

You can do this way.

Reference :

• manual count
• source count
• manual array_sum
• source array_sum - source

How to efficiently calculate the top permutations

This problem is actually NP-complete; it is a form of the "Multiple Choice Knapsack Problem" (MCKP).

A simple approach which may work out for you is to generate combinations from the top 1 letter in each slot, then the top 2 letters in each slot, then the top 3, etc., and stop once two iterations in a row produce the same top 20 scores. This isn't guaranteed to be any more efficient than a brute force search, but it's simple to implement and will work well for the "general" case.

---

Related Topics