1.查找第k大的数：快速选择法，On（这里讲的都是时间复杂度）。快速选择法：由于快速排序每次排序都可以用On时间求出基准是第几大的数且左边都比基准小，右边都比基准大。若第一次求出基准是第i大，若ik，以i为右边界递归左边，每次减小一半查找范围，直到i==k，总共时间为On。2.查找最大k个数(k远小于n）：建一个大小为k的优先队列（小根堆），klogk，对于剩下的元素，若大于堆顶则拿掉堆顶最小的再插入，总共用nlogk的时间找到最大k个(堆顶为第k大的）。共计(n+k)logk<2nlogk=nlogk，k很小时视为On，k大时用方法4。3.频繁查找第k大的数（数组变化)：先用方法2找出原始数组最大k个数，klogk，若要新增元素，先对比堆顶，若大于堆顶则先移除堆顶再插入堆，这时堆顶为第k大的数。每次查找复杂度为logn。4.频繁查找第k大的数(k变化)：排序，nlogn，每次查找时间为O1。5.查找a~b之间的所有元素：先用快速排序法找到第a大和第b大的数，用On，再遍历一次，选出位于这两个数之间的数。总共On。6.频繁查找，数组和k同时变化：先建一个二叉搜索树nlogn，维护每个结点的子树大小，查k时从根节点开始，若小于左子树大小，直接进入左子树，否则k-=左子树大小后进入右子树，每次查找logn，每次插入时将经过的结点子树大小++，也是logn。7. 查找数据流的中位数：维护一个最大堆和一个最小堆，满足最大堆所有的数都小于最小堆的数，当两个堆数量相等时，中位数就是堆顶平均，若最大堆比最小堆大1，中位数就是最大堆顶，插入新元素时，奇数次考虑插入最大堆，若大于堆顶则插入最小堆，再把最小堆堆顶插入最大堆。偶数次类似。#面试题刺客退退退#

一个小时，手撕：二叉树中序遍历，数组中的第k个最大元素面试管很友好，开始介绍了十分钟业务，后续简单聊了聊项目（点评）1.线程和进程2.为什么需要加锁？java中有什么锁？3.java的内存模型。垃圾回收机制。4.http和https的区别，https的加密握手5.tcp和udp的区别6.tcp有哪些特点（如何实现可靠传输的）7.DNS解析7.在浏览器中输入一个url会发生什么手撕第二个用最小堆没写出来，我太菜了，后续面试官说可以先排序直接去遍历寻找，很简单的一道题

（面试时长30min）自我介绍怎么解决问题，难点项目相关提问http2.0相对于1.1的区别http缓存（深挖）学习前端的方法改变this指向的方法就记得这些了，其他不记得了疑似kpi，摄像头也没开，一到马上30min他就准备撤了，然后我出了会议室没多久就挂了

美团面了大概四十分钟，全程细节拷打，面完汗流浃背，感觉过不了了，看面经吧1.说说你平时是怎么送餐的?直接傻瓜式回答拧车把就走了2.如果送餐途中下雨了，你会怎么办?回答找个地方躲着，然后就问我那订单超时怎么办，答不出来了。。。3.如果有个地方爆单，同时有多个不同楼层但是是同一栋楼的地方下单，可能是什么情况?答不出来，乱蒙了个可能在开派对，有没有大佬知道的4.如果到了商家，但商家还没把餐备好，你会怎么做?直接回答干等着了，然后感觉这样回答不太好,又补了句我可能会催催商家。。。5.实际送餐过程中有没有考虑过使用多部手机?我说配送账号就一个，没必要使用多部手机。面试官好像不太满意6.送到餐了，但客户-直不来取餐,你会怎么办?阻塞等待吗?我说会打电话催促客户，客户-直不来的话就把餐放到地点，然后拍照走人，然后问我这样做有没有考虑过外卖丢失的情况，外卖丢失怎么办，完了，又掉进坑了7.有没有送错餐的情况?我说实际没遇过这种场景，面试官又不太满意了。。。搞不懂，- 定要有实际解决过出错的经验吗。。。没出错不是更好吗。。。8.餐箱满了，但你又接单了，餐箱放不下了，出现了Out Of Box,如何解决?我说一般我会每次接单前检查下餐箱容量，有空间才会接新的单，又追问这样会不会影响接单效率，如果被其它骑手抢单了怎么办?完了，双掉进坑了。。。9.送餐过程有没有把外卖进行分类?我说我一般电动车前后有两个餐箱，前面放带有汤水易撒的，后面放比较干的外卖。总算是能答出一题了10.看了下我送的最快的一单，问我为什么那一单10s就送达了。因为客户就在店里面，当堂点外卖是为了用券。。。我这个订单是不是有点水了，但鼠鼠是真没什么订单拿得出手了做了道算法，一道贪心,给定单子信息，寻找最短配送路线，之前刷过，10分钟a出来了