Amazon Interview Question
SDE1sCountry: United States
Interview Type: Written Test
Similar to what I would do. A pesky interviewer might tell you that you should extract some methods like map() (where you map the score to the appropriate priority queue) and reduce() (where you calculate the average). This would be easier to unit test.
Also I don't really like this kind of questions because some might simply fail you for no {} after if() or for() when there is only a single line. Guess this kind of details would be important here since as you said this isn't really an algo type of question.
According to my understanding, we can use Map
Map<String, Integer> studentScores = new HashMap<String, Integer>();
-> For 1st test, we will add, student id and his first test score
-> For second test, we will get the student id and add the second test score to first test.So, it will be O(1).
-> we wll repeat this for 2nd,3rd,4th test and for 5th test we will add score and also we will calculate average and score in students id.
what if there are more than 5 test scores for a particular student? you need a appropriate data structure in the Map instead of just Integer.
Map<Integer, Double> calculateFinalScores(List<TestResult> results) {
Map<Integer, Double> res = new TreeMap<>();
if (results != null && results.size() > 0) {
Map<Integer, PriorityQueue<Integer>> scoresQueue = new HashMap<>();
for (TestResult result : results) {
PriorityQueue<Integer> scores = scoresQueue
.get(result.studentId);
if (scores == null) {
scores = new PriorityQueue<Integer>();
scoresQueue.put(result.studentId, scores);
}
scores.add(result.testScore);
if (scores.size() > 5) {
scores.poll();
}
}
for (int studentId : scoresQueue.keySet()) {
double totalScores = 0;
PriorityQueue<Integer> scores = scoresQueue.get(studentId);
for (int score : scores) {
totalScores += score;
}
res.put(studentId, totalScores / 5);
}
}
return res;
}
class TestResult {
int studentId;
String testDate;
int testScore;
// setter getter for all attributes
}
public class FinalScoreQuestion {
/**
* Final result to hold student actual result
*/
class FinalResult {
double finalScore;
long scores;
int count;
// getter for finalScore only
}
/**
* Proper java doc
*/
Map <Integer, FinalResult> calculateFinalScores (List<TestResult> results) {
Map<Integer, FinalResult> finalResults = new HashMap();
// iterate results
for(TestResult result : results) {
int id = result.getId();
Finalresult finalResult = finalResults.get(id);
if(finalResult == null) {
// entry not found
finalResult = new FinalResult();
finalResult.scores = result.getScore();
finalResult.count++;
finalResults.add(finalResult);
} else {
// entry found
if(finalResult.count == 5) {
finalResult.finalScore = finalResult.scores / 5;
} else {
finalResult.scores += finalResult.scores;
finalResult.count++;
}
}
}
return finalResults;
}
}
NB: Extra DS required to track how many scores calculated ...
Instead of calculating average each time from priority queue, it would be better to store it and keep on changing it without browsing whole queue
class TestResult {
int studentId;
String testDate=null;
int testScore;
public TestResult() {
// TODO Auto-generated constructor stub
}
TestResult(int studentId, int testScore){
this.studentId=studentId;
this.testScore=testScore;
}
}
class PriorityQueueWithAverage {
PriorityQueue<Integer> pq = new PriorityQueue<>();
Double avg = 0.0;
static int maxTestToConsider = 5;
public void add(int i) {
if (pq.isEmpty()) {
pq.add(i);
avg = (double) i;
}
else if (pq.size() < maxTestToConsider) {
avg = (((avg * pq.size()) + i) / (pq.size() + 1));
pq.add(i);
} else {
if (pq.peek() < i) {
int temp = pq.peek();
avg = (((avg * pq.size()) + i - temp) / (pq.size()));
pq.poll();
pq.add(i);
}
}
}
@Override
public String toString(){
return("AVG :"+avg+", Queue:"+pq);
}
}
public class FinalScoreQuestion {
Map<Integer, Double> calculateFinalScores(List<TestResult> results) {
Map<Integer, Double> finalScore = new HashMap<Integer, Double>();
Map<Integer, PriorityQueueWithAverage> nonFinalMapWithAverage = new HashMap<Integer, PriorityQueueWithAverage>();
for (TestResult testResult : results) {
if (!nonFinalMapWithAverage.containsKey(testResult.studentId)) {
PriorityQueueWithAverage tempPqWithAverage = new PriorityQueueWithAverage();
tempPqWithAverage.add(testResult.testScore);
nonFinalMapWithAverage.put(testResult.studentId,
tempPqWithAverage);
} else {
PriorityQueueWithAverage tempPqWithAverage = nonFinalMapWithAverage
.get(testResult.studentId);
tempPqWithAverage.add(testResult.testScore);
}
}
for (Iterator<Integer> iterator = nonFinalMapWithAverage.keySet()
.iterator(); iterator.hasNext();) {
int studentId = iterator.next();
finalScore
.put(studentId, nonFinalMapWithAverage.get(studentId).avg);
}
return finalScore;
}
}
class TestResult {
int studentId;
String testDate;
int testScore;
public TestResult(int studentId, String testDate, int testScore) {
super();
this.studentId = studentId;
this.testDate = testDate;
this.testScore = testScore;
}
}
public class FinalScoreQuestion {
public static void main(String[] args) {
List<TestResult> testResults = new ArrayList<TestResult>(0);
testResults.add(new TestResult(1, "02-07-2013", 60));
testResults.add(new TestResult(1, "02-07-2013", 70));
testResults.add(new TestResult(1, "02-07-2013", 80));
testResults.add(new TestResult(1, "02-07-2013", 90));
testResults.add(new TestResult(1, "02-07-2013", 95));
testResults.add(new TestResult(2, "02-07-2013", 60));
testResults.add(new TestResult(2, "02-07-2013", 65));
testResults.add(new TestResult(2, "02-07-2013", 70));
testResults.add(new TestResult(2, "02-07-2013", 75));
testResults.add(new TestResult(2, "02-07-2013", 80));
FinalScoreQuestion finalScoreQuestion = new FinalScoreQuestion();
finalScoreQuestion.calculateFinalScores(testResults);
}
/**
* @description This method calculates average of top five scores of each student and returns a map of student and average score.
* @param results
* @return
*/
protected Map<Integer, Double> calculateFinalScores (List<TestResult> results) {
Map<Integer, Double> finalStudentScore = new HashMap<Integer, Double>();
Map<Integer, List<TestResult>> studentScoresMap = new HashMap<Integer, List<TestResult>>();
List<TestResult> list = new ArrayList<TestResult>(0);
studentScoresMap = partitionStudentScores(results, studentScoresMap, list);
for (Map.Entry<Integer, List<TestResult>> entry : studentScoresMap.entrySet()) {
List<Integer> scores = new ArrayList<Integer>(0);
Integer averageScore = 0;
int consolidateScore = 0;
scores = getAllTheScoresOfStudent(entry, scores);
averageScore = sortAndGetTheAverage(scores, consolidateScore);
finalStudentScore.put(entry.getKey(), (Double.valueOf(averageScore)));
}
return finalStudentScore;
}
/**
* @description This method shall sort the List of scores of each student and takes the first five top scores and calculates the
* average of the scores and returns it.
* @param scores
* @param consolidateScore
* @return
*/
protected Integer sortAndGetTheAverage(List<Integer> scores, int consolidateScore) {
Integer averageScore;
Collections.sort(scores, Collections.reverseOrder());
for (int i = 0; i < 5; i++) {
consolidateScore = consolidateScore + scores.get(i);
}
averageScore = Integer.valueOf(consolidateScore) / 5;
return averageScore;
}
/**
* @description This method shall return all the scores of a student in the form of a List
* @param entry
* @param scores
* @return
*/
protected List<Integer> getAllTheScoresOfStudent(Map.Entry<Integer, List<TestResult>> entry, List<Integer> scores) {
for (TestResult studentScore : entry.getValue()) {
scores.add(Integer.valueOf(studentScore.testScore));
}
return scores;
}
/**
* @description This method shall split the all the list of scores and gives you the map of student and list of student's all scores
* @param results
* @param studentScoresMap
* @param list
* @return
*/
protected Map<Integer, List<TestResult>> partitionStudentScores(List<TestResult> results, Map<Integer, List<TestResult>> studentScoresMap,
List<TestResult> list) {
for (TestResult testResult : results) {
if (studentScoresMap.containsKey(testResult.studentId)) {
list = studentScoresMap.get(testResult.studentId);
} else {
list = new ArrayList<TestResult>(0);
}
list.add(testResult);
studentScoresMap.put(Integer.valueOf(testResult.studentId), list);
}
return studentScoresMap;
}
}
public Map<Integer, Double> calculateFinalScores(List<TestResult> results) {
Map<Integer, List<Integer>> scoreMap = new HashMap<>();
for (TestResult testResult : results) {
if (scoreMap.containsKey(testResult.studentId)) {
List<Integer> scoreList = scoreMap.get(testResult.studentId);
scoreList.add(testResult.testScore);
scoreMap.put(testResult.studentId, scoreList);
} else {
List<Integer> scoreList = new ArrayList<>();
scoreMap.put(testResult.studentId, scoreList);
}
}
Map<Integer, Double> finalScores = new HashMap<>();
for (Integer id : scoreMap.keySet()) {
List<Integer> scoreList = scoreMap.get(id);
Collections.sort(scoreList); // sort the score list because we need
// top 5 highest scores
ListIterator<Integer> itr = scoreList.listIterator(scoreList.size() -5);
double avg = 0.0;
int sum = 0;
for (int i = 0 ; i < 5 ;i++) {
sum += itr.next();
}
avg = sum / 5;
finalScores.put(id, avg);
}
return finalScores;
}
class TestResult {
int studentId;
String testDate;
int testScore;
TestResult() {
studentId = 0;
testDate = "";
testScore = 0;
}
TestResult(int Id, String date, int score) {
this.studentId = Id;
this.testDate = date;
this.testScore = score;
}
int getID() {
return this.studentId;
}
int getScore() {
return this.testScore;
}
}
public class StudentRanking {
static class PQComparator implements Comparator<TestResult> {
@Override
public int compare(TestResult one, TestResult two) {
// TODO Auto-generated method stub
return one.testScore - two.testScore;
}
}
public static void main(String[] args) {
// Create an array List of TestResult
List<TestResult> student = new ArrayList<TestResult>();
Map<Integer, Double> FinalScores = new HashMap<Integer, Double>();
// create a list of test result for a student
student.add(new TestResult(1, "2010", 90));
student.add(new TestResult(1, "2010", 90));
student.add(new TestResult(1, "2010", 60));
student.add(new TestResult(1, "2009", 75));
student.add(new TestResult(1, "2010", 80));
student.add(new TestResult(1, "2009", 88));
student.add(new TestResult(1, "2009", 98));
student.add(new TestResult(1, "2009", 50));
student.add(new TestResult(1, "2008", 40));
student.add(new TestResult(1, "2009", 100));
// create a list of test result for another student
student.add(new TestResult(2, "2010", 90));
student.add(new TestResult(2, "2010", 90));
student.add(new TestResult(2, "2010", 90));
student.add(new TestResult(2, "2009", 90));
student.add(new TestResult(2, "2010", 90));
student.add(new TestResult(2, "2009", 88));
student.add(new TestResult(2, "2009", 78));
student.add(new TestResult(2, "2009", 50));
student.add(new TestResult(2, "2008", 60));
student.add(new TestResult(2, "2009", 100));
student.add(new TestResult(3, "2010", 85));
student.add(new TestResult(3, "2010", 90));
student.add(new TestResult(3, "2010", 60));
student.add(new TestResult(3, "2009", 75));
student.add(new TestResult(3, "2010", 80));
student.add(new TestResult(3, "2009", 88));
student.add(new TestResult(3, "2009", 98));
student.add(new TestResult(3, "2009", 50));
student.add(new TestResult(3, "2008", 40));
student.add(new TestResult(3, "2009", 100));
FinalScores = calculateFinalScores(student);
for (Map.Entry<Integer, Double> e : FinalScores.entrySet()) {
System.out.println("Student ID >> " + e.getKey()
+ " >> Average Score >> " + e.getValue());
}
}
static Map<Integer, Double> calculateFinalScores(List<TestResult> results) {
Double avg = 0.0;
int sum = 0;
int count = 0;
HashMap<Integer, PriorityQueue<TestResult>> top5_marks = new HashMap<Integer, PriorityQueue<TestResult>>();
// put the student id and his average in a hashmap
HashMap<Integer, Double> final_scores = new HashMap<Integer, Double>();
PQComparator pqComparator = new PQComparator();
PriorityQueue<TestResult> pq = null;
for (TestResult r : results) {
if (top5_marks.containsKey(r.studentId)) {
if (pq.size() == 5) {
pq.add(r);
pq.poll();
} else {
pq.add(r);
}
} else {
pq = new PriorityQueue<TestResult>(5, pqComparator);
pq.add(r);
top5_marks.put(r.studentId, pq);
}
}
for (Map.Entry<Integer, PriorityQueue<TestResult>> e : top5_marks
.entrySet()) {
PriorityQueue<TestResult> temp = e.getValue();
for (TestResult t : temp) {
sum = sum + t.testScore;
count = count + 1;
}
avg = (double) sum / count;
final_scores.put(e.getKey(), avg);
sum = 0;
count = 0;
}
return final_scores;
}
}
import java.util.*;
class TestResult
{
int studentId;
String testDate;
int testScore;
public TestResult(int studentId, String testDate, int testScore) {
super();
this.studentId = studentId;
this.testDate = testDate;
this.testScore = testScore;
}
}
public class FinalScoreQuestion {
Map<Integer, Double> calculateFinalScores(List<TestResult> results)
{
Map<Integer, Double> StuMap = new HashMap<>();
Map<Integer,PriorityQueue<Integer>> map = new HashMap<>();
if(results == null || results.size() == 0) return StuMap;
for(TestResult result: results)
{
int id = result.studentId;
int score = result.testScore;
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
if(map.containsKey(id))
{
queue = map.get(id);
if(queue.size()>6)
{
queue.poll();
queue.offer(score);
map.put(id,queue);
}
else
{
queue.offer(score);
map.put(id,queue);
}
}
else
{
queue.offer(score);
map.put(id, queue);
}
}
//Calculate average
for(int key: map.keySet())
{
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue = map.get(key);
int sum=0;
double avg;
for(int i=0;i<5;i++)
sum += queue.poll();
avg = sum/5;
StuMap.put(key, avg);
}
return StuMap;
}
public static void main(String[] args) {
List<TestResult> testResults = new ArrayList<TestResult>(0);
testResults.add(new TestResult(1, "02-07-2013", 60));
testResults.add(new TestResult(1, "02-07-2013", 70));
testResults.add(new TestResult(1, "02-07-2013", 80));
testResults.add(new TestResult(1, "02-07-2013", 90));
testResults.add(new TestResult(1, "02-07-2013", 95));
testResults.add(new TestResult(1, "02-07-2013", 100));
testResults.add(new TestResult(2, "02-07-2013", 60));
testResults.add(new TestResult(2, "02-07-2013", 65));
testResults.add(new TestResult(2, "02-07-2013", 70));
testResults.add(new TestResult(2, "02-07-2013", 75));
testResults.add(new TestResult(2, "02-07-2013", 80));
FinalScoreQuestion finalScoreQuestion = new FinalScoreQuestion();
finalScoreQuestion.calculateFinalScores(testResults);
}
}
Output:
Peek, Key = 1 value 100
Peek, Key = 1 value 95
Peek, Key = 1 value 90
Peek, Key = 1 value 80
Peek, Key = 1 value 70
1 Key AVG = 87.0
Peek, Key = 2 value 80
Peek, Key = 2 value 75
Peek, Key = 2 value 70
Peek, Key = 2 value 65
Peek, Key = 2 value 60
2 Key AVG = 70.0
to me, it seems a Java problem rather than a algo problem
- Anonymous June 17, 2013