## Amazon Interview Question for SDE1s

• 0

Country: United States
Interview Type: In-Person

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

How about a min_heap of size k ? If we come across an element greater than the top of the heap, remove top, add new element to heap, and heapify. So the top of the heap will have the kth highest price.

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

Seems like the solution is more of a max_heap of size k. You inserts the bids into the heap and it keeps the top k bits. At the end you get the value at the bottom of the heap.

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

max heap does not necessarily keep the top k bids.

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

Maintain a min_heap of size k and max_bid. If new bid larger than min_heap.top() arrives remove min_heap.top() and insert new bid. Also, if new bid is larger than max_bid then update max_bid. At the end, top element of the min_heap has the cost desired.

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

Do we require heap as deletion will take O(logn) times.
Assumption: All next bid is higher then previous bid or check it before you insert next bid. You need access of peak element in the list and also access to the kth element of the list. A link list of size exactly k with head and tail should do the job. tail is where you append next bid and remove head as soon as you insert new bid. Then when you required kth bid just pop head out and give the result.
Access time of everything is O(1)
Highest bid kth bid
1 2 3 4 K

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

A min heap of size k and a variable holding topBidSoFar.
Store the top k bids in min heap. If any bid is greater than the top of minHeap, replace min Heap top. Also if this bid is greater than the topBidSoFar, replace it.

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.