Reorder Search Results for Provider Diversity
Problem: Reorder Search Results for Provider Diversity
Build a function that paginates ordered provider listings for a telehealth marketplace. The input is a list of records, where each record is a CSV string in the format: provider_id, listing_id, rating, consultation_fee, city.
Example Record: 1,101,4.9,100,NYC
Assumptions:
- The input list is already sorted by relevance.
- A single provider may have multiple listings.
Task: Reorder the listings into pages of size 5 according to the following rules:
- Provider Diversity: Within a page, include at most one listing from the same provider whenever possible.
- Order Preservation: Preserve the original order as much as possible. When selecting the next valid result, prefer the earliest remaining listing.
- Page Filling Fallback: If there are not enough distinct providers to fill a page, allow repeated providers to fill the remaining slots.
Output: Return or print the results page by page, with a blank line separating each page.
Example Input:
['1,101,4.9,100,NYC', '2,102,4.8,120,LA', '1,103,4.7,95,Boston', '3,104,4.6,110,Chicago']
Discussion Points:
- Analyze the time and space complexity of your solution.
Follow-up Questions:
- How would you change the algorithm if high-scoring providers were allowed to appear multiple times on the same page?
- How would you implement a memory-efficient streaming version when the input can contain roughly 150 million listings and does not fit in memory?
AI interview prep
Core dilemma
Balancing the strict requirement for provider diversity within a page against the need to preserve the original relevance order, especially when dealing with large, potentially memory-exceeding datasets.
2 tradeoffs and 2 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Reorder Search Results for Provider Diversity
Problem: Reorder Search Results for Provider Diversity
Build a function that paginates ordered provider listings for a telehealth marketplace. The input is a list of records, where each record is a CSV string in the format: provider_id, listing_id, rating, consultation_fee, city.
Example Record: 1,101,4.9,100,NYC
Assumptions:
- The input list is already sorted by relevance.
- A single provider may have multiple listings.
Task: Reorder the listings into pages of size 5 according to the following rules:
- Provider Diversity: Within a page, include at most one listing from the same provider whenever possible.
- Order Preservation: Preserve the original order as much as possible. When selecting the next valid result, prefer the earliest remaining listing.
- Page Filling Fallback: If there are not enough distinct providers to fill a page, allow repeated providers to fill the remaining slots.
Output: Return or print the results page by page, with a blank line separating each page.
Example Input:
['1,101,4.9,100,NYC', '2,102,4.8,120,LA', '1,103,4.7,95,Boston', '3,104,4.6,110,Chicago']
Discussion Points:
- Analyze the time and space complexity of your solution.
Follow-up Questions:
- How would you change the algorithm if high-scoring providers were allowed to appear multiple times on the same page?
- How would you implement a memory-efficient streaming version when the input can contain roughly 150 million listings and does not fit in memory?