模拟面试面经（一）_模拟算法面试

自己回答的部分省略，下面写的都是标准答案，还没写完，复习之后贴链接

简历相关

• 岗位：软件测试工程师
• 熟悉语言：C++
• 算法：排序，查找，贪心，动态规划
• 数据结构：vector、链表、二叉树
• 项目相关

面试过程

一、 自我介绍

姓名+学校+专业+技术+简单项目

二、 基础问题

1. 数组和指针的区别？
   [我的回答 ] 数组指定大小，指针可以扩容
   [标准答案]：
   几个方面：作用、概念、存储、初始化、传参
   https://blog.csdn.net/qq_36804363/article/details/89050799

2. 指针的大小
   [我的回答]：x32位 和x64都是四个字节
   [标准答案]：32位是4个字节，64位是8个字节，与机器字长相同

3. vector的理解（重点在扩容）
   [我的回答]：一个可以存储不同对象的容器
   [标准答案]：
   ① 封装好的动态数组，提供相关操作和接口。
   ② Vector将元素复制到dynamic array内部，是一种动态的顺序表结构。
   ③ Vector支持随机访问，可以以常量时间访问元素，Vector支持随机访问迭代器，以及STL提供的任何算法（排序、查找等）。
   ④ 对于插入、删除和移动等操作，Vector效率较低（类似于数组的特性）。

   【面试官】：内存机制是如何实现
   [我的回答]：线性表（标准答案：连续的内存空间）
   [标准回答]：（后来想到的）
   ① 只是单独定义没有给大小，在内存中是0
   ② 如果没有初始化大小（reserve(‘大小’)），直接使用push_back(),size()与元素相同，capacity()的值在当前内存空间已满的情况下增加当前空间的1倍，
   ③ 若是给定初始内存大小，当push_back()或者insert()所需内存大于当前拥有的内存时，以当前容量的1倍的方式扩容

   面试官：比数组好的地方在哪里
   [我的回答]：有插入、删除、清空、查找等便捷操作
   [标准答案]：最重要的点是实现扩容（当时前面没答到）

   【面试官】：如何实现扩容
   我的回答：若超出限定大小则+1 （笨死了！！）
   标准答案：
   ① 什么时候会扩容：vector的大小（size）是指当前元素所占用的空间，而容量（capacity）分配内存预留大小，当size超过capacity时，vector会自动扩容
   ② 当size>capacity时，capacity会变成当前大小的1.5-2倍，动态的重新分配当前大小的1.5~2倍的新内存区，再把原数组的内容复制过去，原来的删除。
   ③ 提一下reserve()函数，可以显示指定预留空间的大小，而避免vector反复进行内存重新分配，提高利用率，但是reserve不能减小vector容量，若使用其定义一个小于当前容量的值，则不会有任何作用
   补充vector知识① 补充vector②

4. 对多态的理解？
   我的回答：基类中定义的方法在子类中得到不同的实现
   标准答案：多态分为静态实现和动态实现
   https://blog.csdn.net/qq_39412582/article/details/81628254

5. 动态规划算法解决填方格问题
   我的回答：用数学方法推导递归公式，得出一个类似斐波那契数列的结果
   标准答案：递归操作

6. 递归底层实现是什么
   我的回答：使用栈实现，如果递归次数过多，会导致栈溢出问题
   标准答案：函数自身调用自身，最先开始的函数最后结束，最先开始的函数最先入栈，每次调用一个新函数就会入栈一次，最后实参压入栈中，与形参结合返回，再返回下一个函数直到全部执行完毕。

7. STL库的理解
   没答上来

8. 排序算法
   （1） 本想讲一个快排，一个非比较类排序，讲快排的时候被面试官打断，有些问题没答出来，非比较类排序没有机会讲。
   （2） 主要讲了快排的基本实现原理，时空复杂度O(nlogn)/O(n)，最坏情况O(n²)
   （3） 面试官的问题：最坏情况是什么？如何优化快排？为什么比冒泡排序快？什么情况下使用快排？
   O(N²)、随机选择基准，两端遍历查找，分支递归

9. 查找算法
   面试官：熟练的查找算法
   我：二分查找、不太熟悉的红黑数、B树、B+树等
   面试官：对红黑树的理解
   我：不太熟悉（不熟悉就不要讲出来）
   标准答案： 二分，简单一维搜索、二叉树查找等

10. 实现strcpy(char * src,char *drc)
    我：（错误样例）应该没那么简单直接复制，考虑覆盖。
    【正解】：
    ① const 修饰：源字符串参数用const修饰，防止修改源字符串；
    ② 空指针检查:源端和目的都检查
    ③ 目的指针dst移动，需要辅助ret表明首指针

    char * strcpy(char *dst,const char *src)   
    {
       if((dst==NULL)||(src==NULL))
               return NULL; 
        char *ret = dst; //[1]
        while ((*dst++=*src++)!='\0'); //[2]
        return ret;//[3]
    }
    1
    2
    3
    4
    5
    6
    7
    8

三、 项目问题

1. 功能实现
2. 问题分析
3. 负责部分
4. 遇到的问题以及如何解决
5. 简述贝叶斯定理
   （1）描述条件概率公式
   （2）结合项目
   简历上的项目建议：项目不用太多，详细且深度

四、 岗位相关问题

面试官提到，但是前面基础不行就没有详细问这些问题！

1. 常用测试软件
2. GDB调试
3. 内存泄漏
4. BUG出现原因

面试总结

1. 复习基础知识，C++11 新特性，STL库，内存机制
2. 数据结构、算法基础
3. 不会的东西不要写，不会的东西不要提到