Airbnb店面挂经

Job Hunting Interview
, , , , ,
1

下午的新鲜热乎面筋， 算是运气比较好都是面筋题， 但是半裸考跪了-。-

  1. median of large stream. hints给了无数个， 最后套出来时间复杂度nlogn， 空间复杂度必须是1（logn）？，这题需要注意的是LARGE，最后的思路应该是二分 quickselect。对不起面试官小哥，就差答案怼我脸上了
  2. imagine you’re an airbnb host, find largest income by arrange your reservations. 也就是 input 一串长度为二的array， 代表入住和退房时间，要求reservation time不能overlap， 求最大能accommodate的晚数，提示greedy不行

都说遇到国人不太好，但是我碰到的俩都好nice啊，第一个小哥好可爱！（喂现在是花痴的时候吗？？）
接下来的面试加油吧， 有准备的可不能再挂了！！
祝大家快快上岸，offer多多

2

想问一下楼主这道题有说不能通过数组index去索引吗？因为之前看到的版本是不能通过index去索引，不能用index的话该怎么用quickselect啊。

我做的可以索引，不能用index的是不是LC上那道2 pq 啊？

3

能不能说一下和正常quickselect有何不同？
第二题应该是DP

正常的quickselect是通过swap来确定你选的数的位置，但是由于输入形式是stream，相当于immutable的，所以只能一遍一遍地去数大于选定数的数有多少个，小于的有多少个

4

还想请问一下楼主large的要求是需要用long来存index吗

我写的是python， large主要用来限制你的space complexity，也就是不能像利口上那题用两个heapq