CareerCup

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.

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.

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.

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

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.