View All num of num See all Photos Amazon.com www.amazon.com Engaged Employer Overview Reviews Salaries Interviews Jobs Photos Benefits 5.3k Reviews 12k Salaries 6.4k Interviews 7.6k Jobs Follow Add Interview Follow Add Interview Interview Question Software Development Engineer In Test Interview Seattle, WA Amazon.com 2. Find top 100 maximum number from a continuous input stream. Tags: See more , See less 8 Answer Add Tags Answer Interview Answer 6 Answers ▲ 4 ▼ Use a min heap to store the top 100 maximum numbers. If the incoming number is greater than the top element replace it and sort the heap. Interview Candidate on Dec 6, 2012 ▲ 1 ▼ Use a sorted generic list.If the number of elements is < 100 Add the incoming number to the list.else if the incoming number is greater than the zero element of the list Add the incoming number to the list remove the zero element from the list to keep the number of elements at 100. Developer on Dec 7, 2012 ▲ 0 ▼ The interview candidates solutions is the best, n insertion * log n for each heap insert - > nlognDeveloper: n * n = n^2 Hamid Dadkhah on Dec 9, 2012 ▲ 0 ▼ I think the key of the question would be 100, a fixed number.The sorting time of 100 numbers would always be O(1). Anonymous on Dec 10, 2012 ▲ 0 ▼ There is a blog discussing a similar coding interview question at http://codercareer.blogspot.com/2011/09/no-05-least-k-numbers.html.The first solution is suitable for this problem. Harry on Dec 23, 2012 ▲ 0 ▼ "I think the key of the question would be 100, a fixed number.The sorting time of 100 numbers would always be O(1)."This is bad design given that if it was something other than 100, then this does not hold true. Even if it was always true, using a heap (or Priority Queue in java) will give you a better run time.Here's why: for each insertion you will sort, this will be 100*log(100) for each incmoming number, and you might have to remove a number, which will be logn (assuming you are using an array and using binary search to search the element), and finally, o(1) for each insertion...using a priority queue will give you log(100) for each removal, and log(100) for each insertion, and o(1) for a comparison with the head of the heapcomparing solutions this is: 100*log(100) + log(100) + 1 V.S. log(100) + log(100) + 1, solution 2 is much better timewise, and spacewise it is the same. gman on Jun 22, 2014 Interviews > Software Development Engineer In Test > Amazon.com Add Answers or Comments To comment on this, Sign In or Sign Up.