【面经】字节跳动-后端开发-2019秋招

https://zhuanlan.zhihu.com/p/50186804

因为每个人的理解不太一样,所以我在这里就不给出所谓的答案了,大家可以根据自己的理解加以描述,我只在一些地方做出一些提示。有的问题已经忘了,大概也就这些了。


一面:

进程和线程以及它们之间的区别(我通过对比多个面经,发现这道是必考题,划重点)

线程用于小任务,而进程用于更多的'重量级'的任务- 应用基本执行。 一个线程和进程之间的另一个区别是,在同一进程中的线程共享相同的地址空间,而不同的进程没有。 因此线程可以读写同样的数据结构和变量,便于线程之间的通信。 

定义方面:进程是程序在某个数据集合上的一次运行活动;线程是进程中的一个执行路径。

进程间的通信方式和对应的同步方式,你用过吗?具体怎么用?

进程间的通信主要是指多个进程间的数据交互。
同步主要指维护多个进程或者线程之间数据的准确性和一致性。

进程通信方式:管道(Pipe)、信号(signal)、信号量(semophere)、消息队列(message queue)、共享内存(shared memory)、套接字(socket)。

同步方式:将线程串行化(wait notify方法来睡眠和唤醒线程)、互斥锁(加锁 mutex)、管程、临界区、信号量

TCP和UDP的区别

TCP的优点: 可靠,稳定。TCP的可靠体现在TCP在传递数据之前,会有三次握手来建立连接,而且在数据传递时,有确认、窗口、重传、拥塞控制机制,在数据传完后,还会断开连接用来节约系统资源。TCP的逻辑通信信道是全双工的可靠信道。 
TCP的缺点: 慢,效率低,占用系统资源高,易被攻击 TCP在传递数据之前,要先建连接,这会消耗时间,而且在数据传递时,确认机制、重传机制、拥塞控制机制等都会消耗大量的时间,而且要在每台设备上维护所有的传输连接,事实上,每个连接都会占用系统的CPU、内存等硬件资源。 而且,因为TCP有确认机制、三次握手机制,这些也导致TCP容易被人利用,实现DOS、DDOS、CC等攻击。

UDP的优点: 快,比TCP稍安全 UDP没有TCP的握手、确认、窗口、重传、拥塞控制等机制,UDP是一个无状态的传输协议,所以它在传递数据时非常快。没有TCP的这些机制,UDP较TCP被攻击者利用的漏洞就要少一些。但UDP也是无法避免攻击的,比如:UDP Flood攻击……
UDP的缺点: 不可靠,不稳定。因为UDP没有TCP那些可靠的机制,在数据传递时,如果网络质量不好,就会很容易丢包。
面向数据报:不能够灵活的控制读写数据的次数和数量,应用层交给UDP多长的报文, UDP原样发送, 既不会拆分, 也不会合并。但是不会存在粘包的问题。

三次握手、四次挥手,为什么?

三次握手:为了保证接收方和发送方的接收能力和发送能力都正常。
四次挥手:为了释放全双工的信道。所以是单独释放和确认的。

这是因为服务端在LISTEN状态下,收到建立连接请求的SYN报文后,把ACK和SYN放在一个报文里发送给客户端。而关闭连接时,当收到对方的FIN报文时,仅仅表示对方不再发送数据了但是还能接收数据,己方是否现在关闭发送数据通道,需要上层应用来决定,因此,己方ACK和FIN一般都会分开发送。

TCP如何保证传输的可靠性?

TCP通过序列号、确认应答、超时重传、拥塞控制来保证传输的可靠性

确认应答机制&序列号
TCP将每个字节的数据都进行了编号,即为序列号。
每一个ACK都带有对应的确认序列号,意思是告诉发送者,我已经收到了哪些数据;;下一次你从哪里开始发。

超时重传&序列号
主机A发送数据给B之后, 可能因为网络拥堵等原因, 数据无法到达主机B; 如果主机A在一个特定时间间隔内没有收到B发来的确认应答, 就会进行重发;主机A未收到B发来的确认应答,也可能是因为ACK丢失了,因此主机B会收到很多重复数据,这时候利用序列号可以使得主机B来实现数据报文的去重。

拥塞控制
每次发送数据包的时候, 将拥塞窗口和接收端主机反馈的窗口大小做比较, 取较小的值作为实际发送的窗口。
拥塞控制, 归根结底是TCP协议想尽可能快的把数据传输给对方, 但是又要避免给网络造成太大压力的折中方案。

TCP如何提高传输效率:

TCP通过滑动窗口、流量控制、延迟应答、捎带应答来提升传输的效率

滑动窗口机制
1. 窗口大小指的是无需等待确认应答而可以继续发送数据的最大值.
2. 发送窗口内字段的时候, 不需要等待任何ACK, 直接发送;
3. 收到第一个ACK后, 滑动窗口向后移动, 继续发送下一个窗口字段的数据; 依次类推;
4. 操作系统内核为了维护这个滑动窗口, 需要开辟发送缓冲区来记录当前还有哪些数据没有应答; 只有确认应答过的数据, 才能从缓冲区删掉;
5. 窗口越大, 则网络的吞吐率就越高

流量控制
接收端处理数据的速度是有限的. 如果发送端发的太快, 导致接收端的缓冲区被打满, 这个时候如果发送端继续发送, 就会造成丢包, 继而引起丢包重传等等一系列连锁反应。
1.接收端将自己可以接收的缓冲区大小放入TCP首部中的 "窗口大小" 字段, 通过ACK端通知发送端;
2.窗口大小字段越大, 说明网络的吞吐量越⾼高;
3.接收端一旦发现自己的缓冲区快满了, 就会将窗口大小设置成一个更小的值通知给发送端;
4.发送端接受到这个窗口之后, 就会减慢自己的发送速度;
5.如果接收端缓冲区满了, 就会将窗口置为0; 这时发送⽅方不再发送数据, 但是需要定期发送一个窗口

延迟应答
如果接收数据的主机立刻返回ACK应答, 这时候返回的窗口可能比较小.
窗口越大, 网络吞吐量就越大, 传输效率就越高. 我们的目标是在保证网络不拥塞的情况下尽量提高传输效率;

捎带应答
在延迟应答的基础上, 我们发现, 很多情况下, 客户端服务器在应用层也是 “一发一收” 的.
那么客户端在发送数据的同时,携带对方消息的报文序列号,来顺带通知对方,自己所接收到的报文情况

TCP的拥塞控制,具体过程是怎么样的?UDP有拥塞控制吗?如何解决?

TCP拥塞控制主要有四种方法,滑动窗口机制、慢启动机制、拥塞避免机制、快速重传与恢复。

滑动窗口机制
在发送数据的时候,将发送窗口内的数据全部发送,才会停下来等待ACK,如果接收到对方的ACK信息,则滑动窗口前移。

慢启动机制
在刚开始发送数据的时候,发送窗口取一个较小的值,来防止网络拥塞,同时探测对方的接收能力。如果收到了对方的ACK回应,则按照对方要求的窗口大小来调整发送窗口,否则进行窗口的扩大。窗口大小一开始是1,之后进行指数级别扩大,其中ssthresh为估算的一个发送窗口阈值,当窗口大小超过这个阈值,则之后的窗口每次扩大1,不再是指数级别的扩大。

还有一个概念是 AIMD(加法增大乘法减小):无论在慢启动阶段还是在拥塞控制阶段,只要网络出现超时,就是将发送端的拥塞窗口(cwnd)置为1,ssthresh置为cwnd的一半,然后开始执行慢启动算法;当网络频发出现超时情况时,ssthresh就下降的很快,为了减少注入到网络当中的分组数,而加法增大是执行拥塞避免算法后,使拥塞窗口缓慢的增大,以防止网络过早出现拥塞。

快速重传
快重传算法要求首先接收方收到一个失序的报文段后立刻发出重复确认,而不要等待自己发送数据时才进行捎带确认。当发送方收到ACK之后,进行相应的报文重传。

快速恢复
当发送方连续收到三个重复确认时(代表丢了三个包),执行“乘法减小”算法,慢启动门限减半,从而预防网络发生阻塞。由于发送方现在认为网络很可能没有发生阻塞(因为没有超时),因此现在不执行慢启动算法,而是把拥塞窗口(cwnd)值设置为慢启动门限减半后的值,然后开始执行拥塞避免算法,拥塞窗口cwnd值线性增大

TCP和UDP是传输层协议(物理层、数据链路层、网络层、传输层、会话层、表示层、应用层)

UDP没有拥塞解决措施,当网络拥塞时,直接丢掉UDP的包。解决方式:在传输层之上,利用UDP并改造:如RUDP(传输层)、RTP(应用层和传输层之间)、UDT(应用层)等


算法题:

一个链表,假设第一个节点我们定为下标为1,第二个为2,那么下标为奇数的结点是升序排序,偶数的结点是降序排序,如何让整个链表有序?(分离链表,合并两个有序链表)

先把两个链表按照奇偶性分成两个链表(偶数构造成双向链表);然后一个链表从头部开始,另一个链表从尾部开始,插入第一个链表即可。

假设我们有一个队列,可能存放几千万上亿的数据,我们应该如何设计这个队列?写出来看看?(提问:这个队列是只需要在头尾添加和删除吗?双向队列?答:是的)

创建一个class,利用双向链表构造这个双向队列,实现 getHead() getTail() addToHead() addToTail() popHead() popTail()

一个二维矩阵,从左到右是升序,从上到下是降序,找一个数是否存在于矩阵中(类似于二叉查找树)

假设二维矩阵 g,查找的数为 t
先往右找(二分查找),找到 g[0][i]=a > t > g[0][i+1]=b,(所有行的 i+1, ... 的列的元素肯定全部小于 t,可以忽略),然后从 i 往下找(二分查找),找到 g[j][i] = c > t > g[j+1][i] = d,(说明 0~j 行的 0~i 列均大于 t,可以忽略),然后继续往左找,再往下找,左下不断交替,最终即可判断是否存在 t


二面:

前面面试官已经问了你三道算法了,那我就随便问一道吧:翻转链表(面试官:能不能用c写)....(然后让我一边写一边跟他讲redis)

翻转链表:三个指针解决。p c n 分别记录 前一个节点,当前节点,后一个节点
初始化:前一个节点 p = NULL,当前节点 c = head,后一个节点 n = head.next;
运行:c.next = p; p = n.next ; n.next = c; c = p ; p = n; n = c.next; 注意判断是不是null
结束:while(n != null)

redis:

你知道redis有哪几种数据类型吗?你比较熟悉哪几种?为什么?

redis有五种数据类型:string(字符串),hash(哈希),list(列表),set(集合)及zset(sorted set:有序集合)。

String(字符串)
string 是 redis 最基本的类型,你可以理解成与 Memcached 一模一样的类型,一个 key 对应一个 value。
string 类型是二进制安全的。意思是 redis 的 string 可以包含任何数据。比如jpg图片或者序列化的对象。
string 类型是 Redis 最基本的数据类型,string 类型的值最大能存储 512MB。
常用命令:set、get、decr、incr、mget等。
注意:一个键最大能存储512MB。

Hash(哈希)
Redis hash 是一个键值(key→value)对集合;是一个 string 类型的 field 和 value 的映射表,hash 特别适合用于存储对象。
每个 hash 可以存储 2^32 -1 键值对(40多亿)。
常用命令:hget、hset、hgetall等。
应用场景:存储一些结构化的数据,比如用户的昵称、年龄、性别、积分等,存储一个用户信息对象数据。

List(列表)
Redis 列表是简单的字符串列表,按照插入顺序排序。你可以添加一个元素到列表的头部(左边)或者尾部(右边)。
list类型经常会被用于消息队列的服务,以完成多程序之间的消息交换。
常用命令:lpush、rpush、lpop、rpop、lrange等。
列表最多可存储 2^32 - 1 元素 (4294967295, 每个列表可存储40多亿)。

Set(集合)
Redis的Set是string类型的无序集合。和列表一样,在执行插入和删除和判断是否存在某元素时,效率是很高的。集合最大的优势在于可以进行交集并集差集操作。Set可包含的最大元素数量是4294967295。
集合是通过哈希表实现的,所以添加,删除,查找的复杂度都是O(1)。
应用场景:
1、利用交集求共同好友
2、利用唯一性,可以统计访问网站的所有独立IP。
3、好友推荐的时候根据tag求交集,大于某个threshold(临界值的)就可以推荐。
常用命令:sadd、spop、smembers、sunion, srem, srange, sinter等。
集合中最大的成员数为 232 - 1(4294967295, 每个集合可存储40多亿个成员)。

zset(sorted set:有序集合)
Redis zset 和 set 一样也是string类型元素的集合,且不允许重复的成员。
不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序。
zset的成员是唯一的,但分数(score)却可以重复。
sorted set是插入有序的,即自动排序。
常用命令:zadd、zrange、zrem、zcard等。
当你需要一个有序的并且不重复的集合列表时,那么可以选择sorted set数据结构。
应用举例:
(1)例如存储全班同学的成绩,其集合value可以是同学的学号,而score就可以是成绩。
(2)排行榜应用,根据得分列出topN的用户等。

讲讲redis里面的哈希表吧

Redis对于hash冲突,采用的是链地址法(其他的解决冲突的方法是再哈希和开放地址(线性探测和二次探测))
Redis为了控制哈希表占用内存的大小,采用双哈希表结构,并逐步扩大哈希表容量的策略。
Redis存储一个对象时,首先使用 zipmap又称为small hash存储。这样会节省很多哈希自身所需要的元数据的存储开销。当域字段field的数量超过限制范围,或者字段值value的长度大小超过系统限定的字节数,此时Redis将该zipmap转化为正常的hash进行存储。

参考 //www.greatytc.com/p/7f53f5e683cf 源码分析:

结构

hash表的结构定义如上。整个dict包含两个hash table,每个table初始化为4的大小,dictEntry 则是真正存放数据的结构。对于键值冲突的地方,采用链地址法

但是在 dict 扩容缩容时,需要分配新的 hashtable,然后进行渐进式搬迁,这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后,旧的 hashtable 被删除,新的 hashtable 取而代之。

rehash

扩容:当 hash 表中元素的个数(即第一个hash表的used)等于第一维数组的长度(即第一个hash表的size)时,就会开始扩容,扩容的新数组是原数组大小的 2 倍。不过如果 Redis 正在做 bgsave,为了减少内存页的过多分离 (Copy On Write),Redis 尽量不去扩容 (dict_can_resize 标志是否能够扩容),但是如果 hash 表已经非常满了,元素的个数已经达到了第一维数组长度的 5 倍 (dict_force_resize_ratio),说明 hash 表已经过于拥挤了,这个时候就会强制扩容。

缩容:当 hash 表因为元素的逐渐删除变得越来越稀疏时,,Redis 会对 hash 表进行缩容来减少 hash 表的第一维数组空间占用。缩容的条件是元素个数低于数组长度的 10%。缩容不会考虑 Redis 是否正在做 bgsave。

收缩或者扩展哈希表需要将ht[0]表中的所有键全部rehash到ht[1]中,但是rehash操作不是一次性、集中式完成的,而是分多次,渐进式,断续进行的,这样才不会对服务器性能造成影响

渐进式rehash(incremental rehashing)

渐进式rehash的关键:
1、字典结构dict中的一个成员rehashidx,当rehashidx为-1时表示不进行rehash,当rehashidx值为0时,表示开始进行rehash。
2、在rehash期间,每次对字典的添加(只加到 ht[1])、删除(ht[0] ht[1] 全部查找并删除)、查找(先查找 ht[0],如果未找到再查 ht[1])、或更新操作时,都会判断是否正在进行rehash操作,如果是,则顺带进行单步rehash(调用_dictRehashStep 函数,该函数调用 dictRehash(d, 1)),并将rehashidx+1。新添加到字典的key-val一律会被保存到ht[1]里面,而ht[0]不再进行任何添加操作,这一措施保证了ht[0]包含的key-val对数量只增不减,并随着rehash操作的执行而最终变成空表。
3、dictRehash(dict* d, int n) 函数每次 rehash 前进 n 步(顺序访问 n 个 ht[0].table 的非空 dictEntry),如果 dictEntry 一直为空,则访问到 n*10 个空 dictEntry 之后,本次 rehash 结束。
4、启动 redis 会启动一个 cron 定时任务(定时任务默认每秒执行 server.h CONFIG_DEFAULT_HZ=10 次),每次定时任务运行 1ms 的 rehash,调用 dictRehash(d, 100),执行100步rehash。
4、当rehash时进行完成时,将rehashidx置为-1,表示完成rehash。同时 ht[0]=ht[1],ht[1]=Null,更换表指针。

一个URL从浏览器输入到响应页面,整个过程是怎么样的,能讲得多详细就讲多详细。

你说HTTP可以进行多路复用,具体是怎么复用?如果服务器挂掉或者客户端挂掉,会怎么样?

http1.1 通过设定 Connection:keep-alive 字段来保持TCP的长连接,从而能够在一次建立连接的情况下处理多个请求。
下一个请求需要在上一个请求的响应之后发送,因此会存在队头阻塞。
HTTP1.1进一步地支持在持久连接上使用管道化(pipelining)特性。管道化允许客户端在已发送的请求收到服务端的响应之前发送下一个请求,借此来减少等待时间提高吞吐率。但是需要响应的顺序是按照请求顺序进行,因此也会存在队头阻塞。

http2 开启了完全的多路复用:一个连接被多个流复用。一个流表示一次请求-响应过程。
这个过程有两个概念:流和帧。帧代表着最小的数据单位,每个帧会标识出该帧属于哪个流,流也就是多个帧组成的数据流。
多路复用,就是在一个 TCP 连接中可以存在多条流。换句话说,也就是可以发送多个请求,对端可以通过帧中的标识知道属于哪个请求。通过这个技术,可以避免 HTTP 旧版本中的队头阻塞问题,极大的提高传输性能。

挂掉,则一段时间之后,保活时间到期,则关闭。或者TCP等待时间结束,关闭TCP连接。或者采用应用层周期发送心跳包来检测是否对方还在。

好处:
减少服务端连接压力,减少占用内存,提升连接吞吐量;
连接数的减少改善了网络拥塞状况,慢启动时间减少,拥塞和丢包恢复速度更快;
避免连接频繁创建和关闭(三次连接、四次挥手);

HTTP的各种头你了解吗?每种头具体是什么作用?说一下

四种方法
GET:获取信息
POST:传输实体
PUT:上传文件
DELETE:删除文件

头部信息:
Host (主机和端口号)
Connection (链接类型)
Upgrade-Insecure-Requests (升级为 HTTPS 请求)
User-Agent (浏览器名称)
Accept (传输文件类型)
Referer (页面跳转处)
Accept-Encoding(文件编解码格式)
Cookie (Cookie)
x-requested-with :XMLHttpRequest (是 Ajax 异步请求)

你说arp会进行广播,会造成网络风暴,那应该怎么解决?

arp发出去之后,交换机会查找自己的 mac 缓存表,如果存在,则直接返回,不存在则按照 IP 选择端口进行发送,如果不存在 IP 的端口,则广播。之后每个路由器都有隔离广播的作用,其也缓存了 IP 对应的端口,并向对应的端口进行发送。

你知道CDN吗?说一下

BIO NIO AIO说一下?epoll了解吗?用过吗?具体调用OS什么方法?webSocket呢?

java 相关

创建进程调用的是OS哪些方法?具体说说

我们聊聊JAVA吧,你了解JVM吗?给我讲讲

JVM具体会在什么时候进行垃圾回收?JMM具体说说?

垃圾回收算法具体说说?各种垃圾回收器了解吗?什么时候执行STOP THE WORLD?


三面:

感觉应该是总监,很高冷。

说说项目?(没啥兴趣)

我们聊聊JAVA吧,现在我要求设计一个容器,容器满的时候生产者阻塞,容器空的时候消费者阻塞(我跟他讲了一下BlockingQueue和Condition,然后用Condition来写)

二叉树的最大路径。

好吧,今天就到这里了(哈???)

三面面完一度觉得自己凉透了,过两天收到offer call,然后就收到offer了。白菜价,很高兴了。

总的来说,个人感觉头条面试算法题不难(应该是给我放水了,谢谢面试官),不过绝对不能做不出来。基础一定要牢固,一些细节问题一定要搞清楚,一般还会问一些设计问题,这种问题就要靠灵机一动了(其实主要还是看对各种原理的理解,例如说那道队列的问题)。噢,对了,还有一件事,一面是要求自己写测试用例运行的,所以coding一定要快准狠。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 217,509评论 6 504
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,806评论 3 394
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 163,875评论 0 354
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,441评论 1 293
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,488评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,365评论 1 302
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,190评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,062评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,500评论 1 314
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,706评论 3 335
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,834评论 1 347
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,559评论 5 345
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,167评论 3 328
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,779评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,912评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,958评论 2 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,779评论 2 354