Host Diverse Pagination
MediumHeap · Airbnb
Search results arrive as a ranked list rows, best first. Each row is a comma-separated string whose first field is the host id, for example "7,listing_42,4.9" belongs to host "7". Compare host ids as strings (the text before the first comma).
The results are shown in pages of page_size rows, and within one page the same host should not appear twice when that can be avoided. Build pages one at a time, filling each page slot by slot:
- Take the highest-ranked remaining row whose host is not already on the current page.
- If every remaining row belongs to a host already on the current page, take the highest-ranked remaining row anyway.
- A page is complete when it holds
page_sizerows or no rows remain; then start a new, empty page.
Return all rows in the order they appear across the pages (pages concatenated, no separators). Every input row appears exactly once in the output, unchanged.
Example 1
- Input:
- rows = ['11,a,9.8', '11,b,9.5', '22,c,9.1', '11,d,8.7', '33,e,8.0', '22,f,7.5'], page_size = 3
- Output:
- ['11,a,9.8', '22,c,9.1', '33,e,8.0', '11,b,9.5', '22,f,7.5', '11,d,8.7']
- Explanation
- Page 1 takes
11,a, skips the other host-11 rows, takes22,c, then33,e. Page 2 starts fresh with11,band22,f; the only row left is11,d, whose host is already on the page, so it is taken anyway to fill the last slot.
Example 2
- Input:
- rows = ['5,a', '5,b', '5,c', '8,d'], page_size = 3
- Output:
- ['5,a', '8,d', '5,b', '5,c']
- Explanation
- Page 1 takes
5,a, then jumps ahead to8,dbecause it is the only other host. No new host remains, so5,bfills the third slot.5,cstarts page 2.
Example 3
- Input:
- rows = ['1,x', '2,y', '1,z'], page_size = 1
- Output:
- ['1,x', '2,y', '1,z']
- Explanation
- With one row per page there is never a conflict, so the original ranking is kept.
Constraints
0 <= rows.length <= 10^41 <= page_size <= 100- Each row is non-empty and its host id (the text before the first comma) is non-empty