美团3.24 一面凉经
上来两道算法题
1， two sum
但是 元素可以有重复，要求找到所有加和为目标值的两个数的坐标
例 1 3 1 2 2 3， target 4
返回【0 1，1 2，3 4， 0 5， 2 5】
我是用Map<Integer, List<Integer>> key是当前值与target的差值，index是对应的坐标的array，比如对于第二个1，我的map里 应该加入<3, [0, 2]>
遍历所有元素，要是map里含有这个元素，就用当前坐标，与map对应key的list里面所有坐标组合，加入答案List里面， 再用自己的值更新map，规则如上。
2， 多 sum， 要求返回加和为target的数字组合，可以为任意长度。元素没有重复
例 1 2 3 4 5 6， target 6， 返回[[1,2,3], [6]]
我用的是back tracking，也有人叫dfs。但是 这么做时间复杂度是n！，我也有和面试官讨论可以先sort array来减少时间复杂度。但是怎么减也逃不掉n！。
空间复杂度，我答得是 栈上有O（n）因为栈深最大是O（n）
但是我看面试官在这里追问了我一下，栈深一定是O（n）吗，我有点懵，因为我觉得无论如和基本都会到O（n），除非加的数的和已经大于target可以提前停，但是这个不能一定保证啊，所以我觉得worst case还是O（n）
接下来是基础知识
1 Hash Map，实现 1.7 Entry Array 头插法， 1.8 超过8 转红黑树，尾插法。
2 Hash Map线程安全吗？ （这块面试官提到Hash Table，但是我提到concurrent hash map然后面试官直接让我讲concurrent 的了）不安全 安全的有concurrent hash map，实现1.5之前用的synchronize， 后来1.8用的CAS获取头部元素，头部不为空则用synchronize锁住头，再进行插入。
3 因为之前提到CAS，讲讲CAS。
4 讲讲死锁。死锁产生的4个条件，如何避免死锁。
5 synchronized的实现，锁升级等
6 单例模式，答DCL
7 DCL中violate的作用 答可见性，与禁止指令重排序。
8 数据库，隔离等级。读未提交，读提交，可重复读， 串行化。
9 为什么有串行化这个等级。答：可以解决可重复读未完全解决的幻读问题。
10 索引，聚集非聚集
11 索引覆盖，最左原则
12 索引回表
13 索引实现 B+树，为啥B+。答 索引node不包含数据，一次硬盘读写可以拿到更多节点，减少硬盘IO。以及叶子节点，相互联通，方便对树进行操作。
14 手写query， 查班上同学，总分大于300的人的Id。一开始用了拼接表，后来想了想用了 having一条语句搞定。
15 最后一题：有一个抢票系统，只有1000张券，请问如何再整点秒杀情况下，避免超发，同时又保证效率。
我内心。。。。。 我咋知道。。。。完全没过这种题。。。。于是我只能说加锁，但是这样效率就是会低。
面试官提示，不一定是技术层面的解决方案，但是我一时间没想出来，要是有小伙伴有想法可以留言回复一下～
最后面试就结束了，总体上我觉得答得还可以吧？基本都答上来了。
有几点担心的就是第二个算法时间复杂度太高了，以及基础知识，虽然大部分答出来了但是还是有一些遗漏。
然后有探探口风，面试官说我数据库方面掌握的不错。
但是我总感觉面试官有隐约还是有露出一些不是很满意的样子。
哎•́︿•̀，可能美团bar比较高吧。
祈福2面 Orz
