CareerCup

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for private lessons by FB, Google and Uber engineers

Our ONE TO ONE class offers

SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn and other top-tier companies after weeks of training.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

Candidate’s Solution (Passed all test cases in Airbnb OA)

int paginate(const std::vector<std::string>& addressbook, std::vector<std::string>& results) {
    std::list<std::pair<int, int> > 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<int> uniq_host_ids;
        std::vector<decltype(curve)::iterator> 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;
}

const results = [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']
];


const paginate = (results)=>{
    const max =results[0] ;
    let pageData = results.slice(2);
    let pages = [];
    let ids = new Set();
    let inserted = new Set();
    let i=0;
    while(i<pageData.length){
        if(pages.length%max==0 && ids.size>0){//Reset ids
            ids = new Set();
            i=0;
        }
        if(ids.has(pageData[i][0]) || inserted.has(i)){
            i++;
            continue;
        }
        ids.add(pageData[i][0])
        pages.push(pageData[i]);
        inserted.add(i);
        i++;
    }
    //Add the rest of the elements to the new array
    pageData.forEach((el,index)=>{
        if(!inserted.has(index))
            pages.push(el);
    });
    return pages;
}

const results = [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']
];


const paginate = (results)=>{
    const max =results[0] ;
    let pageData = results.slice(2);
    let pages = [];
    let ids = new Set();
    let inserted = new Set();
    let i=0;
    while(i<pageData.length){
        if(pages.length%max==0 && ids.size>0){//Reset ids
            ids = new Set();
            i=0;
        }
        if(ids.has(pageData[i][0]) || inserted.has(i)){
            i++;
            continue;
        }
        ids.add(pageData[i][0])
        pages.push(pageData[i]);
        inserted.add(i);
        i++;
    }
    //Add the rest of the elements to the new array
    pageData.forEach((el,index)=>{
        if(!inserted.has(index))
            pages.push(el);
    });
    return pages;
}

console.log(paginate(results));

let results = [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']
];
const alreadyExists = (val, arr) => {
   return arr.find((a) => a[0] === val); 
}

const paginate = (results)=>{
    let pageData = results.slice(2);
    let pages = [];
    const max =results[0] ;
    const maxPages = Math.ceil(results[1]/results[0]);
    let indexToStartAt = 0;
    let yetTo = [];
    for(let i=0; i<maxPages; i++) {
        pages[i] = [];
        
        let j=indexToStartAt;
        while(pages[i].length < max && j < pageData.length) {
            let considering = pageData[j];
            if(alreadyExists(pageData[j][0], pages[i])) {
                yetTo.push(j);
            } else {
                pages[i].push(pageData[j]);
            }
            j++;
        }
        indexToStartAt = j;
        yetTo.slice().forEach((entry, index) =>{
            if(entry) {
                let considering = pageData[entry];
                if(!alreadyExists(pageData[entry][0], pages[i])) {
                    pages[i].push(pageData[entry]);
                    delete yetTo[index];
                }
            }
        });
        if(pages[i].length < max) {
            for(let k=0; k<yetTo.length && pages[i].length < max; k++){
                if(yetTo[k]) {
                   pages[i].push(pageData[yetTo[k]]);
                   delete yetTo[k]; 
                }
            }      
        }
    }
    return pages;
}

console.log(paginate(results));

{
let results = [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']
];
const alreadyExists = (val, arr) => {
   return arr.find((a) => a[0] === val); 
}

const paginate = (results)=>{
    let pageData = results.slice(2);
    let pages = [];
    const max =results[0] ;
    const maxPages = Math.ceil(results[1]/results[0]);
    let indexToStartAt = 0;
    let yetTo = [];
    for(let i=0; i<maxPages; i++) {
        pages[i] = [];
        
        let j=indexToStartAt;
        while(pages[i].length < max && j < pageData.length) {
            let considering = pageData[j];
            if(alreadyExists(pageData[j][0], pages[i])) {
                yetTo.push(j);
            } else {
                pages[i].push(pageData[j]);
            }
            j++;
        }
        indexToStartAt = j;
        yetTo.slice().forEach((entry, index) =>{
            if(entry) {
                let considering = pageData[entry];
                if(!alreadyExists(pageData[entry][0], pages[i])) {
                    pages[i].push(pageData[entry]);
                    delete yetTo[index];
                }
            }
        });
        if(pages[i].length < max) {
            for(let k=0; k<yetTo.length && pages[i].length < max; k++){
                if(yetTo[k]) {
                   pages[i].push(pageData[yetTo[k]]);
                   delete yetTo[k]; 
                }
            }      
        }
    }
    return pages;
}

console.log(paginate(results));
}

from heapq import heappush, heappop
import math
from collections import deque
def paginate(records_per_page):
    data = [
        [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"]
    ]

    records = len(data)
    pages = math.ceil(records/records_per_page)
    output = [[] for i in range(pages)]
    page = 0
    q = []
    for d in data:
        heappush(q, (-d[2], d))

    seen = set()
    while q:
        if len(output[page]) == records_per_page:
            page += 1
            seen.clear()
        point, record = heappop(q)
        if record[0] not in seen:
            seen.add(record[0])
            output[page].append(record)
        else:
            prev = deque()
            prev.append(record)
            added = False
            while True:
                if q:
                    p, r = heappop(q)
                    if r[0] not in seen:
                        seen.add(r[0])
                        output[page].append(r)
                        added = True
                        break
                    else:
                        prev.append(r)
                else:
                    break
            if not added:
                output[page].append(prev.popleft())
            while prev:
                r = prev.popleft()
                heappush(q, (-r[2], r))
                
    return output