Amazon Interview Question for SDE1s

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
1
of 1 vote

to me, it seems a Java problem rather than a algo problem

``````class FinalScoreQuestion {

Map<Integer, Double> calculateFinalScores (List<TestResult> results)
{
if(results == null || results.size() == 0)
return null;

HashMap<Integer, PriorityQueue<Integer> > id_scores =
new HashMap<Integer, PriorityQueue<Integer> > ();

Comparator comp = Collections.reverseOrder();

for(TestResult res : results) {

PriorityQueue<Integer> queue = null;
if(id_scores.containsKey( res.studentId ) ) {
queue = id_scores.get(res.studentId);
} else {
queue = new PriorityQueue<Integer>(5,comp);
}

queue.offer(res.testScore);

id_scores.put(res.studentId, queue);
}

Map<Integer, Double> averages = new HashMap<Integer, Double>();
for(int key : id_scores.keySet()) {
PriorityQueue<Integer> queue = id_scores.get(key);

double avg = 0;
for(int i=0; i<5 ; i++)
avg += queue.poll();

avg /= 5;

averages.put(key, avg);
}

return averages;
}
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

this code is very concise, thank you

Comment hidden because of low score. Click to expand.
0

Why did you use priority queue?

Comment hidden because of low score. Click to expand.
0

What would be the time complexity of the above code? Will it be O(n) where n is the number of entries in the input list results?

Comment hidden because of low score. Click to expand.
0
of 0 vote

this is one of online test problems

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

here we are taking each student separately and adding score to him/her. if there are more subjects for some students, then we can add score to them separately. because we are not maintaining an array to store their score.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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) {
finalResult = new FinalResult();
finalResult.scores = result.getScore();
finalResult.count++;
}  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 ...

Comment hidden because of low score. Click to expand.
0

Complexity is O(N)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

if (pq.isEmpty()) {
avg = (double) i;
}
else if (pq.size() < maxTestToConsider) {
avg = (((avg * pq.size()) + i) / (pq.size() + 1));
} else {
if (pq.peek() < i) {
int temp = pq.peek();
avg = (((avg * pq.size()) + i - temp) / (pq.size()));
pq.poll();
}
}
}
@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();
nonFinalMapWithAverage.put(testResult.studentId,
tempPqWithAverage);
} else {
PriorityQueueWithAverage tempPqWithAverage = nonFinalMapWithAverage
.get(testResult.studentId);
}
}
for (Iterator<Integer> iterator = nonFinalMapWithAverage.keySet()
.iterator(); iterator.hasNext();) {
int studentId = iterator.next();
finalScore
.put(studentId, nonFinalMapWithAverage.get(studentId).avg);
}
return finalScore;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);

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()) {
}
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);
}
studentScoresMap.put(Integer.valueOf(testResult.studentId), list);
}
return studentScoresMap;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
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;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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

// create a list of test result for another student

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.poll();
} else {
}
} else {
pq = new PriorityQueue<TestResult>(5, pqComparator);
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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);

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``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.