Paginate Search Results by Unique Host
Reported by candidates from Airbnb's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The Airbnb OA reported in May 2019 asks you to paginate search results so each page favors unique hosts. It looks like a binary-search problem on paper, but it's really a simulation. The mistake that sinks a first attempt is treating the pad step as a re-scan of the whole list instead of the leftover skipped entries in order. Constraints are small, up to 1000 results, so clarity beats cleverness. If you blank on the page-building loop during the live OA, StealthCoder runs invisibly on your screen and gives you a working solution as a safety net. Know the shape first.
The problem
Search results are supplied in descending score order. Each element of results is the original CSV string host_id,listing_id,score,city; the host ID is the substring before the first comma. Partition the results into pages containing at most resultsPerPage entries. To build each page: Scan the remaining results in order and select the earliest entry from each host not yet represented on this page, until the page is full or the scan ends. If the page is still not full, append the earliest remaining skipped entries in their current order until the page is full or no results remain. Remove every selected entry, then build the next page from the remaining list. Return every selected original CSV string in page order. Insert an empty string between consecutive pages, but not after the final page. Function paginate(resultsPerPage: int, results: String[]) → String[] Examples Example 1 resultsPerPage = 5 results = ["1,28,300.6,San Francisco","4,5,209.1,San Francisco","20,7,203.4,Oakland","6,8,202.9,San Francisco","6,10,199.8,San Francisco","1,16,190.5,San Francisco","6,29,185.3,San Francisco","7,20,180.0,Oakland","6,21,162.2,San Francisco","2,18,161.7,San Jose","2,30,149.8,San Jose","3,76,146.7,San Francisco","2,14,141.8,San Jose"] return = ["1,28,300.6,San Francisco","4,5,209.1,San Francisco","20,7,203.4,Oakland","6,8,202.9,San Francisco","7,20,180.0,Oakland","","6,10,199.8,San Francisco","1,16,190.5,San Francisco","2,18,161.7,San Jose","3,76,146.7,San Francisco","6,29,185.3,San Francisco","","6,21,162.2,San Francisco","2,30,149.8,San Jose","2,14,141.8,San Jose"] The first page takes the earliest entries from hosts 1, 4, 20, 6, and 7. On page two, host 6 appears first, so its later result is skipped during the unique-host scan and then used to pad that page. Example 2 resultsPerPage = 3 results = ["1,10,9.0,A","1,11,8.0,A","2,20,7.0,B","1,12,6.0,A"] return = ["1,10,9.0,A","2,20,7.0,B","1,11,8.0,A","","1,12,6.0,A"] The unique-host scan selects hosts 1 and 2. It cannot find a third distinct host, so the earliest skipped host-1 result pads the first page. Example 3 resultsPerPage = 2 results = ["1,1,3.0,A","2,2,2.0,B","3,3,1.0,C"] return = ["1,1,3.0,A","2,2,2.0,B","","3,3,1.0,C"] All hosts are distinct, so each page simply takes the next entries in order. The last page has one result and no trailing separator. Constraints 1 <= resultsPerPage <= 1000. 0 <= results.length <= 1000. Every result is a valid CSV string with exactly four fields: integer host ID, integer listing ID, finite decimal score, and a non-empty city containing no comma. results is already sorted by non-increasing score.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is that each page is two passes over the remaining list. Pass one walks in order and takes the first entry per host, tracking hosts in a set, until the page is full. Pass two walks the same remaining list again and takes the earliest entries you didn't select, in their current order, until full. Then you remove the selected entries and repeat. With n up to 1000, an O(n^2) rebuild is fine. The common pitfall is the separator. Insert an empty string between pages, never after the last one. Another is parsing the host ID: take the substring before the first comma, and don't convert the whole line. Also don't mutate the list while you iterate it. Mark selected indexes in a boolean array, then rebuild the remainder. If you freeze under the clock, StealthCoder is the hedge that reads the prompt and hands you the loop. Trace Example 1 by hand first.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Paginate Search Results by Unique Host cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Airbnb's OA.
Airbnb reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Paginate Search Results by Unique Host FAQ
What's the trick in the Airbnb paginate problem?+
Build each page in two passes over the remaining list. First pick the earliest entry per unseen host. Then, if the page isn't full, fill with the earliest skipped entries in order. Remove what you took and repeat. It's simulation, not a clever algorithm.
Is binary search actually needed here?+
No. The hint says binary search, but nothing in the statement requires it. With at most 1000 results, a direct simulation with a set per page is enough. Don't waste your time hunting for a sorted-search angle.
How do I handle the empty-string separators?+
Add an empty string after every page except the last. Easiest approach is to append the separator at the start of each page after the first, or check whether any results remain before adding it. Example 3 shows the exact output.
What edge cases should I test?+
Empty results should return an empty array. Test resultsPerPage larger than the list, all entries from one host, and all distinct hosts. Example 2 covers padding with skipped entries, and Example 3 covers the missing trailing separator.
How do I prepare for this in 48 hours?+
Code the two-pass page builder from scratch twice. Parse the host with a split on the first comma, use a used-index array, and hand-trace Example 1 against your output. Practice getting the separator logic right, since that's where most attempts break.