booking 面经

下班店面了国内booking 高级岗，体验一般。


题目很简单，陈述一堆背景后，给出一个数组，里面是map, hash, dict, you name it,
然后，给一个需要入住的客人总数，比如5，

1. [
   
2.     {id: 0, price: 180, guests: 1},
   
3.     {id: 1, price: 230, guests: 2},
   
4.     {id: 2, price: 220, guests: 2},
   
5.     {id: 3, price: 310, guests: 3},
   
6. ]

复制代码

求能满足客人入住所需要的最低价格，房间容量，是可能会超过客人总数的，比如有一个房间 {price: 1, guests

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ts'], -1):
因为， num_guest 不会是N， 房间容量不会是无穷，

所以两层循环时间复杂度是O(n)， 各位大神还有啥高招？

也许挂了，他们感觉并不理解我再说什么。。。代码如下。。

1. 
   
2. def binguan(room_list, num_guest):
   
3.     # 1. 找出容量大于等于需求的房间，里面取最小值
   
4.     haofangjian_arr  = [r for r in room_list if r['guests'] >= num_guest ]
   
5.     haode_room = min(haofangjian_arr, key=lambda r: r['price'])
   
6. 
   
7.     # 2. 使用动态规划，在容量小于需求的房间里找出最便宜组合
   
8.     dp = [float("inf")] * (num_guest + 1)
   
9.     best_dp_room = [[] for _ in range(num_guest + 1)]
   
10.     dp[0] = 0
    
11. 
    
12.     for r in room_list:
    
13.         for i in range(num_guest, r['guests'], -1):
    
14.             new_price = dp[i - r['guests']] + r['price']
    
15.             if dp[i] > new_price:
    
16.                 dp[i] = new_price
    
17.                 best_dp_room[i] = best_dp_room[i - r['guests']] + [r]
    
18.    
    
19.     dp_best = sum([r['price'] for r in best_dp_room[num_guest]])
    
20.    
    
21.     return best_dp_room[num_guest] if dp_best <= haode_room['price'] else haode_room
    
22. 
    

复制代码

看代码看得不是特别明白，说错的话抱歉哈。
感觉楼主这个代码是不是解决不了几个房间容量和大于num_guest 的情况，因为每次是从 num_guest 往下遍历的。
比如 capacity: [2, 2, 3], num_guest: 6

lesterlilijing 发表于 2023-5-22 08:32
看着也是01背包问题。面试官说不能在选的意思应该是，每个房间只能选一次

是的，每个房间只能选一次，主要是比价惊讶的是，我上来给DP，考官貌似觉得我方向不对。。。哈哈

看着也是01背包问题。面试官说不能在选的意思应该是，每个房间只能选一次

没积分看不到尴尬

攒分看面经

lz 面了啥系统设计呢

回溯（recursion）+ Memorisation 也是可以接受的方法

大于需要人数的不能叫edge case, 有点confusing， 而且代码直接把他们找出来相当于一次full table scan 如果表特别大 并不是很划算 而且造成代码不够优雅 时间复杂度也不是 N 而是 NM

有OA的题目吗

Moonrise8101 发表于 2024-9-27 12:11
有OA的题目吗

OA很简单，两道题是件很充足，一个半小时的时间大概四十分钟就做出来了