面试体会

因为涉及到保密等原因就不说多了。我的建议是:多玩游戏。

面试准备

面试“2022腾讯游戏客户端开发公开课-学员”。这算是我第一次参加比较正式的面试吧,再加之本来口才就不好,所以这篇文章也写得口水话一点。统共30分钟,自问自答,就当是演练吧,希望到时候不要卡壳了😂。

下面是复习和准备时的一些知识点。C++的多态平时用的太少差不多都忘完了……

C++方面

请说明引用和指针的关系

指针的语法含义就是指向变量的地址。它本质是一个变量,用于存储其他变量的地址。指针所占空间的大小和机器或使用的编译器有关,32位机器指针占4字节,64位机器地址占8字节。

我们可以给指针附加权限,分为一般指针、指针常量int * const ptr,常量指针int const * p和指向常量的指针常量const int * const ptr

引用则是C++中引入的新类型,语法含义是变量的别名。它也是一个变量,在内存中占的大小也是地址的大小。它的安全性同指针常量一样,只能在初始化时指定为某个变量的别名,之后就不能改变成其他变量的了。

我们也可以给引用附加权限:常引用const int & ref。如果常引用引用的是变量,那么就不能使用引用来修改变量的值,增强了安全性;如果需要引用常量,那么就必须用常引用,否则会报错。

简述一下malloc和new、free和delete的区别与联系?

mallocfree是C语言中的函数。malloc的作用是申请一块连续的内存空间,并返回void类型的指针。如果申请失败,返回的就是空指针。所以使用malloc之后常常判指针是否为空。free的作用是释放之前申请的空间。

newdelete是C++引入的函数。对于内置类型,new的写法比malloc更简单;对于自定义类型,如类,new还可以调用构造函数;同样地,delete会调用析构函数。且new必须和delete搭配,malloc必须和free搭配,否则报错。

简述this指针。this指针存在于哪里?

这个问题嘛,得从类的存储模型开始说起。

类包括成员变量和成员函数。类是一块连续的内存空间,它的大小就是成员变量的大小,且遵循字节对齐的规则。成员函数在类中是不占空间的,它存储在公共的代码段。可以验证,同一类的所有实例相同成员函数的函数地址是相同的。

由于同一个类的所有对象都共用成员函数,所以当我们调用成员函数时,需要知道是哪一个实例在调用它,特别是成员函数内部涉及到对成员变量的操作时。C++采用的解决方式就是给每个成员函数添加一个默认的this指针。this指针指向调用这个成员函数的对象。

需要注意this指针是一个隐藏的函数参数,不需要我们手动添加,编译器会自动帮我们加上去。由于this指针是函数的形参,所以它存在于内存的栈空间。

简述C++面向对象的三大特性。

面向对象的三大特性为封装、继承与多态。

封装就是将数据和方法整合在一起,并用作用域限制符对其访问加以限定。在C++中的体现就是类。

继承就是子类(派生类)从父类(基类)那里获得父类的属性和方法,同时也可以增加自己的成员与方法。需要注意继承的方式:public继承父类的公有成员在子类中也是公有成员,保护成员在子类中也是保护成员;protected继承父类中的公有和保护成员在子类中都是保护成员;private继承父类中的公有和保护成员在子类中都是私有成员。三种继承方式父类的私有成员在子类中都不可见。

多态就是完成某个相同的行为时,不同的对象有不同的方法。它通过虚函数来实现:当父类和子类分别定义了两个函数名相同的函数且二者均为虚函数时,使用时将父类的指针或引用指向子类的实例,就可以通过这个父类指针或引用调用子类的重写后的方法了。

菱形继承是什么?缺陷是什么?怎么解决?

菱形继承就是一个类多继承于两个父类,同时两个父类又继承于同一个父类。它的问题就是最上面的父类的成员会在最下面的子类中出现两次,即数据冗余;当给子类的冗余成员赋值时,因为出现了多次,所以会因为歧义报错。总结下来问题就是冗余和歧义两个问题。

可以使用虚继承来解决这个问题。两个父类虚继承于同一个父类,子类中的之前冗余的成员就只会出现一次,就没有冗余和歧义的问题了。但是使用虚继承会增大子类对象的空间,因为它需要分别使用两个指针指向虚基表来表示偏移值,保证子类到父类的切片能正常进行。

实际上,我们应该尽量避免多重继承和多次继承,所以可以使用final关键字来加以限定,表明这是一个最终的类。

简要说明一下多态的应用场景。

多态首先可以应用在析构函数里。当我们使用父类的指针指向子类对象时,如果不将析构函数定义为虚函数,那么释放父类指针时只会调用父类的析构函数,子类的部分空间没有释放,造成内存泄漏。而将析构函数声明为虚函数,那么就会先调用子类的析构函数,再调用父类的析构函数。

另外一个场景就是简化程序,以图形为例。有图形类的父类,三角形、矩形、圆形等子类。当我们画这些图形时,只需要定义一个绘制函数,传入的类型定义为图形类,那么只需要做一个函数就可以首先所有图形的绘制,而不需要为每个图形定义一个绘制函数。

谈谈你对模板和STL的一些认识。

模板是为了提高程序的可复用性而引入的,它包括函数模板和类模板。

STL有六大组件,其中常常使用的就是容器。容器封装了数据结构,包括vectorliststackqueuesetmap等。使用时先传入相应的类型进行模板类的实例化,然后就可以调用其中的方法了。此外比较常用的还有算法,它包括了一些常用的函数如获取数组最大值maxValue()swapreversesort等。

关于继承于多态的一些坑题(笔试考到了子类和父类构造与析构函数的调用


DSA方面

说一下你对各种排序算法的理解。

排序分为外部排序和内部排序。外部排序的数据量很大,数据一般存储在辅存中,需要分批次调入内存,常用的有桶排序;我们研究的一般是内部排序。

冒泡排序的思想是每次都将记录序列从头到尾进行比较,选出一个最大或最小的元素到最后面。它的时间复杂度为$O(n^2)$,空间复杂度为$O(1)$。

插入排序的思想是将元素插入到排好的有序序列中,使有序序列越来越长。缺点是需要进行大量数组元素的移动。时间复杂度为$O(n^2)$,空间复杂度为$O(1)$。

希尔排序是插入排序的一种改进。先选取一个增量进行宏观的插入排序,然后不断缩小增量,进行插入排序直到增量缩小为1(1也要排)。由于进行了宏观的调整,所以最后插入排序的移动次数比较少,算法性能也很高。时间复杂度介于$O(n^2)$和$O(nlogn)$之间。

选择排序的思想是从无序序列中选出一个最大或最小的元素放到有序序列的末尾。时间复杂度为$O(n^2)$,空间复杂度为$O(1)$。

堆排序的思想是将记录梳理成一个大顶堆(升序)或小顶堆(降序),每次将对顶元素与最后一个元素交换,再将剩下的元素重新梳理为大顶堆或小顶堆。时间复杂度为$O(nlogn)$,空间复杂度为$O(1)$。

二路归并排序的思想是分治。将待排序的序列不断分解为很多子序列,对这些子序列进行排序后,再将这些有序的子序列合并为更长的有序序列。它的时间复杂度为$O(nlogn)$,空间复杂度为$O(n)$。

快速排序的思想是二分法:先选一个基准数,然后把大于和小于基准数的元素分别移到它的左边或右边;然后再从左边和右边分别选一个基准数,直到各分区只有一个数为止。时间复杂度为$O(nlogn)$,空间复杂度为$O(logn)$。

上面7中排序方法中,稳定的排序有冒泡排序、插入排序、二路归并排序;不稳定的排序有选择排序、希尔排序,堆排序、快速排序。

因为C++算法库提供了sortstable_sort函数,该函数使用快速排序,且可以自定义比较函数,泛用性比较强,所以实际上自己写排序函数的情况比较少。

STL中set和map的底层数据结构是什么?简要说明一下。

setmap包括mutisetmutimap的底层数据结构是红黑树,其中的元素是排好序的,默认为升序。红黑树是一颗自平衡的二叉排序树。它的特点是比BST更加平衡,同时又没有AVL达到严格平衡那样比较严苛的条件,追求性能上的最优。

unordered_set和unordered_map与set和map的区别是什么?简要说明。

它们的区别主要是底层的实现不同,这也导致了它们的一些特性不同。unordered_setunordered_map的底层数据结构为哈希表,元素无序排列。因为是哈希表,所以它更适合查找;而setmap的底层是红黑树,更适用于插入和删除比较频繁的情况。

其实真要复习DSA的话要看的还挺多的,所以暂时就到这了吧……


图形学方面(&OpenGL)

简要说明OpenGL的图形渲染流水线。

渲染流水线又称为渲染管线,简单来说就是将图形或图像从数据一步一步生成画面的过程。两个必要步骤就是顶点渲染和像素渲染,在可编程管线中对应的就是两个必须自定义的着色器:顶点着色器和片段着色器。

OpenGL早期使用的是固定管线。它向程序员提供了一系列接口,程序员要做的就是使用这些接口来实现图形的绘制和OpenGL状态的设置。可以将类比OpenGL类比为一台机器(状态机),但这时我们只能通过拨动开关来控制各部分的工作。

现在普遍使用的是可编程管线。它的特点就是程序员可以定制化地、最大程度地简化渲染管线的逻辑以提高渲染效率。这时相当于我们可以控制OpenGL状态机内部的工作方式。

总结一下,OpenGL的渲染流水线包括顶点渲染、图元装配、光栅化、像素处理与混合阶段。固定管线通过调用API实现,而可编程管线通过使用着色器实现。

简要描述图形学中的直线绘制算法?

首先最容易想到的算法就是DDA算法。它的原理就是直接使用直线的斜截式方程,在一个坐标轴上以单位间隔取样,另一个坐标轴以m或1/m变化,从而获得线段上的各像素点。由于像素点的位置都是整数,所以还需要进行取整以确定对应像素点位置。DDA算法应该在变化更快的方向上取样,这样的误差会低一些。具体来说就是斜率绝对值小于1,x轴取样;斜率绝对值大于1,y轴取样。它的缺点是浮点运算比较耗时。

然后是DDA算法的改进算法:Bresenham算法,它的目标是避免浮点运算。由于像素点最后都要从浮点数取整,所以从这里入手,推导出决策参数。再观察到下一个点的坐标(假设斜率大于0)要么加1,要么不变,所以可以通过决策参数来确定下一个点的坐标。

为什么图形学要用齐次坐标系?

使用齐次坐标系,可以把矩阵的加减法转化为矩阵的乘法,这样可以统一各种几何变换中三维矩阵的运算。

如平移变换,是平移向量加上位置向量;旋转变换,是旋转矩阵乘以位置向量;伸缩变换是伸缩矩阵乘以位置向量。使用齐次坐标系,就可以这些变换统一为相应的变换矩阵乘以位置向量。