字节跳动后端开发一面(持续更新ing)

一面

先做个自我介绍。

如果让你来实现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”}

}

我的分析思路:

  1. 要改变的O值一定不会在外围,一定在中间。
  2. 如果O的上下左右都是X,把O换成X;
  3. 如果O的上下左右存在O,那这两个O要么同时变为X(多个邻接的O整体被X上下左右包围),要么同时不变;
  4. 把中间的O存起来,深度遍历到边缘,边缘都是X,那么整体改变为O,若边缘存在O,那整体都不改变。

面试官:这确实是一个解题思路,但还有更好的方法,你想一下从结果的角度考虑,外围出发,把不改变的O找出来,剩下的就是需要改变的O。

不知道能不能过,祈祷~

上一篇:win10ltsb2016升级到LTSC2019并删除Windows.old


下一篇:ing