Ebay Interview Question for Software Engineer / Developers


Country: United States




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

I think you should use min heap of size 100, NOT max heap.
1. add first 100 data into the heap
2. pick up a data and compare it with the top one of heap, if the data is greater than the top data of the heap, use it replace the top one and adjust the heap. if the data is less than the top data of heap, ignore it.

- Yaya January 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is wrong. if data is less than the top of the heap then we cannot ignore it. we have to see if it greater than the minimum of the 100 that we already have. if no then we can ignore. so we have to maintain one max heap and one min heap. both of size 100. the min head will have the smallest element in the root whereas the max heap has largest element at the root. when a new number comes in we check if it is grater than the root of the max heap. if yes then we remove the root of the max heap and add this number. if the new number is less than the root of the max heap then we check if it grater than the root of the min heap. if yes then we delete the root of the min heap and add this new number to the min heap and adjust it. if the new number is less than the root of the max heap and less than the root of the min heap then we ignore it.

- shash September 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Shash: the question is to get the largest 100, not the smallest 100.

- eugene.yarovoi September 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

MIN HEAP. MIN HEAP.. MIN HEAP

- loveCoding July 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Take a max heap of size 100. Keep inserting elements into the heap.
Initially, the first 100 elements would all go into the heap. After that, the maximum of those 100 elements would be at the top of the heap. This is the current top 100.
So, if the 101th element is less than the top, it means it is part of the top 100 and the element which is currently at the top must be removed. Add this 101th element to the heap.

If the 101th element is greater than the top, it means it is greater than all of the 100 elements which are currently in the heap. So, don't add it to the heap.

Keep doing this by loading as much of the elements you can in your memory. This can be easily calculated by the total amount of memory - memory to store a heap of size 100.

I think this should convince the interviewer.

- sushant.singh1987 January 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

To largest mean the largest 100 elements. You have to use min heap and not max heap. Max heap should be used if you have to find the smallest 100 items. Try out with a small set of numbers (10), where you have to find the largest 4. If your numbers are from 1-10, the min heap at the end will contain numbers 7,8,9,10.

- mahendruajay June 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

In my opinion, the question is how to keep track of 100 biggest numbers of the huge file / array / database.

When first 100 elements come to the file, we remember each of them in the array of 100 integers, and also keep tracking
of what is MIN and what is MAX.
After all 100 indexes are occupied, we do the following upon the next element coming:
If the current element <= MAX element of the array - do nothig;
If the current element > MAX element of the array:
a). Insert this element into array on the place of MIN element;
b). Recalculate MIN and MAX elements of the array.

- sergey.a.kabanov January 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question can be easily solved using min-heap of size 100, initially load any 100 elements of the file into the min-heap then starting from element number 101 to the size of residual file, consider 1 element at a time and check if that element is greater than the minimum element if it is indeed greater then use the extract-min operation on the min-heap which can be done in O(logn) time and insert this new element into the min-heap which gives us our current collection of 100 largest elements and repeat the same procedure for other elements in the file. I hope I am correct in my reasoning :).

- AnkitSablok19091989 March 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's right. One small correction: doing the heap operations isn't log(n); it's log(100). That is, the cost of the heap operations is proportional to the log of the heap size, not the total array size. This means the complexity of selecting the largest k elements from an array of size n using this method would be O(n log k).

- eugene.yarovoi March 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

N*log(100): Binary search tree

- Demi March 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Selection algorithm. O(N).

- Larry March 13, 2012 | 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