滴滴9.13笔试

A了 #23届找工作求助阵地#  #滴滴#

请问滴大人都是在招什么超人呀，看不上可以简历挂或者一面挂，没必要搞这样一个算法题。面试是实现lru并且并发安全，我问是要写lru吗，然后问我用什么数据结构，我说用链表，他说链表时间复杂度太大了，redis源码用的什么结构，然后咱就试探性写了linkedhashmap，然后用sync修饰get等方法，然后面试官看了一眼说你这是用的人家封装好的linkedhashmap，你得自己实现这个类，好好好，投降!!

第一题，每个玩具有一个电量值，你有一块电池总电量为m，现在要选几个连续的玩具，且这几个玩具的电量总和不能超过m，求能最多选几个玩具？滑动窗口题，初始left和right为0，right不断+1，判断right和left之间的玩具电量和是否大于m，若大于，则left+1，直到电量和小于m，更新res变量max(res,right-left+1)，这里电量和可以用前缀和做，也可以每次right或者left变化的时候动态维护。第二题，有n首歌各自有自己的排名1~n，输入n行，每行两个数，op，x，op为1则表示排名为x的歌排名应该变低，op为-1则表示排名为x的歌排名应该变高，op为0则表示排名不变，现在问能否根据这n行输入构造出一个满足要求的歌排名？开一个n+1的bool数组occupy，occupy[i]表示排名i被占用了，先根据输入按照x排序，遍历一遍处理op=0的，对应的accupy[x]=True即可，再遍历一遍处理op=1的，从前往后遍历occupy，如果有False的，占用掉，如果找不到False，则返回“NO”，再遍历一遍处理op=-1的，从当前位置往后遍历找有没有False的。

### 线程池的一个情况 #### 拒绝策略 使用场景 （不知道呀）### B+树 为什么快（回答了 二叉树 b树还不够）- 页的大小- node节点大小- 影响因数有那些### 二叉树和B+树二叉树其实层数影响并不大，为什么呐（不够）### es减少索引量，为什么快（原理呐）### 算法 链表+法就这几个问题，搞了一个半小时，确实难搞9.13 二面，许愿hr面呀，唔