Airbnb Interview Question
Software EngineersCountry: United States
Interview Type: Written Test
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));
{
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
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)
- aonecoding October 13, 2017