美团再见

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他就准备撤了，然后我出了会议室没多久就挂了

大概多久会发邮件填详细信息呀急急急