CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question


Country: India
More Questions from This Interview



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

Could use external merge sort to sort by value. Then walk through sorted array, count frequency of each number and add to a min-heap. If min heap has more than k elements, remove minimum. Overall effort O(n log n) for sorting, O(n * log k) for building up and maintainig k element min heap, so O(n log n).

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

yes, I told about using hash map to count frequency and then min-heap. hash map will grow very large in case of large numbers. So we can make use of multiple hashes or B-trees to store the hash map.

- rams December 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes, I told about using hash map to count frequency and then min-heap. hash map will grow very large in case of large numbers. So we can make use of multiple hashes or B-trees to store the hash map.

- rams December 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Is sorting required ? I think it can be avoided right ?

- rams December 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

How about using tree map. It sorts key values automatically. We can put each number from file as key and number of occurrences of that number as value pair. Finally take top k values.

- raghava.javvaji December 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

tree map sorts elements based on keys... so for this problem it wont work since keys will be distinct numbers from file and values will be number's occurrences/count.. and we need to provide max "occurring" value.. please correct me if i am wrong..

- kn January 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

u can apply sorting according to their size, u can use bubble sort or merge sort depending on the value of k, u can use bubble sort if k is less than log n and get k maximum elements otherwise apply merge sort...the maximum complexity will be nlogn

- probs December 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A better question to ask is what type of numbers they are? Are they ages of people or huge digits or digits within 1 to 1000? Depending on the answer you can create an array, with each index representing the digit in the file. Then return the highest digit in the array.

- Anonymous December 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can anybody provide algo for this ?

- Ankur December 24, 2011 | 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