字节跳动｜data部门go后端开发｜（22届春招，三轮技术面）｜2021｜
匿名用户
14186
2021.03.27
2021.04.06
发布于 未知归属地
字节跳动Go求职面试后端

字节跳动飞书C++客户端开发（22届春招，两轮技术面）
字节跳动data部门go后端开发（22届春招，三轮技术面）
腾讯天美工作室C++后台开发（22届春招，三轮技术面）

字节跳动data部门go后端开发（22届春招，三轮技术面）

一面

  1. 自我介绍。
  2. 对一块内存1，值为a。线程1：将该内存的值修改为b：a->b。线程2：a->c，c->a。如何避免当内存值a被修改为c之后，线程1修改为b。
    可以使用CAS（比较与交换，Compare and swap）算法来解决，它是一种有名的无锁算法，使用方法很简单，每次去检测一个值是不是目标值是则修改为某一个值，否则不做处理，这整个操作是原子的。这个场景中我们只需要再线程1中使用这个算法即可保证内存被修改为c的时候，线程1修改内存的值。
  3. TCP和UDP的区别？服务器宕机了怎么办？
    我们这里来讲一下，TCP通信的异常情况及对应的解决方案。
    3.1 试图与一个不存在的端口建立连接：服务器端口还没有监听，我们的客户端就调用connect，视图与其建立连接。这时会发生什么呢？这符合触发RST分节的条件，目的为某端口的SYN分节到达，而端口没有监听，那么内核会立即响应一个RST，表示出错。客户端TCP收到这个RST之后则放弃这次连接的建立，并且返回给应用程序一个错误。正如上面所说，建立连接的过程对应用程序来说是不可见的，这是操作系统帮我们来完成的，所以即使进程没有启动，也可以响应客户端。
    3.2 试图与一个不存在的主机上面的某个端口建立连接：这也是一种比较常见的情况，当某台服务器主机宕机了，而客户端并不知道，仍然尝试去与其建立连接。这个时候由于宕机，操作系统帮不上忙，服务器处于一种完全没有响应的状态。那么此时客户端的TCP会怎么办呢？客户端不会收到任何响应，那么等待6s之后再发一个SYN，若无响应则等待24s之后再发一个，若总共等待了75s后仍未收到响应就会返回ETIMEDOUT错误。这是TCP建立连接自己的一个保护机制，但是我们要等待75s才能知道这个连接无法建立，对于我们所有服务来说都太长了。更好的做法是在代码中给connect设置一个超时时间。
    3.3 Server进程被阻塞：由于某些情况，服务器端进程无法响应任何请求，比如所在主机的硬盘满了，导致进程处于完全阻塞，通常我们测试时会用gdb模拟这种情况。上面提到过，建立连接的过程对应用程序是不可见的，那么，这时连接可以正常建立。当然，客户端进程也可以通过这个连接给服务器端发送请求，服务器端TCP会应答ACK表示已经收到这个分节（这里的收到指的是数据已经在内核的缓冲区里准备好，由于进程被阻塞，无法将数据从内核的缓冲区复制到应用程序的缓冲区），但永远不会返回结果。
    3.4 我们杀死了server：这是线上最常见的操作，当一个模块上线时，OP同学总是会先把旧的进程杀死，然后再启动新的进程。那么在这个过程中TCP连接发生了什么呢。在进程正常退出时会自动调用close函数来关闭它所打开的文件描述符，这相当于服务器端来主动关闭连接——会发送一个FIN分节给客户端TCP；客户端要做的就是配合对端关闭连接，TCP会自动响应一个ACK，然后再由客户端应用程序调用close函数，也就是我们上面所描述的关闭连接的4次挥手过程。接下来，客户端还需要定时去重连，以便当服务器端进程重新启动好时客户端能够继续与之通信。
    3.5 Server进程所在的主机宕机：客户端向服务器端发送分节，由于服务器端宕机，不会有任何响应，客户端持续重传，然而服务器始终不能应答，重传数次之后，大约4~10分钟才停止，之后返回一个ETIMEDOUT错误。
  4. 如果对index(A,B,C)建立索引，下面这些查询会怎么样？是否会使用索引？
where a=? and b=? and c=?
where a=? and b=?
where a=?
select *
where b=5
limit 3000000,5

索引是否使用的情况.png
5. 一个物品5块钱，n个人有5块，n个人有10块，始终能够找出零钱的排列有多少种？
这是一个卡特兰数，可以参考这个https://zhuanlan.zhihu.com/p/235008161

  1. 基本计算器
  2. 验证二叉搜索树，题目要求递归和非递归两种方式。
  3. 反问环节

二面

  1. Proactor模式和Reactor模式的区别？
    事件处理模式：Reactor模式/Proactor模式。
    服务器程序通常要处理3类事件，I/O事件、信号和定时事件。在处理事件上有两种高效的事件处理模式：Reactor和Proactor。这两种其实也都是I/O复用模型
    Reactor：它要求主线程只负责监听文件描述上是否有事件发生，有的话就立即将该事件通知工作线程。除此之外，主线程不做任何其他实质性的工作，读写数据、接收新的连接，以及处理客户请求均在工作线程中完成。使用同步I/O模型（以epoll_wait()为例）实现的Reacotr模式的工作流程如下：
    1）主线程往epoll内核事件表中注册socket上的读就绪事件。
    2）主线程调用epoll_wait()等待socket上有数据可读。
    3）当socket上有数据可读时，epoll_wait()通知主线程。主线程将socket可读事件放入请求队列。
    4）睡眠在请求队列上的某个工作线程被唤醒，它从socket读取数据，并处理客户请求，然后往epoll内核事件表中注册该socket上的写事件。
    5）主线程调用epoll_wait()等待socket可写。
    6）当socket可写时，epoll_wait()通知主线程。主线程将socket可写事件放入请求队列。
    7）睡眠在请求队列上的某个工作线程被唤醒，它往socket上写入服务器处理客户请求的结果。
    Proactor模式：与Reactor模式不通，Proactor模式将所有I/O操作都交给主线程和内核来处理，工作线程仅仅负责业务逻辑。使用异步I/O模型（aio_read和aio_write为例）实现得Proactor模式工作流程。
    1）主线程调用aio_read函数向内核注册socket上的读完成事件，并告诉内核用户读缓冲区的位置，以及读操作完成时如何通知应用程序。（信号）
    2）主线程继续处理其他逻辑。
    3）应用程序预先定义好的信号处理函数选择一个工作线程来处理客户请求。工作线程处理完客户请求之后，调用aio_write函数向内核注册socket上的写完成事件，并告诉内核用户缓冲区的位置，以及写操作完成时如何通知应用程序（信号）。
    4）主线程继续处理其他逻辑。
    5）当用户缓冲区的数据被写入socket之后，内核将向应用程序发送一个信号，以通知应用程序数据已经发送完毕。
    6）当用户缓冲区的数据写入socket之后，内核向应用程序发送一个信号，以通知应用程序数据已经传送完毕。
    7）应用程序预先定义好的信号处理函数选择一个工作线程来做善后处理，比如决定是否关闭socket。
    同步模拟Proactor模型：《Linux高性能服务器编程》一书中提到了一种用同步I/O来模拟Proactor模式的方法。其原理是：主线程执行数据读写操作，读写完成之后，主线程向工作线程通知这一“完成事件”。那么工作线程直接获得了读写结果，接下来只要做的只是对读写结果的处理。
    1）主线程调用epoll_wait()内核事件表中注册socket上的读就绪事件。
    2）主线程调用epoll_wait()等大socket上有数据可读。
    3）当socket上有数据可读时，epoll_wait()通知主线程。主线程从socket循环读取数据，直到没有更多数据可读，然后将所有数据封装成一个请求对象并插入请求队列。
    4）睡眠在请求队列中的某个工作流程被唤醒，它获得请求对象并处理客户请求，然后往epoll内核事件表中注册socket上的写就绪事件。
    5）主线程调用epoll_wait()等待socket可写。
    6）当socket可写时，epoll_wait()通知主线程。主线程往socket上写入服务器处理客户请求的结果。
    这里同步模拟和异步模拟Proactor的区别在于，同步模拟是主线程自己进行I/O操作，需要等待读完数据，而异步I/O是通过aio_read()异步读取，主线程不需要等待I/O完成。
    总结：Reactor和Proactor的本质区别在于谁负责I/O操作，其实它们都可以分别利用同步I/O或者异步I/O来实现。
  2. select、poll、select的区别？
    select：
int select (int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout); 
void FD_ZERO(fd_set *fdset);	//清空一个fdset
void FD_SET(int fd, fd_set *fdset);	//添加一个fd进入fdset
void FD_CTR(int fd,fd_set *fdset);	//从fdset删除一个fd
int FD_ISSET(int fd, fd_set *fdset);	//判断fdset里面是否有某个fd

select函数监听的文件描述符分3类，分别是writefds、readfds和exceptfds。调用后select函数会阻塞，知道有描述符就绪，或者超时，函数返回。当select函数返回后，可以通过遍历fdset来找到就绪的描述符。select目前在几乎所有平台上支持，其良好的跨平台支持也是它的一个优点。缺点就是单个进程能够监听的描述符的数量存在最大限制，在Linux上一般为1024，可以通过修改宏定义来提升这一限制，但是会降低效率。
Poll：

int poll (struct pollfd *fds, unsigned int nfds, int timeout);

不同于select使用3个位图来表示3个fdset的方式，poll使用一个pollfd的指针实现。

struct pollfd{
	int fd;
	short events;
   short revents;
}

pollfd结构包含了要监视的event和发生的event，不再使用select“参数-值”传递方式。同时，pollfd并没有最大数量限制（但是数量大了性能变差）。和select一样，poll返回后需要轮询pollfd来获取就绪的描述符。从上面的例子看，select和poll都需要在返回后同遍历文件描述符来获取已经就绪的socket。事实上，同时连接的大量客户端在一时刻可能只有很少的处于就绪状态，因此随着监听的描述符数量增长，其效率线性下降。
Epoll：
epoll是select和poll的增强版本。epoll更加灵活，没有数量限制。epoll使用一个文件描述符管理多个描述符，将用户关系的文件描述符的事件存放在内核的一个事件表中，这样在用户空间和内核空间的copy只需一次。epoll操作过程需要3个接口，分别如下所示：

int epoll_create(int size);
int epoll_ctl(int epfd, int op, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);

epoll_create()创建一个epoll句柄，size用来告诉内核这个监听的数目一共多大，这个参数无法限制epoll监听的最大数目，而是给出一个建议。 epoll句柄会占用一个fd值。
epoll_ctl()对指定的描述符fd执行op操作，可以添加（EPOLL_CTL_ADD）/删除（EPOLL_CTL_DEL）/修改（EPOLL_CTL_MOD）对fd的监听事件。event是告诉我们内核需要监听数目事件。struct epoll_event结构如下所示：

struct epoll_event{
	_uint32_t events;	/* Epoll events */
   epoll_data_t data;  /* User data variable */
};
//events可以表示为以下几个宏的集合
EPOLLIN ：表示对应的文件描述符可以读（包括对端SOCKET正常关闭）；
EPOLLOUT：表示对应的文件描述符可以写；
EPOLLPRI：表示对应的文件描述符有紧急的数据可读（这里应该表示有带外数据到来）；
EPOLLERR：表示对应的文件描述符发生错误；
EPOLLHUP：表示对应的文件描述符被挂断；
EPOLLET： 将EPOLL设为边缘触发(Edge Triggered)模式，这是相对于水平触发(Level Triggered)来说的。
EPOLLONESHOT：只监听一次事件，当监听完这次事件之后，如果还需要继续监听这个socket的话，需要再次把这个socket加入到EPOLL队列里

epoll_wait()等待epfd上的I/O事件，最多返回maxevents个事件。参数events用来从内核得到事件的集合，maxevents告知内核这个events有多大。
Epoll在内核维护了两个数据结构，一个红黑树用来存储监听IO事件的fd，另一个用来存储IO事件的双链表。红黑树能够提供高效的fd查找、修改、删除操作（epoll_ctl()）。一旦某个fd发生了IO事件，就会触发fd的回调函数，将事件添加到双链表中。而epoll_wait()只需要检查链表是否为空即可，不为空等待返回，否则等待IO事件发生触发回调函数。

  1. 读写锁实现，写伪代码。
int count;  //读者计数
lock w_lock;    //写者锁
lock r_lock;    //读者的锁
void reader_lock()
{
    lock.lock();
    count++;
    if(count==1){
        w_lock.lock();
    }
    lock().unlock();
}
void reader_unlock()
{
    r_lock().lock();
    count--;
    if(count==0){
        w_lock.unlock();    
    }
    r_lock().unlock();
}
void writer_lock()
{
    w_lock.lock();
}
void writer_unlock()
{
    w_lock.unlock();
}
  1. 不同的子序列
    要求动态规划和递归两种写法。
  2. ping的实现原理。
    ping命令是用来查看网络上另一个主机系统的网络连接是否正常的一个工具。ping命令的工作原理是：向网络上的另一个主机系统发送ICMP报文，如果指定系统得到了报文，它将把报文一模一样地传回给发送者。ICMP（网际控制报文协议）：这是IP层的一个协议，但是由于差错报告在发送给报文源发方时可能也要经过若干子网，因此牵涉到路由选择等问题，所以ICMP报文需通过IP协议来发送。ICMP数据报的数据发送前需要两级封装：首先添加ICMP报头形成ICMP报文，再添加IP报头形成IP数据报。由于IP层协议是一种点对点的协议，而非端对端的协议，它提供无连接的数据报服务。

三面

  1. 自我介绍。
  2. 挑一个项目介绍。
  3. tail了解吗？tail -f这个你会如何设计？tail -10如何设计？
    tail -10可以读取文件的最后10行，可以用快慢指针的思想来设计。tail -f常用来查看正在改变的日志文件。tail -f filename会把 filename 文件里的最尾部的内容显示在屏幕上，并且不断刷新，只要 filename 更新就可以看到最新的文件内容。可以用循环去读取文件，也可以使用select、poll来监听日志文件，并输出。
  4. 寻找最近回文数
    这道题写了很久。
  5. 海盗分金
  6. 反问环节
评论 (12)