Paginate Provider Listings with Per-Page Diversity
Maven Clinic● MediumFULLTIMEONSITE INTERVIEWProblem statement
Search results are supplied in descending relevance order. Each element of results is an original five-field CSV string provider_id,listing_id,rating,consultation_fee,city. The provider ID is the first field and the numeric rating is the third field.
Partition the results into pages containing at most resultsPerPage entries. During the diversity scan for one page, a listing whose rating is at least highScoreThreshold may be selected while that provider has appeared fewer than highScorePerProviderPageLimit times on the page. Every lower-rated listing uses a limit of one selected listing for its provider.
Build each page as follows:
- Scan the remaining rows in their current order. Select a row when its provider is below the applicable limit above; otherwise defer it. Stop when the page is full or every remaining row has been scanned.
- If the scan ends before the page is full, append the earliest deferred rows in order until the page is full or no rows remain. This padding step may exceed the diversity-scan limits.
- Remove the selected rows. All unselected rows keep their relative order before the next page is built.
Return every selected original five-field CSV string unchanged in page order. Insert an empty string between consecutive pages, but not after the final page.
Function
paginate(resultsPerPage: int, highScoreThreshold: double, highScorePerProviderPageLimit: int, results: String[]) → String[]Examples
Example 1
resultsPerPage = 4highScoreThreshold = 4.8highScorePerProviderPageLimit = 2results = ["1,L1,4.9,100.00,San Francisco","1,L2,4.8,120.00,Oakland","2,L3,4.7,80.00,San Jose","3,L4,4.6,90.00,Oakland","1,L5,4.9,110.00,Berkeley","2,L6,4.9,85.00,San Jose","4,L7,4.5,75.00,Oakland"]return = ["1,L1,4.9,100.00,San Francisco","1,L2,4.8,120.00,Oakland","2,L3,4.7,80.00,San Jose","3,L4,4.6,90.00,Oakland","","1,L5,4.9,110.00,Berkeley","2,L6,4.9,85.00,San Jose","4,L7,4.5,75.00,Oakland"]Provider 1 contributes two qualifying high-rated listings to page one. All five CSV fields, including consultation fee and city, are returned unchanged.
Example 2
resultsPerPage = 3highScoreThreshold = 4.8highScorePerProviderPageLimit = 2results = ["1,A,4.8,100.00,A","1,B,4.8,110.00,A","1,C,4.7,120.00,A"]return = ["1,A,4.8,100.00,A","1,B,4.8,110.00,A","1,C,4.7,120.00,A"]A rating equal to the threshold qualifies. After two provider-1 listings are selected, the lower-rated third row is deferred and then used as deterministic padding.
Example 3
resultsPerPage = 2highScoreThreshold = 4.9highScorePerProviderPageLimit = 2results = ["1,A,4.9,100.00,A","1,B,4.0,110.00,A","2,C,4.0,90.00,B","3,D,4.0,80.00,C"]return = ["1,A,4.9,100.00,A","2,C,4.0,90.00,B","","1,B,4.0,110.00,A","3,D,4.0,80.00,C"]The lower-rated second provider-1 row is deferred while provider 2 fills page one. It remains ahead of the unscanned provider-3 row for page two.
Constraints
1 <= resultsPerPage <= 1000.0.0 <= highScoreThreshold <= 5.0.1 <= highScorePerProviderPageLimit <= resultsPerPage.0 <= results.length <= 100000.- Every entry has exactly five comma-separated fields
provider_id,listing_id,rating,consultation_fee,city; the rating parses as a number and the complete row must be preserved verbatim. - The input is already ordered by decreasing relevance.