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

- Anonymous June 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous June 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this code is very concise, thank you

- Lesley Fang July 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why did you use priority queue?

- Shaziya Syeda December 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Anonymous February 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is one of online test problems

- zcatla June 17, 2013 | Flag Reply
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.

- prashanthreddy.mtech June 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous June 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- prashanthreddy.mtech June 17, 2013 | Flag
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);
			}
			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;
}

- Anonymous June 17, 2013 | Flag Reply
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) {
				// 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 ...

- Debasis Jana June 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity is O(N)

- Debasis Jana June 17, 2013 | Flag
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;

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

}

- cyrus June 17, 2013 | Flag Reply
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);
		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;
	}
	
}

- Rakesh July 02, 2013 | Flag Reply
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);
				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;

	}

- Ankit August 01, 2013 | Flag Reply
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
		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;
	}

}

- Bharath Rajakumar January 01, 2014 | Flag Reply
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);
		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

- JAR February 20, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More