Count Same Bid History Fast | Dataford Interview Questions

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.

Formal Specification

Input current_bid: an integer bid value.
Input previous_bids: a nondecreasing array of integers representing prior bids.
Output: an integer count of values in 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.

Constraints

0 <= previous_bids.length <= 10^7
-10^9 <= current_bid <= 10^9
-10^9 <= previous_bids[i] <= 10^9
previous_bids is sorted in nondecreasing order
previous_bids must not be modified

Function Signature

def count_in_history(current_bid, previous_bids):

Your question is Count Same Bid History Fast. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem