2019年3月23日字节跳动一面总结
23号这天一次性来了三场面试，面试的问题都有点混了。
首先自我介绍，老样子，介绍一下自己，介绍一下项目。
1.说说你的项目，主要有什么功能
这个因项目而定吧，大体介绍一下。
2.了解HashMap吗？说一下吧
HashMap和HashTable常常被放在一起对比，HashMap和HashTable都是底层通过哈希表来存储信息的容器，哈希表是用空间换时间算法的代表。在插入一个数据时，首先计算这个这个对象的Hash值，这里HashMap和HashTable有一点不同，通过他们源码的对比可得知，HashTable的值如果是null直接抛出空指针异常，计算键的hash值则是调用键对象的hashcode()方法得到hash码并在此基础上进行一个处理得到最终hash值，这样的话如果键是null也会在调用hashcode()方法是抛出空指针错误。但是HashMap不同，HashMap中的hash值是通过自带的算法计算的，这个算法中会处理null值。因此HashMap可以插入null的键值。
在插入数据时会发生hash碰撞，Hashmap和HashTable都是挂桶来解决问题的，即在数组的每一项上通过链表存储相同hash码的值。但是HashMap在JDK8中得到了优化，当同一hash的值数量超过8时链表会变为红黑树，红黑树的结构稳定，查找效率是logN，比链表的N效率更高。当同一hash的值数量小于6时，红黑树结构会变回链表，因为当基数比较小时，logN和N相差并不多，而且红黑树的维护很复杂，这样反而链表效率更高。
HashMap是注重效率的Map容器，因此他不是线程安全的，高并发情况下多个线程同时插入数据，在resize时可能产生链表环，之后在get时会陷入死循环。如果追求线程安全，可以选择HashTable或者ConcurrentHashMap。HashTable几乎在每个方法的定义处加上synchronized关键字解决同步问题，但是synchronized是一种重量级锁的实现，效率很低。在JDK5中加入了ConcurrentHashMap，它通过分段锁和volatile关键字实现线程同步，并有不错的效率。
关于面试中的Map问题，可以参考我之前的博客https://blog.csdn.net/yan245294305/article/details/88709760
3.我们来做一道题吧
要求：合并N个有序链表
代码：不贴了，归并算法实现即可
4.进程间的通信方法
大体上分为5种，有管道通信，共享内存通信。剩下的我忘了。。。。
（操作系统是我的软肋，一下午三场面试，问了三次进程间的通信，我都不会，太难受了，之后恶补操作系统）
5.忘了问的是什么了。。。
6.来做一个设计题目吧。设计一个外卖系统，外卖系统中有骑手和用户，设计一下这两个类吧
class User {
String ID;
String name;
String phone;
//用作记录用户的信用度或者状态信息
String state;
String[] address;
}
class Driver {
String ID；
String name;
String phone;
//用作记录用户的信用度或者状态信息
String state;
String localtion;
}面试官：如果我想通过分析用户的地理位置来给各个地区分派相应数量的骑手怎么做
我：可以给User类中加上一个用户点外卖的次数，然后通过计算得出该用户在每个地址的点外卖的次数，然后给比例大的地方分派更多的骑手。
面试官：怎么给骑手规划路线
我：设计一个点阵图，把每个等待配送的用户的点进行标记，根据骑手当前的位置通过最短路径算法给出一条最短路径。
面试官：如果骑手在配送的过程中遇到顺路的订单怎么办
我：把订单的商家和用户的点在点阵图上标记出来，如果在骑手配送的路线的周边就顺路带一下
面试官：好，那你考虑到当前订单超时的情况了吗
我：。。。。那就估算一下骑手顺路带的订单一共要花费多长时间，如果能在当前订单时间内完成就顺路带。但是还有很多情况，比如可以顺路取餐，然后先给当前订单的用户送外卖，然后再给顺路订单的用户送外卖（说到这里我已经晕头转向的了）
面试官：嗯嗯，看来这个要考虑的因素还不少呢是吧
我：嗯嗯，是挺多的（2333333）
7.上个问题有点太难了，换一个问吧。现在我有一本字典，要把字典中的单词都存储起来，然后给出一个单词，找出包含这个单词的所有单词。怎么设计
用一个树结构保存字典中的数据，每个树的根节点是单个字母，然后儿子节点是包含这个字母的两个字母的单词，然后每一层的单词都比上面一层的字母数多一这样保存，然后检索包含指定单词的单词集就从头遍历树，如果某个单词符合条件就加入容器中。最后返回容器中的数据。
8.这个设计的时间复杂度是多少
我：logN吧，就是检索树的复杂度
面试官：是吗？我要的是所有包含此单词的单词集合
我：（想了一下）NlogN，因为要从这个单词的每个字母开始遍历，因此和单词的长度有关
面试官：嗯。还有其他效率更高的方法吗？
我：（想了一会儿）想不到了。
面试官：嗯好，时间差不多了，先就这样，我把面试记录同步给HR。
我：OK
小结
这次面试时常1小时，20分钟的基础知识，10分钟的手写代码，30分钟的设计题。我之前都没怎么准备过设计题，这次答的不太好，我一度以为自己挂在一面了，但是还是进二面了。