Airbnb Online Assessment Paginate List
5
13
1,28,310.6,SF
4,5,204.1,SF
20,7,203.2,Oakland
6,8,202.2,SF
6,10,199.1,SF
1,16,190.4,SF
6,29,185.2,SF
7,20,180.1,SF
6,21,162.1,SF
2,18,161.2,SF
2,30,149.1,SF
3,76,146.2,SF
2,14,141.1,San Jose
Here is a sample input. It’s a list generated by user search. (1,28,100.3,Paris) corresponds to (Host ID, List ID, Points, City).
5 in the first row tells each page at most keeps 5 records.
13 in the second row is the number of records in the list.
Please paginate the list for Airbnb by requirement:
1. When possible, two records with same host ID shouldn’t be in a page.
2. But if no more records with non-repetitive host ID can be found, fill up the page with the given input order (ordered by Points).
Expected output:
1,28,310.6,SF
4,5,204.1,SF
20,7,203.2,Oakland
6,8,202.2,SF
7,20,180.1,SF
6,10,199.1,SF
1,16,190.4,SF
2,18,161.2,SF
3,76,146.2,SF
6,29,185.2,SF -- 6 repeats in page bec no more unique host ID available
6,21,162.1,SF
2,30,149.1,SF
2,14,141.1,San Jose

int paginate(const std::vector& addressbook, std::vector& results) {
    std::list > curve; // host_id, position in addressbook
    int num_entries = addressbook.size(); // already sorted by score.
    for (int index = 0; index < num_entries; ++index) { 
        const std::string& s = addressbook[index];
        int host_id = std::stoi(s.substr(0, s.find_first_of(',')));
        curve.emplace_back(host_id, index);
    }

    while (!curve.empty()) {
        std::unordered_set uniq_host_ids;
        std::vector hosts;
        bool combo = false;
        for (auto iter = curve.begin(); iter != curve.end(); ++iter) {
            if (uniq_host_ids.find(iter->first) == uniq_host_ids.end()) {
                uniq_host_ids.insert(iter->first);
                hosts.push_back(iter);
                if (hosts.size() == resultsPerPage) {
                    combo = true;
                    break;
                }
            }
        }
        for (auto& host : hosts) {
            results.push_back(addressbook[host->second]);
        }
        for (auto& host : hosts) { 
            curve.erase(host);
        }

        if (combo) {
            if (!curve.empty()) results.push_back("");
            continue; // enter next loop
        }

        if (!curve.empty()) {
            int num_done = hosts.size();
            for (auto iter = curve.begin(); iter != curve.end(); ++iter) {
                hosts.push_back(iter);
                if (hosts.size() == resultsPerPage) {
                    combo = true; break;
                }
            }
            int num_hosts = hosts.size();
            for (int i = num_done; i < num_hosts; ++i) {
                results.push_back(addressbook[hosts[i]->second]);
            }
            for (int i = num_done; i < num_hosts; ++i) {
                curve.erase(hosts[i]);
            }
            if (combo && !curve.empty()) {
                results.push_back("");
            }
        } // end if condition
    } // end while loop
    return 0;
}