深信服C++面经

1面

1面面试官问得比较简单
1.const
2.static
3.写一个memcpy
装一下 讲了字典树和跳表
讲一些具体实现

2面

1.手写memcpy.
2.进程间通信
3.在TCP报文的画出三次握手的全过程。
4.一道智力题:100层楼,有两个玻璃球,有唯一一层,从该楼层及以下楼层扔下玻璃球不会碎,从该楼层以上扔玻璃球会碎,请用用两个玻璃球找出该层(最小的时间复杂度)。

后面就问tcp udp
线程进程
最后问了一个算法
象棋中马从A到B最短走几步
答bfs
问可否优化
想不出就说还是bfs 不过先建表算出来放表里存着直接查

 

一面:
0)自我介绍?
1)如何用数组实现链表的功能?(数组中存放一个结构体,一个表示数据,另外一个表示其下一个节点在数组中的index,以便于快速插入删除)

2)linux下有哪些信号?
3)https中的pipeline?多个相同请求的时候一次返回
4)函数指针的作用?
5)如何实现一个非定长的结构体? -长度为0的数组(a[0])

6)strcpy实现方法及其缺点,strncpy?
7)野指针?

8)linux io和标准io区别?

9)http网址访问过程,get post区别?
一面大概只记得这么多内容了,大约30-40分钟的样子,有两种面试官,一种调出笔试题让讲算法和错题的,另外一种直接怼基础的,总体上不太难。
二面:
0)简单自我介绍?

1)讲熟悉的项目,讲讲项目难点?
谈谈io复用,select?
谈谈项目共享内存实现方法?
2)linux 下编译调试方法,如何调试内存泄露问题?
3) 给几百万个网址,如何高效找出特定网址是否在其中?(布隆过滤器)
布隆过滤器优缺点,如何解决其缺点?
4)给一容量较大非法单词词典,如何判断某输入中是否有非法单词?

建立字典树–实现一次遍历就可做出判断
1、画堆排序过程,复杂度分析。
2、画平衡二叉树建立过程。
3、画红黑树构造过程。(这个不会了。。。)
4、虚析构作用。
5、什么叫重载,继承,隐藏。
6、什么函数不能声明为virtual。
7、extern C的作用。
8、讲一下快排。
9、算法题,O(n)内旋转字符串。
10、算法题,文件中有大量数字,排序并保存到结果文件中。
11、memcpy的实现。
12、TCP快重传。(记成快恢复了。。。)
1.sizeof 各种基本类型 结构体 类2.继承和多态

3.栈在实际编程的时候有哪些应用场景

4.广搜用什么数据结构

5.浮点数判断是否相等

6.手写代码 字符串反转 有时间和空间复杂度限制

7.手写代码 字符串循环移位 面试官让优化复杂度 没想出来(要用到上一题的字符串反转)

8.统计一篇英文文章出现频率最高的十个单词

9.new和malloc

10.智力题 4刀把一个圆柱形蛋糕切16块

11.实现strcpy,要考虑内存重叠和特殊情况处理

 

Q:象棋中马从一个位置跳到另一个位置的最少步数
A:手写BFS

Q:一次可以上一层台阶,也可以上两层台阶,到第N层有多少种走法
A:F[N]=F[N-1]+F[N-2]

Q:一分钟内经过公交车的概率为p,求三分钟内有公交车经过的概率
A:P=1-(1-p)^3

Q:strcpy和memcpy的区别
A:复制的内容不同,strcpy无需指定长度,遇到’\0’为止

Q:那strncpy呢?
A:我没用过

Q:你怎么判断两个struct相等?
A:我会选择重载==运算符,逐一比较成员变量是否相等

Q:那能不能用内存比较memcmp来判断呢?
A:不能,涉及字节对齐,可能有内存间隙,这里的值是随机的

Q:进程间的通信有哪些方式?
A:管道、有名管道、(信号、信号量、)共享内存、消息队列、socket

Q:epoll和select/poll的区别
A:epoll是实现I/O多路复用的一种方法,有水平触发(level trigger,LT,默认)和边缘触发(edge trigger,ET)两种工作模式,区别在于两种模式的返回就绪状态的时间不同。水平触发和select/poll的方式一样

  • 水平触发
    • 读:缓冲内容不为空返回读就绪
    • 写:缓冲区还不满返回写就绪
  • 边缘触发
    • 读:
      • 缓冲区由不可读变为可读
      • 新数据到达,缓冲区中待读数据变多时
    • 写:
      • 当缓冲区由不可写变为可写
      • 当有旧数据被发送走,即缓冲区中的内容变少的时候

epoll之所以高效,是因为epoll将用户关心的文件描述符放到内核里的一个事件表中,而不是像select/poll每次调用都需要重复传入文件描述符集或事件集。比如当一个事件发生(比如说读事件),epoll无须遍历整个被侦听的描述符集,只要遍历那些被内核IO事件异步唤醒而加入就绪队列的描述符集合就行了。

Q:在TCP连接中,服务端的socket要做哪些?
A:socket->bind->listen->accept->send/recv

Q:堆和栈的区别?
A:堆是一颗二叉树、栈是一个单向进出的线性结构

Q:堆排序和快排的区别?
A:快排的思想是分治,每次选择当前范围的第一个数作为标杆,然后再将这个范围的所有比它小的数放到他左边,大的放到他右边,由这个标杆的现在位置划分出两个范围,分别对这两个范围的数再重复这样的*作,直到范围大小为1
堆排序则是在建堆的时候保证堆顶最小,然后每次取堆顶

下面应该是面试官自己出的一些题目

Q:XML是什么结构?
A:树

Q:用过正则表达式吗?写一个32位IP地址的正则
A:用过,忘记了不好意思

Q:进程和线程的区别?
A:这个没背,只回答上了几句话

 

 

1、第一个问题,怎样统计一篇英文文章中出现频率最高的10个单词,用什么数据结构和算法实现,因为是第一个问题,很紧张,答得有点语无伦次,面试小哥倒是忍了,跟我说不用说这么细,说个主要思路就可以了。

2、为找出一个字符串中第一次出现的指定字符,怎么优化算法。一脸懵逼,甚至想出了两端遍历的方式,然后小哥提醒我是第一次出现的。。。然后我就随口胡诌了一个。

3、结构体的比较问题,之前也有老哥说过。

4、根据主要用的编译环境,我是windows,他问了debug和release的区别,我就说一个会忽视ass断言一个不会(太激动还把断言说成了警告。。。)。然后又追问另一个问题,我都忘记是啥了。。。

5、main函数有没有返回值,分别针对什么情况。这个比较简单没啥好说的,然后他直接追问,那么如果出现异常,怎么捕获,然后我就懵逼了。。。

6、下一个问题更懵逼,问C++写的动态链接库能不能直接给C用,为什么。。。我就说,您既然这么问了,那肯定不能,但我也不知道为什么,因为平时使用的时候C++可以支持90%的C操作,然后就没有然后了。

7、问我有没有学过计算机网络,我说学院没开,做项目的时候用过,所以自学了一部分,然后面试官很贴心的问了个基础的问题,TCP的三次握手。这个应该都有准备过,然后又问了一下几次握手中,两端的状态转换,以及为什么两次握手不行。

8、最后问了一个关于C中宏定义的问题,前面老哥们有说过。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注