回首自己面试中遇到的关于c++的面试题


经过跨度比较长的一段时间的面试,经历了腾讯、京东、迅雷等的一些面试,当然最终都还是跪了,不过还是记录下自己面试中或者笔试中遇到的一些问题,及自己觉得应该加强的地方。

网络编程方面

  • time-wait状态的产生原因。

这个在网络编程上,几乎是必考的,主要考察对TCP/IP网络编程中,套接字状态变化的认识,以及TCP全双工的认识。

  • tcp的端口数最多只有65535个,为何能支持几十万的连接?
  • accept是发生于tcp三次握手的哪个阶段

我们知道,TCP的三次握手是这样的:

第一次:主动发送方先发送SYN包请求建立连接。此时主动方TCP连接处于SYN_SENT状态。

第二次:被动方发送SYN+ACK包,发送ACK表示对收到的主动方的SYN包的回应,并附带发送被动方自己的SYN包。此时,被动方TCP连接处于SYN_RCVD状态。

第三次:主动方收到被动方发送的SYN+ACK包,然后发送ACK包。此时TCP连接处于ESTABLISHED状态。

被动方等收到主动方发送的最后一个ACK后,TCP连接处于ESTABLISHED状态。而accept就是在被动方在开启监听之后,调用的函数,作用是等待客户端的连接。在tcp建立连接过程中,内核为监听套接字维护的两个队列需要了解下:

1.未完成连接队列。这些队列中的套集字处于SYN_RCVD状态。

2.已完成连接队列。这些队列中的套接字处于ESTABLISHED状态。

    而accept函数,就是从已完成连接队列中取出队头项返回给进程,而如果进程为空,则阻塞(阻塞模式下)。所以,accept发生在三次握手之后。

  • connect(阻塞),在TCP的三次握手的哪一步返回?

connect仅在连接成功或出错时才返回。其中出错返回有以下几种情况:

1.若TCP客户没有收到SYN分节的响应,则返回ETIMEDOUT错误。记住,没有响应时,我们会进行SYN的超时重发,利用超时时长的指数退避算法,最终仍然是超时时,则返回超时错误。

2.若对客户的SYN的响应是RST(此时可能是服务器端口未处于监听状态),则表明服务器主机在我们指定的端口上没有进程在等待与之连接。这种一种硬错误,客户端一接收到RST就马上返回ECONNREFUSED错误。

3.若客户端发出的SYN在中间的某个路由器上引发一个destination unreachable的ICMP错误,则认为是一种软错误。客户端主机内核保存该信息,并按第一种情况中所述的时间间隔继续发送SYN。若在某个规定的时间后仍未收到响应,则把保存的ICMP错误作为EHOSTUNREACH或ENETUNREACH错误返回给进程。

成功返回,是当发送完最后一个ACK时,自身进入ESTABLISHED状态,此时,connect函数成功返回

  • 服务器端如何避免产生大量的TIME_WAIT状态
  • 当对端关闭时,此时调用write向对方写数据,write的返回是什么
  • 关于UDP的套接字接收缓冲区,说法正确的是?A.UDP没有缓冲区。B.UDP有缓冲区

这个很容易和UDP是否有流量控制相混淆。答案是B

  • 通过epoll,如何知道已建立好了连接?

其实,面试官想问的是,非阻塞模式下,如何知道已建立好了连接,通常,我们可以通过向假设建立好的连接发出请求,包括read/getpeername等方法,如果返回失败,则连接没有建立。或者也可以再次调用connect,如果返回EISCONN,则说明连接已经建立。

  • 如何设置套接字非阻塞?有哪些函数可以使用?

1.ioctl或fctnl

  1. fcntl(sockfd, F_SETFL, fcntl(sockfd, F_GETFL, 0) | O_NONBLOCK);
  2. ioctl(sockfd, FIONBIO, 1); //1:非阻塞 0:阻塞

2.linux平台上,在type的参数中设置SOCK_NONBLOCK标志即可,例如: int s = socket(AF_INET, SOCK_STREAM | SOCK_NONBLOCK, IPPROTO_TCP);

  • 简单介绍下I/O多路复用
  • select和epoll的区别
  • epoll的几种触发方式?各自的优缺点

epoll有水平触发(LT)和边缘触发(ET),水平触发是当满足触发条件时,就一直能得到触发。而边缘触发时当触发条件从不满足到满足,才会触发。

  • UDP和TCP的优缺点
  • UDP的应用场景有哪些

数据结构方面

  • 单链表删除的时间复杂度是多少?

可能很多人第一反应肯定是O(1),因为我们都知道,单链表的优势就是支持快速的插入和删除。其实,单链表删除的时间复杂度有O(1)和O(n)。当我们知道要删除的节点的指针时,我们可以通过O(1)的复杂度去实现:

1.Node(i)->data=Node(i)-next->data;

2.Node(i)-next=Node(i+1)->next;

但是,当要删除的尾指针时,它没有后续指针,此时,仍然需要遍历整个链表,找到尾指针的前置指针,所以时间复杂度此时是O(n)
  • STL的算法中,sort方法使用的是什么排序?

快速排序 + 插入排序。

  • 为什么map底层使用RB树而不是AVL树

首先要知道RB树和AVL树分别是什么东西。RB树,红黑树,平衡二叉树的一种。AVL树-最早的平衡二叉树。AVL树是高度平衡的二叉树,在AVL树中任意节点的两个子树的高度最大差别为一,为维持树的平衡,需要极大的代价。而RB树,平衡二叉树的一种,相比AVL树,它的每个节点都带有红或黑的颜色属性,具有必须满足的五个特性。相比AVL树,红黑树要保持自平衡的代价较小。

  • 快速排序如何控制递归次数?即不想递归太多次,如何控制在一个小范围内的递归?
  • 红黑树各操作的时间复杂度
  • 说下你知道的几种排序算法,哪些是稳定的,哪些是不稳定的?

c++基础

  • string str; sprintf((char*)str.c_str(),"%s\n", "hello"); 此时,输出的str的输出是什么?

经实践,应是空字符串,查看string源码,发现内部有个size成员,控制着输出的结果,尽管str内部的m_start被强制转换成了char *,内容虽然可能被写进去了,但是输出的时候,依然是由size控制的,所以输出的内容还是空

  • 进程与线程的区别
  • 进程间通信有哪几种方式?哪些需要加锁
  • 多态的实现原理
  • 多线程共享哪些资源
  • 说出常用的gdb命令
  • 如何调试多线程和多进程
  • 如何查看进程占用的文件
  • 如何查看进程的堆栈

数据库

  • 事务的四个隔离级别
  • 事务的四个特性
  • InnoDB默认的隔离级别
  • 什么是幻读问题,如何解决
  • 什么情况下应该使用InnoDB引擎,什么情况下不适用?

当表的某个单个字段过大时,会造成聚簇节点的严重倾斜,也会提高建立索引需要的时间,此时,不适合使用InnoDB引擎。个人理解,不知道是否正确,欢迎拍砖。

  • mysql索引的最左前缀原则是什么?
  • select name from table where name like '%xxx',假设对name建立索引,那么,该查询是否会使用到索引,为什么?
  • mysql主从同步有哪些模式?默认使用哪种
  • MVCC是什么,有哪些应用

分布式相关

  • 什么是一致性哈希
  • 什么是分布式全局锁,如何设计?
  • 什么是CAP理论
  • 在使用一致性哈希的情况下,怎样热迁移数据?
  • 在应用中,有大量的大用户数据,还有一些小用户数据,都使用消息队列的方式去入库,结果查询时几乎都是大用户的数据,造成这种现象的原因?请提供解决思路

这个是面试题目,我面试时,想的是因为大用户数据数据量很大,占据了消息队列,导致入库的都是大用户数据。所以我给出的解决方案是给用户数据排出优先级,优先级高的数据先入消息队列。面试官反问,这样是否会造成查询时查找不到大用户的数据?其它细节已经记不清了。欢迎大家提供自己的思路。

逻辑思考

  • 5海盗分100金问题
  • 两个人从一堆书架中抽书,假设书架中有100本,每人每次必须取1本-5本,谁拿最后谁输。现在你有权决定谁先开始拿书,那么,怎么能保证你肯定赢?
  • 2块钱能买一瓶可乐,两个空瓶可以兑换一瓶可乐,现在你有100元钱,你最多能喝多少瓶可乐?

时间过去的有点久远了,有些问题一时想不起来了,感觉挺可惜的,感觉腾讯这类大厂,很看重个人解决问题的思维能力和算法能力。没事还是要多刷刷算法。



评论

发表评论