Airbnb onsite 跪经

Tianwen

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由 zzwcsong 于 2019-2-19 01:04 编辑

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

面试后第二天收到了据信，猎头不愿意透露任何feedback，也能理解。airbnb的待遇很好，但面试下来，我看不出这家公司牛逼的tech。Anyway， good luck guys！

xdc_901026

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

hj867955629

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

cencenseven

dfs

class solution:
def dfs(self, start_pos, profit, prev_end):
#find next eligible request
while start_pos < len(self.requests) and prev_end > self.requests[start_pos][0]:
start_pos += 1
#if no eligible session left can be added: track the profits
if start_pos >= len(self.requests):
if profit > self.max_profit:
self.ans = self.cur[:]
self.max_profit = profit
else:
#select this interval
new_profit = profit + self.requests[start_pos][1] - self.requests[start_pos][0]
self.cur.append(self.requests[start_pos])
self.dfs(start_pos+1, new_profit, self.requests[start_pos][1])
self.cur.pop()
#not select this interval
self.dfs(start_pos+1, profit, prev_end)
def optimize_requests(self, requests: list):
self.requests = sorted(requests)
#for each request, we have options to have it or not have it
self.ans = []
self.cur = []
self.max_profit = 0
self.dfs(0, 0, 0)
print("max profit is {}".format(self.max_profit))
return self.ans

复制代码

twilightgod

感觉面的还可以啊，楼主觉得是哪跪了

jackalsin

楼主，第5题你怎么做的。。。我觉得除了binary search没有啥特别好的想法，

jackalsin

xdc_901026 发表于 2019-2-18 08:05
binary search咋做？我能想到的就是先把intervals按start排序，然后用dfs去取不重合的intervals，取完后 ...

类似于treeset不断insert，我印象中700多有道差不多的解法，就是容易错。。。

MercyAPDY

同问，楼楼觉得是哪里跪呢

jason524

jackalsin 发表于 2019/02/18 08:37:41

类似于treeset不断insert，我印象中700多有道差不多的解法，就是容易错。。。

第一感觉也是dfs 听你这么一说有点虚啊

Tianwen

本人粗鄙的想法。

def optimize_requests(requests: list):
if not requests:
return 0, []
requests = sorted(requests, key=lambda x: (x[0], -x[1]))
print(requests)
# end time for current plan, -total_profit current plan, path
pq = [(requests[0][1], requests[0][0] - requests[0][1], [requests[0]])]
for idx, item in enumerate(requests[1:], 1):
if requests[idx][0] == requests[idx - 1][0] and requests[idx][1] <= requests[idx - 1][1]:
continue
start, end = item
profit, path = 0, []
if pq[0][0] <= start:
_, profit_old, path_old = pq[0]
profit, path = profit_old, path_old
heapq.heappop(pq)
profit += -(end - start)
path.append((start, end))
heapq.heappush(pq, (end, profit, path))
for plan in pq:
print(plan)
print("Final answer:\n")
_, profit, path = min(pq, key=lambda x: x[1])
print(-profit, path)
inputs = [(1, 3), (2, 5), (10, 17), (8, 11), (16, 21), (10, 11), (16, 17), (23, 26), (25, 30)]
optimize_requests(inputs)

复制代码

Tianwen

本人粗鄙的想法。

def optimize_requests(requests: list):
if not requests:
return 0, []
requests = sorted(requests, key=lambda x: (x[0], -x[1]))
print(requests)
# end time for current plan, -total_profit current plan, path
pq = [(requests[0][1], requests[0][0] - requests[0][1], [requests[0]])]
for idx, item in enumerate(requests[1:], 1):
if requests[idx][0] == requests[idx - 1][0] and requests[idx][1] <= requests[idx - 1][1]:
continue
start, end = item
profit, path = 0, []
if pq[0][0] <= start:
_, profit_old, path_old = pq[0]
profit, path = profit_old, path_old
heapq.heappop(pq)
profit += -(end - start)
path.append((start, end))
heapq.heappush(pq, (end, profit, path))
for plan in pq:
print(plan)
print("Final answer:\n")
_, profit, path = min(pq, key=lambda x: x[1])
print(-profit, path)
inputs = [(1, 3), (2, 5), (10, 17), (8, 11), (16, 21), (10, 11), (16, 17), (23, 26), (25, 30)]
optimize_requests(inputs)

复制代码

Tianwen

本人粗鄙的想法。

def optimize_requests(requests: list):
if not requests:
return 0, []
requests = sorted(requests, key=lambda x: (x[0], -x[1]))
print(requests)
# end time for current plan, -total_profit current plan, path
pq = [(requests[0][1], requests[0][0] - requests[0][1], [requests[0]])]
for idx, item in enumerate(requests[1:], 1):
if requests[idx][0] == requests[idx - 1][0] and requests[idx][1] <= requests[idx - 1][1]:
continue
start, end = item
profit, path = 0, []
if pq[0][0] <= start:
_, profit_old, path_old = pq[0]
profit, path = profit_old, path_old
heapq.heappop(pq)
profit += -(end - start)
path.append((start, end))
heapq.heappush(pq, (end, profit, path))
for plan in pq:
print(plan)
print("Final answer:\n")
_, profit, path = min(pq, key=lambda x: x[1])
print(-profit, path)
inputs = [(1, 3), (2, 5), (10, 17), (8, 11), (16, 21), (10, 11), (16, 17), (23, 26), (25, 30)]
optimize_requests(inputs)

复制代码