一面
先做个自我介绍。
如果让你来实现HashMap,你会怎么做?put的过程?hashcode怎么找到数组下标?hashmap如何扩容,是直接复制到新的数组吗?为什么新数组是原数组长度的两倍?
(1)数组+链表,红黑树。
(2)通过hashcode找到数组下标(见3),equals比较key,如果找到了key,则用新的值覆盖旧值,否则插入到末尾。
(3)hashcode和右移16位的hashcode做异或运算,得到的结果h和(数组长度-1)做与运算可以得到下标,这也是为什么扩容时数组长度是两倍的原因(2的次幂-1是全1的,与任何数都会介于0~length-1)。
(4)扩容时创建长度为原来两倍的数组,链表直接头插法插入到数组上。
(当时很多没答上来,比较菜,囧)
万一冲突数量比较多怎么办,这样就形成了一个很长的链表?
>>红黑树,类平衡二叉树,查找效率lgn。
如果让你实现线程安全的HashMap呢?
>>最简单的方法是加上synchronized,但是这样效率会很慢,jdk的ConcurrentHashMap是高效的线程安全的hashmap.....不会了。。
链表的查询时间复杂度是多少?
>>O(N)
不改变链表结构情况下,如何提高链表查询效率?
>>我说Map从值到结点的映射,面试官说这确实是个解决思路(言外之意是还有其他办法,比如跳表)
TCP如何保证可靠性?
>>流量控制(滑动窗口),拥塞控制,超时重传,确认应答机制,
面试官:介绍下流量控制和拥塞控制?
>>流量控制:为了平衡发送端和接收端之间的速度不一致问题。
>>拥塞控制:慢开始,拥塞避免,快重传
进程交互的方式有哪些?
>>信号机制,信号量机制,共享内存,消息队列,管道机制(父子进程之间)
信号量和信号的区别?
>>信号量是一种同步互斥机制,保证进程有序使用资源;信号是一种异步信息,通知进程某件事情发生了。(我没答上来,emm)
笔试题
给出一个字符串数组:
{
{“X”,“X”,“X”,“X”},
{“X”,“O”,“O”,“X”},
{“X”,“X”,“O”,“X”}
{“X”,“O”,“X”,“X”}
}
将被X包围的O换成X,必须是上下左右都被包围才能换。
结果为:
{
{“X”,“X”,“X”,“X”},
{“X”,“X”,“X”,“X”},
{“X”,“X”,“X”,“X”}
{“X”,“O”,“X”,“X”}
}
我的分析思路:
- 要改变的O值一定不会在外围,一定在中间。
- 如果O的上下左右都是X,把O换成X;
- 如果O的上下左右存在O,那这两个O要么同时变为X(多个邻接的O整体被X上下左右包围),要么同时不变;
- 把中间的O存起来,深度遍历到边缘,边缘都是X,那么整体改变为O,若边缘存在O,那整体都不改变。
面试官:这确实是一个解题思路,但还有更好的方法,你想一下从结果的角度考虑,外围出发,把不改变的O找出来,剩下的就是需要改变的O。
不知道能不能过,祈祷~