CareerCup

import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

public class StudentScore {

	public static Map<Integer, Double> getFinalScores(
			List<TestResult> resultList) {

		Map<Integer, PriorityQueue<Integer>> topFives = new TreeMap<>();

		for (TestResult res : resultList) {
			PriorityQueue<Integer> topFive = topFives.get(res.studentId);
			if (topFive == null) {
				topFive = new PriorityQueue<Integer>();
				topFives.put(res.studentId, topFive);
			}
			topFive.add(res.testScore);
			if (topFive.size() > 5) {
				topFive.poll();
			}
		}

		Map<Integer, Double> finalScores = new TreeMap<>();
		for (int id : topFives.keySet()) {
			double total = 0.0;
			for (int score : topFives.get(id)) {
				total += score;
			}
			finalScores.put(id, total / 5.0);
		}

		return finalScores;
	}

	public static void main(String[] args) {
		int[][] scores = { { 2, 78 }, { 2, 89 }, { 2, 97 }, { 2, 92 },
				{ 2, 99 }, { 2, 66 }, { 2, 23 }, { 3, 78 }, { 3, 89 },
				{ 3, 87 }, { 3, 92 }, { 3, 98 }, { 3, 66 }, { 3, 23 } };

		List<TestResult> resultList = new ArrayList<>();
		for (int[] score : scores) {
			resultList.add(new TestResult(score[0], score[1]));
		}

		System.out.println(getFinalScores(resultList));

	}
}

class TestResult {
	int studentId;
	Date testDate;
	int testScore;

	TestResult(int id, int score) {
		studentId = id;
		testScore = score;
	}
}

Use a map containing for each user a min heap with a size of 5. after that calculate for each user. Complexity n * log(5) == O(n)

Use Map + MaxHeap

Link: github.com/techpanja/interviewproblems/tree/master/src/heaps/heap

Assumptions:
1) The student id are in the range (0-max role number for students) with out any gaps.
2) To achieve constant insertion time to the map we use studentId as the key. So we assume that we have a hashmap with initial capacity = max role number for students
3) test scores are in the range of [0-100]

Approach:
Lets say there is an object called TestResult which encapusulates testdate, studentId, testscore. These test results are stored in a hashmap with student id as the key

Map<Integer, List<TestResult> perStudentResults = new HashMap<Integer,List<TestResult>

Before we declare the score per student, heapify the results per student as a max heap. Once made as a max heap, get the max element 5 times and perform the average of the score and display it as the score.

Complexity:
If there are n students p results for each students,
* Insertion to the hashmap for n student records -> O(n*p)
* Heapify operation for p elements can be done in O(p). The heapify operation for n student is again n* O(p) = O(n*p)
* For each student
for i = 1 to 5
* retrieve the max element and rearrange the heap = O(logp)
* Compute the average so far
end
end
Complexity here will be O(n*5logp) = O(nlogp)

* finally the complexity is O(n*p)

import java.util.*;

public class TestResult implements Comparable<TestResult> {

    int studentId;
    Date testDate;
    int testScore;

    TestResult(int id, Date dt, int score) {
        studentId = id;
        testDate = dt;
        testScore = score;
    }

    @Override
    public int compareTo(TestResult o) {
        if (studentId > o.studentId)
            return 1;
        else if (studentId < o.studentId)
            return -1;
        else
            return 0;
    }

    public Map<Integer, Double> getFinalScores(List<TestResult> resultList) {
        Map<Integer, Double> result = new HashMap();
        Collections.sort(resultList);

        int prevId = resultList.get(0).studentId;
        ArrayList scores = new ArrayList();


        System.out.println("Result");
        int len = 0;
        for (TestResult t : resultList) {
            len++;
            if (prevId != t.studentId || resultList.size() == len){
                result.put(prevId, getAverageTopFiveScore(scores));
                System.out.println(prevId + " " + getAverageTopFiveScore(scores));
                prevId = t.studentId;
                scores = new ArrayList();
                scores.add(t.testScore);
            }
            else {
                scores.add(t.testScore);
            }
        }

        return result;
    }

    public double getAverageTopFiveScore(ArrayList<Integer> topFiveScores) {
        Collections.sort(topFiveScores, Collections.reverseOrder());
        int sum = 0;
        for (int i = 0; i < 5; i++) {
            sum += topFiveScores.get(i++);
        }
        return sum / 5;
    }


}

Time Complexity : O(n log n )

Their may be another(cleaner) way.. something like a group by sort, sort by student id and within that sort by the scores....

class TestResult{ 
int studentId; 
Date testDate; 
int testScore; 
} 

public Map<Integer, Double> getFinalScores(List<TestResult> resultList){ 
	// test if input list if null or empty
if(resultList != null || resultList.isEmpty()) {
		// Sort using an O(nlogn) runtime sorting algo
Arrays.sort(resultList, new TestResultComparator());
		Map<Integer, Double> averages = new HashMap<Integer, Double>();
		int count = 0;
		for(int i = 0 ; i<resultLIst.size() ; i++) {
			
if(!averages.contains(resultList.get(i).studentId)) {
				count = 1;
				averages.put(resultList.get(i).studentId, resultList.get(i).testScore);
			} else {
				if(count > 5) {
					continue;
				}
else if(count == 5) {
					int avg = (averages.get(resultList.get(i).studentId) +resultList.get(i).testScore) /5 ;
					averages.put(resultList.get(i).studentId, avg);
					count++;
				} else {
					int acum = averages.get(resultList.get(i).studentId) +resultList.get(i).testScore;
					averages.put(resultList.get(i).studentId, acum);
					count++;
				}
			}
		}
	}
	
	return null;
}

public class TestResultComparator implements Comparator<TestResult> {
	@Override
	public int compareTo(TestResult o1, TestResult o2) {
		if(o1 == o2)
			return 0;
		if(o1.studentId = o2.studentId) {
			return o1.testScore == o2.testScore ? 0 : o1.testScore > o2.testScore? 1 : -1;
		}
		return o1.studentId > o2.studentId ? 1 : -1;
	}

}

The idea is to store information about every student in Map, where key is Student ID. Value of this Map is a special structure where the best 5 results are in PriorityQueue, but other are in some simple collection (like list).

So when we need to add new item we check if PriorityQueue has 5 items. If it has less - just add new item, otherwise we peek top item which is the worse among best 5 and compare it with given. After that we put new item to list or to priority queue (and put in list top heap item)

So add operation takes O(log 5) == O(1) constant time

public class StudentTest {

    public static void main(String[] args) {
        new StudentTest().solve();
    }

    public void solve() {
        StudentRecord sr1 = new StudentRecord("1", 10, new Date());
        StudentRecord sr2 = new StudentRecord("1", 10, new Date());
        StudentRecord sr3 = new StudentRecord("1", 10, new Date());
        StudentRecord sr4 = new StudentRecord("1", 2, new Date());
        StudentRecord sr5 = new StudentRecord("1", 10, new Date());
        StudentRecord sr6 = new StudentRecord("1", 1, new Date());
        StudentRecord sr7 = new StudentRecord("1", 10, new Date());

        StudentRegister studentRegister = new StudentRegister();
        studentRegister.add(sr1);
        studentRegister.add(sr2);
        studentRegister.add(sr3);
        studentRegister.add(sr4);
        studentRegister.add(sr5);
        studentRegister.add(sr6);
        studentRegister.add(sr7);

        System.out.println(studentRegister.getFinalScore("1"));
    }

    public class StudentRecord implements Comparable<StudentRecord> {

        String id;
        int score;
        Date date;

        public StudentRecord(String id, int score, Date date) {
            this.id = id;
            this.score = score;
            this.date = date;
        }

        @Override
        public int compareTo(StudentRecord that) {
            return this.score - that.score;
        }

    }

    public class StudentRegister {
        private Map<String, StudentScoresCollection> register = new HashMap<String, StudentScoresCollection>();

        public void add(StudentRecord... studentRecords) {
            for (StudentRecord studentRecord : studentRecords) {
                add(studentRecord);
            }
        }

        public void add(StudentRecord studentRecord) {
            if (!register.containsKey(studentRecord.id)) {
                register.put(studentRecord.id, new StudentScoresCollection());
            }

            register.get(studentRecord.id).put(studentRecord);
        }

        public double getFinalScore(String studentId) {
            if (!register.containsKey(studentId)) {
                return -1;
            }

            return register.get(studentId).getFinalScore();
        }
    }

    public class StudentScoresCollection {

        private static final int TEST_NUBMER = 5;

        PriorityQueue<StudentRecord> bestScores = new PriorityQueue<StudentRecord>();
        Collection<StudentRecord> otherScores = new ArrayList<StudentRecord>();
        double bestSum = 0;

        public void put(StudentRecord studentRecord) {
            if (bestScores.size() < TEST_NUBMER) {
                bestScores.offer(studentRecord);
                bestSum += studentRecord.score;
            } else {
                if (bestScores.peek().compareTo(studentRecord) < 0) {
                    StudentRecord record = bestScores.poll();
                    otherScores.add(record);
                    bestSum -= record.score;

                    bestScores.offer(studentRecord);
                    bestSum += studentRecord.score;
                } else {
                    otherScores.add(studentRecord);
                }
            }
        }

        public double getFinalScore() {
            return bestSum / 5.0;
        }
    }
}

public Map<Integer, Double> getFinalScores(List<TestResult> resultList) {

	Map<Integer, Double> finalScores = new HashMap<Integer, Double>();
	for (TestResult result : resultList) {
	    if (finalScores.containsKey(result.studentId)) {
		finalScores.put(result.studentId, finalScores.get(result.studentId) + result.testScore);
	    } else {
		finalScores.put(result.studentId, Double.valueOf(result.testScore));
	    }

	}
	
	return finalScores;
    }