Top Scoring Entities — Problem Statement & Solution Guide
Problem Description
You are given an array of entities, where each entity is associated with a score. Return the top 5 entities with the highest scores. If there are more than 5 entities with the same score as the fifth highest score, include only the first 5 entities with that score.
Examples
Input
[['Bob', 3.9], ['David', 3.9], ['Frank', 3.9], ['Alice', 3.8], ['Eve', 3.8], ['Charlie', 3.7], ['George', 3.7]]
Output
[['Bob', 3.9], ['David', 3.9], ['Frank', 3.9], ['Alice', 3.8], ['Eve', 3.8]]
Explanation: Step-by-step: with input of entities and their scores, we first sort the entities based on their scores in descending order. Then, we select the top 5 entities. If there are more than 5 entities with the same score as the fifth highest score, we include only the first 5 entities with that score.
Input
[['Charlie', 3.7], ['George', 3.7], ['Alice', 3.8], ['Eve', 3.8], ['Bob', 3.9]]
Output
[['Bob', 3.9], ['Alice', 3.8], ['Eve', 3.8], ['Charlie', 3.7], ['George', 3.7]]
Explanation: Step-by-step: with input of entities and their scores, we first sort the entities based on their scores in descending order. Then, we select the top 5 entities.
Constraints
- The input list will contain at least 5 students.
- The GPA of each student will be a decimal number between 0 and 4.
- The function should return a list of lists, where each sublist contains the name and GPA of a student.
- If there are more than 5 students with the same GPA as the fifth highest GPA, include only the first 5 students with that GPA.
Optimal Approach & Strategy
The optimized approach involves using a more efficient sorting algorithm like quicksort or mergesort to sort the list of students. This approach has a time complexity of O(n log n) and is more suitable for large lists. Alternatively, a heap data structure can be used to find the top 5 students with the highest GPAs in O(n log k) time complexity.
Brute Force Approach
The brute force approach involves sorting the entire list of students and then selecting the top 5 students with the highest GPAs. This approach is straightforward but may not be efficient for large lists. It can be implemented using a simple sorting algorithm like bubble sort or insertion sort.
Verified Code Solutions
import java.util.Arrays;
import java.util.Comparator;
class Solution {
public static void main(String[] args) {
String[][] entities = { {"Bob", "3.9"}, {"David", "3.9"}, {"Frank", "3.9"}, {"Alice", "3.8"}, {"Eve", "3.8"}, {"Charlie", "3.7"}, {"George", "3.7"} };
Arrays.sort(entities, new Comparator<String[]>() {
@Override
public int compare(String[] o1, String[] o2) {
return Double.compare(Double.parseDouble(o2[1]), Double.parseDouble(o1[1]));
}
});
for (int i = 0; i < 5; i++) {
System.out.println(Arrays.toString(entities[i]));
}
}
}def top_scorers(entities):
# Sort entities based on scores in descending order
sorted_entities = sorted(entities, key=lambda x: x[1], reverse=True)
# Select top 5 entities
top_5 = sorted_entities[:5]
return top_5Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.