面经

这是面试题笔记系列的第一篇文章,记录一些常见的面试题。其中主要是一些一线互联网大厂的面试题,我主要收集于 LeetCode、CSDN、知乎、GitHub 等技术社区。

答案皆根据我的理解进行编写,可能会存在一定的错误。我将这些面试题主要分为三类:概念题、算法题、理解应用题。

面试题来源

腾讯 - 提前批 - 客户端开发 深信服 - 优招 - C++ 研发(物联网方向) 老虎 - 正式批 - Windows 开发一面 360 - 提前批 - 软件开发

理论概念题

  1. 函数传值的方式? 按值传递、按引用传递、按指针传递。

  2. 引用和拷贝的区别? 引用的::效率::要高于拷贝,这也是为什么如果函数参数是::类对象,通常使用引用传递。::若不想被改变,则加上 const为常引用。

  3. 引用的优缺点和拷贝的优缺点? 拷贝需要大量原始数据的移动,带来时间和空间上的消耗,这是它的缺点。

C++11 所支持的::移动语义::(move semantics),其思想是避免原始数据的移动,而只是修改记录。move 的本质是一个转换函数,将给定类型转换为右值引用。

引用的缺点可以从引用与指针的区别的角度来看。如:构造时必须初始化、不能为 NULL、初始化后无法再改变、引用的创建和销毁不会调用类的拷贝构造函数和析构函数 等等。

  1. C++ 内存分区?未初始化的全局变量放在哪里? ::C++ 内存分区::: 堆、栈、自由存储区、全局/静态存储区、常量存储区。

关于自由存储区(Free Store)和堆(Heap) malloc/new

::文本段:::程序的二进制代码,只读。 初始化数据段:global/static/const/extern初始化的变量。 未初始化数据段:未初始化的变量。 初始化数据段和未初始化数据段统称为::数据段::。 ::堆:::当使用 malloc 在堆上分配的内存。 ::栈:::局部变量、函数返回所需的一些东西。

  1. 野指针是什么?有什么可以检测吗?
  • 声明指针但是没有初始化⚠️。
  • 释放空间后没有置 NULL,产生悬挂指针,存在安全隐患⚠️。
  • 当返回一个基于栈分配的局部变量的地址时,num 是一个局部变量,函数结束后自动释放其空间,编译器会给出警告⚠️。

如何检测野指针?方法是提高野指针的崩溃率,将访问时的随机崩溃变成访问必然崩溃,尽早的定位到野指针。macOS 下 Xcode 提供了内存涂鸦(Malloc Scrobble)。

Linux 下有一个工具可以解决常见的 C++ 内存问题——「Valgrind 」,其中的 memcheck 工具提供:检查程序中的内存问题,如泄漏、越界、非法指针等。

  1. 进程间通信方式,知道互斥锁和自旋锁吗?
  • 管道(Pipe) | > :简单,阻塞,半双工通信。
  • 消息队列 发送数据块,数据块有长度限制,数据拷贝消耗大。
  • 共享内存 解决消息队列的数据拷贝产生的性能消耗。两个拥有独立的虚拟内存空间,但是映射到相同的物理内存中。
  • 信号量 Semaphore。记录型信号量(阻塞队列);互斥信号量。信号量实现进程的互斥和同步。经典的生产者消费者问题。
  • Socket 程序进行 Socket 通信。

自旋锁🔒 指当一个线程在获取锁时,此时的锁已经被其他线程获取,那么该线程循环等待,然后不断判断是否能够被成功获取,知道获取到锁才会退出循环。 核心:线程反复检查锁变量是否可用,忙等待。

while (test_and_set(lock) == 1);

缺点:消耗 CPU、“饥饿”现象 优点:线程不会进入阻塞状态、减少了不必要的上下文切换。

互斥锁🔒:防止两条线程::同时::对同一临界资源进行读写的机制。类似互斥信号量机制提供的阻塞队列,实现让权等待。

  1. 路由器(R)和二层交换机(S)的区别? 交换机,严格定义:以太网交换机。
  • 工作层不同:R - 网络层,S - 数据链路层
  • 转发机制: R - IP addr,S - MAC addr
  • 主要功能: R - 隔离广播域,S - 不能 R - 用于连接不同网络,S - 组建局域网 R - 防火墙,配置复杂 交换机能干的事情,路由器也都可以。
  1. ARP 协议的功能干嘛用的? ARP:Address Resolution Protocol 地址解析协议。 所谓的地址解析,就是主机在发送帧前将目标 IP 地址转换成目标 MAC 地址的过程。ARP 请求就是:根据目的主机的 IP 地址,获得其 MAC 地址。

终端 PING 一个 IP 地址,使用 WireShark 关键字 arp 过滤,可以看到 ARP 请求。

  1. C 和 C++ 的区别?

::C++:: 融合了 3 种不同的编程方式:C 语言代表的过程性语言、C++ 在 C 语言基础上添加的类代表的面向对象语言、C++ 模板支持的泛型编程。

首先,C 语言编程原理:其理念是将大型程序分解成小型、便于管理的任务,是一种自顶向下的设计。结构化编程技术反映了::过程性编程的思想::,根据执行的操作来构思一个程序。即:数据 + 算法 = 程序。

其次,面向对象编程:OOP(Object-Oriented Programming)强调的是数据。在 C++ 中,类是一种规范,它描述了这种新型的数据格式,对象是根据这种规范构造的特定数据结构。OOP 程序设计方法首先设计类,它准确的表示了程序要处理的东西,并不仅仅是将数据和方法合并为类的定义,OOP 还有助于构建可重用代码。

OOP 特性:抽象、封装和数据隐藏、多态、继承、代码的可重用性。

最后,C++ 和范型编程:范型编程(Generic Programming)。C++ 有多种数据类型 —— 整数、浮点数、字符、字符串、用户定义的、由多种类型组成的复合结构。例如,要对不同类型的数据进行排序,通常必须为每种类型创建一个排序函数。泛型编程可以只编写一个泛型(即不是特定类型的)函数,并将其用于各种实际类型。C++ 模板(Template)提供了完成这种任务的机制。

  1. 你对多态的理解? 多态(Polymorphism)是 OOP 编程的一个重要思想在面向对象语言中,::一个接口,多种方法::即为多态。

C++ 的多态分为两种,静态多态和动态多态。

静态多态是通过函数重载实现的,在编译过程完成后就知道了应该调用哪个函数。

动态多态即运行时的多态性,通过虚函数(virtual)来实现的。虚函数允许子类重新定义成员函数,而子类重新定义父类的做法称为覆盖(Override),或者称为重写。

多态最常见的用法就是声明基类类型的指针,利用该指针指向任意一个子类对象,调用相应的虚函数,可以根据指向的子类的不同而实现不同的方法。

  1. 讲一下 tcp 的拥塞控制? TCP 的拥塞控制主要来避免两种现象,即::包丢失::和::超时重传::。一旦出现了这些现象就说明,发送的速度太快了,要慢一些。

一条 TCP 连接开始,cwnd 设置为一个报文段,一次只能发送一个;当收到这一个确认的时候,cwnd 加一,于是一次能够发送两个;当这两个的确认到来的时候,每个确认 cwnd 加一,两个确认 cwnd 加二,于是一次能够发送四个;当这四个的确认到来的时候,每个确认 cwnd 加一,四个确认 cwnd 加四,于是一次能够发送八个。可以看出这是指数性的增长

涨到什么时候是个头呢?有一个值叫做门限(ssthresh)为 65535 个字节,当超过这个值的时候,就要小心一点了,就不能增长那么快了。

于是,每收到一个确认后,cwnd 增加 1/cwnd,我们接着上面的过程来,一次发送八个,当八个确认到来的时候,每个确认增加 1/8,八个确认一共 cwnd 增加 1,于是一次能够发送九个,变成了线性增长

但是线性增长还是增长,还是越来越多,直到发送拥塞。拥塞的一种表现形式是丢包,需要超时重传。

有一种方式是,将 sshresh 设为 cwnd/2,将 cwnd 设为 1,重新开始慢启动。。但是这种方式太激进了,将一个高速的传输速度一下子停了下来,会造成网络卡顿。

快速重传算法。当接收端发现丢了一个中间包的时候,发送三次前一个包的 ACK,于是发送端就会快速的重传,不必等待超时再重传。TCP 认为这种情况不严重,因为大部分没丢,只丢了一小部分,cwnd 减半为 cwnd/2,然后 sshthresh = cwnd,呈线性增长。

TCP BBR 拥塞算法,它占满带宽,但是不占满缓存,时延较低。

  1. 左值引用和右值引用的区别?
  • 左值存放在对象中,有持久的状态;
  • 右值要么是字面常量,要么是在表达式求值过程中创建的临时对象,没有持久的状态。
  • 右值引用的对象,是临时的,即将被销毁;

如果我们将一个对象的内存空间绑定到另一个变量上,那么这个变量就是左值引用。在建立引用的时候,我们是「将内存空间绑定」,因此我们使用的是一个对象在内存中的位置,这是一个::左值::。

const int& qux = 42;  // OK: 42 是右值,但是编译器可以为它开辟一块内存空间,绑定在 qux 上

右值引用也是引用,但是它只能且必须绑定在右值上。右值引用应用在::语义移动::上,语义移动避免了数据的再拷贝带来的花销,提供一种数据的所有权的转交。

  1. 四种 cast 强制类型转换的区别和使用?
  • static_cast:普通的类型转换
static_cast<type-name>(value);

不提供运行时的检查,要在编写程序时确认转换的安装性。 (1)把::子类::对象的指针_引用转换为::父类::指针_引用(上行安全),这种转换是安全的。若把父类对象的指针_引用转换成子类指针_引用(下行不安全),这种转换是不安全的,需要编写程序时来确认。 (2)基本的数据类型转换。安全由程序编写人员保证。

  • dynamic_cast:用于处理多态
dynamic_cast<type-name>(expression);

指针转换失败,则返回空指针,若引用转换失败,则抛出异常。 把父类对象的指针_引用转换成子类指针_引用,即基类转换为派生类时使用 dynamic_cast

  • const_cast:用于移除类型的 const、volatile 属性。
const_cast<type-name>(expression);

常量指针被转换成非常量指针,并且仍然指向原来的对象;常量引用被转换成非常量引用,并且仍然引用原来的对象。

说明:使得 *pb 成为一个可用于修改 bar 对象值的指针,它删除 const 标签。

  • reinterpret_cast
reinterpret_cast<type-name>(expression);

可以转换任何类型的指针,不安全。不改变括号中运算对象的值,而是对该对象从位模式上进行重新解释。

  1. 讲一下智能指针?
  • auto_ptr auto_ptr 会导致所有权的转移,于此同时,原指针不再指向有效数据(后续再访问会出现错误)。

  • unique_ptr unique_ptr 是 auto_ptr 的升级,策略更加的严格。unique_ptr 同样采取建立所有权(ownership)的概念,对于特定对象,只能有一个智能指针可拥有它,只有拥有对象的智能指针的构造函数会删除该对象。

编译阶段即可发现错误, unique_ptr 相比 auto_ptr 有更加安全的机制 。move 函数可以移交所有权。

  • share_ptr shared_ptr 采用引用计数(reference counting)的策略。赋值时,计数加一,指针过期时,计数减一。仅当最后一个指针过期时,才调用 delete 。

  • weak_ptr weak_ptr 可以维持一种弱引用。 对象被析构了,weak_ptr 会自动等于 nullptr。 weak_ptr 可以还原成 shared_ptr 而不会让引用计数错乱。

自己动手实现智能指针:

  • 模版化(Template)
  • 运算符重载(operator)【* 解引用】 | 【-> 指向对象成员】 | 【bool 用在布尔表达式】
  • 拷贝构造和赋值:拷贝时转移指针所有权(舍弃 auto_ptr,选择 unique_ptr)
  • 引用计数
  1. 了解完美转发吗? 一个函数某一组参数原封不动地传递给另一个函数。这里不仅需要参数的值不变,而且需要参数的类型属性(左值/右值)保持不变,这叫做 Perfect Forwarding(完美转发)。

C++11 开始,完美转发由 std::forward 函数实现。底层实现和引用reference 密切相关:remove_reference 、右值引用、引用聚合。

  1. future 和 thread 了解吗? 与并发(Concurrency)编程相关,future 是一个更高的抽象,同样的结构,代码将大大简化,变量减少到只有一个未来量。

调用 async 可以获得一个未来量。在未来量上调用 get 成员函数可以获得结果。

  1. tcp/ip 四层模型和 osi 七层模型具体是哪些?

  1. 进程和线程的区别? 操作系统的设计,因此可以归结为三点: (1)以多进程形式,允许多个任务同时运行; (2)以多线程形式,允许单个任务分成不同的部分运行; (3)提供协调机制,一方面防止进程之间和线程之间产生冲突,另一方面允许进程之间和线程之间共享资源。

a.::地址空间和其它资源:::进程间拥有独立内存,进程是资源分配的基本单位;线程隶属于某一进程,且同一进程的各线程间共享内存(资源),线程是cpu调度的基本单位。

b.::通信:::进程间相互独立,通信困难,常用的方法有:管道,信号,套接字,共享内存,消息队列等;线程间可以直接读写进程数据段(如全局变量)来进行通信——需要进程同步和互斥手段的辅助,以保证数据的一致性。

c.::调度和切换:::线程上下文切换比进程上下文切换要快。进程间切换要保存上下文,加载另一个进程;而线程则共享了进程的上下文环境,切换更快。

算法题

  1. KMP 算法? KMP 算法和核心在于求解模式串的 next 数组,使得模式串与主串在匹配过程中出现失配情况时,大大降低没有必要的回退。

  2. 知道二叉树有哪些遍历的方式吗? 先序_中序_后序_层序遍历。非递归:先序_中序/后序需要使用栈(Stack)辅助,层序遍历需要使用队列(Queue)辅助。

后序遍历难点较高! 线索后遍历(线性结构),但是改变了树的指针结构。

  1. 快速排序的思想? 快速排序是一种基于分治法的重要的排序算法,归并排序也是基于分治技术。快速排序的核心在于切分(Partition)操作。根据切分的不同,可以分为普通快排(单路切分)、双路快排(双路切分)、三路快排(大于、等于、小于三路)。

  2. 冒泡排序

  3. 手撕 strcpy? 注:如果 dest 事先未分配足够的一片连续空间,则 dest++ 可能会覆盖其他的数据。

理解应用题

  1. 一个结构体,能够用 memcpy 判断两个结构体存的东西是不一样的吗? 所以,我不知道能不能?但是可以了解一下 memset 和 memcpy 函数。在对结构体变量都使用 memset 初始化的前提下,使用 memcmp 函数进行一个一个字节的比较,相同则返回 0。

memset 按字节赋值,对每个字节赋值同样的值。0 的二进制代码为全 0,-1 的二进制补码全为 1。所以一般赋初值要赋为 0 或 -1。如果对一个整型赋值为 1,int 占 4 个字节,最后结果为十进制的 16843009。

0000 0001|0000 0001|0000 0001|0000 0001
  int a;
  memset(&a, 1, sizeof(a)); // a is 16843009

如果有结构体成员有指针的情况,则还要再考虑,就如同深拷贝的浅拷贝问题。

memcpy sizeof(char) 等于 1,逐个字节的拷贝。

  1. 知道哈希表吗?怎么解决冲突?如果只有 32 个槽,怎么存放几千个数据?

hashtable,将关键字 K,通过散列函数 F(K) 映射到表中一个位置上。设计优秀的哈希函数,哈希表可以实现接近于 O(1) 的查询速度。当 F(K1) == F(K2) 时,称为冲突。

解决 Hash 冲突的方法有:线性探测法、二次探出法、开链法、再散列法。

如果只有 30 个槽,说明存在大量的冲突,平均每个槽会产生上百的冲突,此时第一级的哈希函数已经没有多大的优化的空间了,要么进行再 hash。我觉得采用开链法也是可取的,可以在每个槽后接上树结构冲突发生时,往树中添加即可,采用树结构可以保证查询的时间复杂度为 O(logn)。

  1. 用过 shell 脚本吗? 用过一点点,基于 Github Page 搭建了个人博客,本地编写博客后,执行一个脚本,自动提交和部署到原厂仓库。有一定的脚本语言基础:Python、Lua。

  2. 学习了哪些数据结构? ::线性数据结构:: 动态数组:Vector 扩容/缩容 链表(LinkedList):头节点、尾指针、循环链表 栈(Stack):链表栈、动态数组栈 队列(Queue):链表队列、动态数组队列、循环队列

::树结构:: 堆(Heap):优先队列,最大/最小堆 二分搜索树(BST) 平衡二叉树(AVL) 红黑树(RB-Tree) B 树和 B+ 树(B-Tree) 字典树(Trie)

::图结构:: 图的表示:邻接矩阵、邻接表。

::其他数据结构:: 并查集(Union Find) 哈希表(Hash-table) 集合(Set):HashSet、TreeSet 映射(Map):HashMap、TreeMap

  1. 你对 mfc 的印象? 微软基础类库(Microsoft Foundation Classes,简称 MFC)。 MFC 可以用面向对象的方法来调用 Windows API,以及能够更加敏捷的开发应用程序。

MFC 出现的时间比较早(1992),而 C++ 的第一个标准是 1998 年(C++98)。C++ 的发展比 MFC 更加迅猛发展,结果 MFC 的一些好的东西就成了它的陋习。

身边也没有同学学过 MFC。我对桌面程序开发有过一点点的经验,我采用的方案的 C++ 和 Qt,做的是一个可视化的排序的窗口。

  1. 用过哪些 UI 界面? 图形化方面了解一点点的 Qt 和 OpenCV。但是时间比较早了,大三的时候。

  2. 用过 qt 吗? 排序算法的可视化,采用的是 C++ 和 Qt:QPainter、自动重绘函数。

  3. 如何判断大小端,手写代码? 在 Socket 网络编程时,会涉及到大端序和小端序的转换。

  • 大端序(Big Endian):高位在前,低位在后。这是人类读写数值的方式。
  • 小端序(Little Endian):地位字节在前,高位字节在后。

计算机正常的内存增长方式是从低到高(栈不是),取数据方式是从基地址根据偏移找到它们的位置。小端序第一个字节是它的低位,符号位在最后一位,在做运算时,从地位开始,最终刷新符号位,运算较为高效。

大端序第一个字节就是高位,很容易知道它是正数还是负数,对于数值判断会很迅速。除了计算机内部处理,其他场合几乎都是大端序,比如网络传输和文件存储。

  1. 做了哪些面向对象编程的工作?
  • 大学对课程设计
  • 动手实现 C++ STL 的部分容器类,遵循 OOP 思想,类的设计,方法接口设计。

参考

  1. What is the difference between new_delete and malloc_free? - Stack Overflow https://stackoverflow.com/questions/240212/what-is-the-difference-between-new-delete-and-malloc-free

  2. 二分搜索树(BST)的前_中_后序遍历-递归+非递归 - 蓝本本 https://zhuanlan.zhihu.com/p/100926726

  3. 十大排序算法 - 蓝本本 https://zhuanlan.zhihu.com/p/100435276