Your question is Count Same Bid History Fast. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Quantcast's real-time bidding service needs to answer how often a proposed bid has appeared in a historical sequence. Implement count_in_history so repeated lookups remain efficient when the history contains millions of bids.
The historical bids are provided in nondecreasing order. Return the number of elements equal to current_bid. Do not modify previous_bids.
current_bid: an integer bid value.previous_bids: a nondecreasing array of integers representing prior bids.previous_bids equal to current_bid.Use the sorted property to avoid scanning the complete array. A solution that performs one full pass per request is not considered optimal for this interface.
def count_in_history(current_bid, previous_bids):