Solving JS Algorithm Problem with Hashes
The problem reads:
Given a list of the scores of different students, items, where items[i] = [IDi, scorei] represents one score from a student with IDi, calculate each student's top five average.
Return the answer as an array of pairs result, where result[j] = [IDj, topFiveAveragej] represents the student with IDj and their top five average. Sort result by IDj in increasing order.
A student’s top five average is calculated by taking the sum of their top five scores and dividing it by 5 using integer division.
Input: items = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]Starting point:
const highFive = (items) => {
};
Step #1: Based on the problem, we note that items is an array of students with a key-value pair representing their student id and their score. We also note that there can be multiple scores that are related to a individual student. After acknowledging this, we see that the answer will need to be shown as an array titled result, which will be the student’s id along with the average score from their top five grades.
In regards to organizing the averages (avgs) of the students, we will show it as a hash because we can use it to store other objects (student’s averages in this case) and we can look up a value from a hash using a key.
const highFive = (items) => {
const avgs = {}
const result = []
};
Step #2: Next we will need to map the items array in order to get the individual students and their respective test scores. The map function gets the student and score key-value pair from within the items array.
[ 1, 91 ]
[ 1, 92 ]
[ 2, 93 ]
[ 2, 97 ]
[ 1, 60 ]
[ 2, 77 ]
[ 1, 65 ]
[ 1, 87 ]
[ 1, 100 ]
[ 2, 100 ]
[ 2, 76 ]
From there we will use our if statement and strict equality operator to check if the student is undefined. If so, then the student id is represented by the value (student[1]) or score. This should be the case since we know that no student can receive a score if they don’t have an id. If not, then we will push the score to the student with the same id.
items.map(student => {
if (avgs[student[0]] === undefined) {
avgs[student[0]] = [student[1]]
} else {
avgs[student[0]].push(student[1])
console.log(avgs)
}
})
After console logging the avgs hash we get:
{ ‘1’: [ 91, 92 ] }
{ ‘1’: [ 91, 92 ], ‘2’: [ 93, 97 ] }
{ ‘1’: [ 91, 92, 60 ], ‘2’: [ 93, 97 ] }
{ ‘1’: [ 91, 92, 60 ], ‘2’: [ 93, 97, 77 ] }
{ ‘1’: [ 91, 92, 60, 65 ], ‘2’: [ 93, 97, 77 ] }
{ ‘1’: [ 91, 92, 60, 65, 87 ], ‘2’: [ 93, 97, 77 ] }
{ ‘1’: [ 91, 92, 60, 65, 87, 100 ], ‘2’: [ 93, 97, 77 ] }
{ ‘1’: [ 91, 92, 60, 65, 87, 100 ], ‘2’: [ 93, 97, 77, 100 ] }
{ ‘1’: [ 91, 92, 60, 65, 87, 100 ], ‘2’: [ 93, 97, 77, 100, 76 ] }
This shows how mapping works, by checking each key-value pair until there are no more.
Now we have the students and their scores organized but, now we need to sort the top five scores from each student.
Step #3: We then use a for loop and in operator to assign the student id as the index within the avgs hash and then we set it to equal to the sorted hash and return in descending order. Next, we would want to just get the top 5 scores and if the student has 6 scores, we would need to remove the lowest score from the list. To do that we set the avgs hash with the studentId equal to the same but using slice to remove the lowest score.
for (let studentId in avgs) {
// find top 5
avgs[studentId] = avgs[studentId].sort((a, b) => {
return b — a
})
avgs[studentId] = avgs[studentId].slice(0, 5)
Console logging avgs[studentId] we get:
[ 100, 92, 91, 87, 65 ]
[ 100, 97, 93, 77, 76 ]
Step #4: Now since we have the top 5 scores from each student, we then must calculate the average of those 5 scores. To do this we will use the .reduce() function to find the average by adding each score within the array until we get one sum.
Console logging avgs[studentId] we get:
For student 1 : 435
For student 2 : 443
// find average
avgs[studentId] = avgs[studentId].reduce((accumulator, currentValue) =>{
return accumulator + currentValue
})
After that we need to divide the total by the number of test scores from each student (in this case 5 tests). So we set the amounts within the student id array to equal to itself divided by 5 and set within the Math.floor() function in order to return the largest integer less than or equal to a given number.
avgs[studentId] = Math.floor(avgs[studentId] / 5)
For student 1 : 87
For student 2 : 88
Step #5: Lastly we need to push our answer into the result array that we created at the start. To do so we type the array result then the push method and within the parenthesis we set the array by studentId followed by the average score from within our studentId array that was also within our avgs hash. Finally outside the for loop function, we return the result and it should return an array of the two students with their overall top 5 average.
// for result format
result.push([studentId, avgs[studentId]])
}
return result
}
Answer:
[[1,87],[2,88]]
