C++闯关手册 - 面试实例:第三轮面试
第三轮面试通常会更加关注你的团队合作能力和沟通技巧,较少情况下也会有编程题。面试官通常是你的部门领导,可能会侧重询问你在团队项目中的角色,或者让你描述一下你解决项目问题的经验。本文包含高频面试题目及解析,注意问的和回答的越深度底层,越凸显更高的技能。
C++ 闯关手册 - 面试实例
第三面:经验沟通
1)自我介绍
每一个面试都会有个自我介绍,这里省略,基本面试几次自己都会说的比较溜了。面试官是有可能根据你的介绍内容进行提问的,这里介绍的时候可以根据情况引导面试官。
以下是一个示例自我介绍的结构(示例还是比较空洞和形式化,一定针对自己的情况细化和调整,且符合个人口吻):
自我介绍示例
“大家好,我叫[你的名字],目前是一名[你的职位]。我拥有[你的学历],在[你的学校]主修[你的专业]。我有[多少年]的C++开发经验,主要从事[你的领域或行业]的工作。
在过去的工作中,我参与了多个重要项目,其中包括[简要描述一个或两个项目]。例如,在一个直播系统的开发项目中,我担任了后端开发工程师的角色,负责系统架构设计和性能优化。通过引入CDN和负载均衡策略,我成功解决了高并发情况下的延迟问题,大幅提升了用户体验。
我熟悉C++的各种特性和标准库,擅长使用STL进行高效的数据结构和算法设计。此外,我还具备多线程编程、网络编程和分布式系统的开发经验。为了不断提升自己的技术水平,我经常参与开源项目,并积极学习最新的技术趋势。
我非常期待能够加入贵公司,与优秀的团队一起工作,共同解决技术难题,推动项目的成功!”
自我介绍结构
- 基本信息:介绍你的名字、职位、学历和专业背景。
- 工作经验:简要描述你的工作经验和C++开发经验。
- 项目经验:重点介绍一个或两个你参与过的重要项目,突出你的角色和贡献。
- 技术技能:列出你熟悉的技术和擅长的领域。
- 学习和成长:提到你如何保持技术更新和提升自己的技能。
- 期望:表达你对加入公司的期待和愿景。
2)问项目,深挖项目中遇到的问题
这里写简历时候或面试前可以提前准备的项目问题,简历里提高点要提前想想可能会挖哪些点,提前有个预期。
很可能问到:你遇到过的难题是如何解决的?
提前挑一个项目中遇到的困难问题或用了很长时间才解决的问题:讲述问题表象,如何从各个方面排查,最后是如何确定到问题点,并用了什么方式解决的。
不一定是很大的问题,也可能最后就是一个很小的点,因为但这就是你的经验,知道了经历过了就觉得很简单,但是不知道的人就大概率要重复踩坑的。
回答这个问题时,可以按照以下步骤进行:
- 具体问题描述:详细描述项目中遇到的一个具体问题。确保问题具有一定的技术深度和复杂性。
- 分析问题原因:解释你是如何分析和诊断这个问题的原因。可以提到使用的工具、方法和技术。
- 解决方案:详细描述你是如何解决这个问题的。包括你采取的步骤、使用的技术和工具,以及你做出的决策。
- 结果和影响:说明解决方案的效果,以及它对项目的整体进展和最终结果的影响。
示例回答:
“在我们开发直播系统的过程中,遇到了一个严重的延迟问题。系统在高并发情况下,直播视频的延迟显著增加,影响了用户体验。
为了找出问题的根源,我首先使用了性能分析工具(如Wireshark和tcpdump)对系统进行全面的网络流量分析。通过分析,我发现瓶颈主要集中在视频流的传输和解码过程中。
经过进一步调查,我发现问题的原因是服务器在处理大量并发连接时,网络带宽和CPU资源不足,导致视频流传输和解码出现延迟。为了缓解这个问题,我决定引入CDN(内容分发网络)和负载均衡策略。
具体来说,我将视频流分发到多个CDN节点,以减少单个服务器的负载。同时,我还实现了负载均衡,将用户请求分配到不同的服务器上,以进一步提高系统的并发处理能力。
实施这些优化措施后,系统的延迟显著降低,用户体验得到了极大改善。这次问题的解决不仅提高了系统的性能,还让我深入理解了实时视频传输和优化方法。”
通过这种结构化的回答方式,你可以清晰地展示你在项目中遇到问题、分析问题和解决问题的能力。
3)做过的项目里,哪个项目的收获最大?
类似前面2种所说,项目中遇到的问题,可以事先准备自己的答案;
回答这个问题时,可以按照以下步骤进行:
- 选择一个项目:选择一个你参与过的、对你影响最大的项目。这个项目应该能够展示你的技能、解决问题的能力以及团队合作的经验。
- 描述项目背景:简要介绍项目的背景、目标和你在项目中的角色。
- 面临的挑战:详细描述你在项目中遇到的主要挑战,以及你是如何解决这些挑战的。
- 收获和学习:重点说明你从这个项目中学到了什么,比如技术技能、项目管理经验、团队合作能力等。
- 结果和影响:描述项目的最终结果,以及它对你个人和团队的影响。
示例回答:
“在我参与的所有项目中,收获最大的项目是一个直播系统的开发项目。在这个项目中,我担任了后端开发工程师的角色。
项目的目标是开发一个高并发、低延迟的直播系统,能够支持数万用户同时在线观看直播。这个项目的主要挑战在于如何设计系统架构以确保高可用性和低延迟。
在项目中,我学习并应用了多种技术,如RTMP协议、HLS协议、WebRTC等。同时,我还深入研究了多线程编程和网络通信技术,以优化系统性能。
通过这个项目,我不仅提升了自己的技术能力,还学会了如何在团队中有效地沟通和协作。最终,我们成功地交付了一个高效稳定的直播系统,得到了用户的高度评价。
这个项目让我深刻理解了实时系统的复杂性和重要性,也让我在解决实际问题的过程中积累了宝贵的经验。”
4)vector的push_back函数,时间复杂度是多少,涉及到vector容量不足发生拷贝的时候,时间复杂度又是多少,这两个的平均时间复杂度是多少?
重复问题,前面一面文章里第11条的答案有涉及,但请注意,这很可能是你之前面试的反馈这个地方回答的不对或不好,这里是给你机会再回答一次,看你有没有自我认识到问题,有没有复盘并纠正自己。
std::vector
的push_back
操作在大多数情况下具有常数时间复杂度 O(1),这是因为vector
通常会预留额外的存储空间来容纳新元素。当vector
的当前容量足以容纳新元素时,push_back
操作只需将新元素添加到vector
的末尾并更新大小即可,这是一个常数时间操作。
然而,当vector的容量不足以容纳新元素时,vector
需要进行扩容操作,这包括分配一个更大的内存块、将现有元素复制或移动到新的内存块中,然后添加新元素。这个过程的时间复杂度是线性的 O(n) ,其中(n)是vector
扩容前的元素数量。
尽管扩容操作的时间复杂度是线性的,但这种情况发生的频率相对较低。
std::vector
通过以指数方式增加容量(通常是将当前容量加倍)来减少扩容的次数,这意味着随着元素的添加,扩容操作发生的频率会逐渐减少。
考虑到扩容操作的摊销(平均)成本,push_back
操作的平均时间复杂度(也称为摊销时间复杂度)仍然是常数时间,即 O(1)。这意味着尽管偶尔会有较慢的插入操作(由于需要扩容),但从长远来看,每个push_bac
操作的平均成本是常数时间的。
5)进程和线程的同步方式,哪些同步方式可以用在线程中,哪些同步方式可以用在进程中而不能用在线程中?
重复问题,前面一面文章里有涉及进程线程同步方式问题,但请注意,这很可能是你之前面试的反馈这个地方回答的不对或不好,这里是给你机会再回答一次,看你有没有自我认识到问题,有没有复盘并纠正自己。当然,也有可能就是特别注重这个问题。
参考前面一面文章13条 相关“进程线程同步” 的答案及扩展部分;没有看过的小伙伴,可以点击链接查看,或者从系列文章搜索“面试实例:第一轮面试”。
在进程和线程的同步中,有一些同步方式可以在两者中通用,而有些则只能在特定的上下文中使用。以下是详细的分类:
线程同步方式
这些同步方式主要用于线程之间的同步:
- 互斥锁(Mutex):用于保护共享资源,确保同一时间只有一个线程可以访问资源。
- 读写锁(Read-Write Lock):允许多个线程同时读,但只允许一个线程写。
- 条件变量(Condition Variable):用于线程间的通知机制,通常与互斥锁一起使用。
- 自旋锁(Spinlock):线程在等待锁时会不断循环检查锁的状态,而不是进入睡眠状态。
- 屏障(Barrier):使一组线程在某个点上等待,直到所有线程都到达该点。
进程同步方式
这些同步方式主要用于进程之间的同步:
- 信号量(Semaphore):可以用于线程和进程之间的同步,但在进程间同步时需要使用系统提供的命名信号量。
- 共享内存(Shared Memory):进程间可以通过共享内存进行通信和同步。
- 消息队列(Message Queue):用于进程间通信和同步。
- 管道(Pipe):用于进程间通信和同步。
- 文件锁(File Lock):通过锁定文件来实现进程间的同步。
只能用于进程同步的方式
这些同步方式只能用于进程之间的同步,不能用于线程之间:
- 命名信号量(Named Semaphore):用于不同进程间的同步。
- 共享内存(Shared Memory):用于不同进程间的通信和同步。
- 消息队列(Message Queue):用于不同进程间的通信和同步。
- 管道(Pipe):用于不同进程间的通信和同步。
- 文件锁(File Lock):通过锁定文件来实现进程间的同步。
只能用于线程同步的方式
这些同步方式只能用于线程之间的同步,不能用于进程之间:
- 条件变量(Condition Variable):通常与互斥锁一起使用,用于线程间的通知机制。
- 自旋锁(Spinlock):线程在等待锁时会不断循环检查锁的状态,而不是进入睡眠状态。
- 屏障(Barrier):使一组线程在某个点上等待,直到所有线程都到达该点。
总结来说,互斥锁、读写锁、信号量等可以用于线程和进程的同步,而条件变量、自旋锁、屏障等主要用于线程同步。共享内存、消息队列、管道、文件锁等主要用于进程同步。
6)同步方式哪种效率最高,为什么?
参考前面一面文章第13条 相关“进程线程同步” 的答案及扩展部分;没有看过的小伙伴,可以点击链接查看,或者从系列文章搜索“面试实例:第一轮面试”。
同步方式的效率取决于具体的使用场景和需求。以下是几种常见同步方式的效率比较及其原因:
1. 自旋锁(Spinlock)
- 效率:在短时间内锁竞争较少的情况下,自旋锁效率最高。
- 原因:自旋锁在等待锁时不会进入睡眠状态,而是不断循环检查锁的状态。这避免了线程上下文切换的开销,但如果锁竞争激烈或等待时间较长,会导致CPU资源浪费。
2. 互斥锁(Mutex)
- 效率:在锁竞争较多或等待时间较长的情况下,互斥锁效率较高。
- 原因:互斥锁在等待锁时会使线程进入睡眠状态,避免了CPU资源的浪费。虽然线程上下文切换有一定开销,但在高并发场景下,这种开销通常低于自旋锁的CPU消耗。
3. 读写锁(Read-Write Lock)
- 效率:在读操作远多于写操作的情况下,读写锁效率较高。
- 原因:读写锁允许多个线程同时读,但只允许一个线程写。这减少了读操作的锁竞争,提高了系统的并发性能。
4. 信号量(Semaphore)
- 效率:信号量的效率取决于具体的使用场景。
- 原因:信号量可以控制多个资源的访问,适用于需要计数的同步场景。它的效率在于灵活性,但在简单的互斥场景下,可能不如互斥锁高效。
5. 条件变量(Condition Variable)
- 效率:条件变量用于复杂的同步场景,效率取决于具体的使用方式。
- 原因:条件变量通常与互斥锁一起使用,用于线程间的通知机制。它适用于需要等待特定条件的场景,但在简单的互斥场景下,可能不如互斥锁高效。
总结
- 自旋锁:适用于短时间锁竞争较少的场景,避免了线程上下文切换的开销。
- 互斥锁:适用于锁竞争较多或等待时间较长的场景,通过线程睡眠避免了CPU资源浪费。
- 读写锁:适用于读操作远多于写操作的场景,提高了系统的并发性能。
- 信号量:适用于需要计数的同步场景,灵活性高。
- 条件变量:适用于复杂的同步场景,通常与互斥锁一起使用。
选择哪种同步方式效率最高,取决于具体的应用场景和需求。一般来说,自旋锁在短时间锁竞争较少的情况下效率最高,而互斥锁在高并发场景下更为适用。
7)前面几面你认为自己有哪些地方可以答得更好,有哪些地方不足?
在面试中,当面试官提出这样的问题时,他们通常希望了解你的自我反思能力以及你如何从经验中学习和成长。
以下是一个建议的回答框架,你可以根据自己的实际情况进行调整:
- 正面评价自己的表现:首先,简短地提及你认为自己做得好的方面,这显示了你能够认识到自己的优点。
- 诚实地指出可以改进的地方:然后,诚实但不过分批评地指出一到两个你认为自己可以做得更好的方面。选择那些你已经有计划或正在努力改进的领域。
- 具体的改进措施:对于每一个你提到的不足之处,提供一个具体的改进计划或者你已经在做的事情来说明你是如何积极应对和改善的。
- 学习和成长的态度:最后,强调你对学习和成长的积极态度,以及你如何将这些经验转化为未来工作中的优势。
示例回答:
"回顾之前的面试,我认为在技术深度和问题解决策略方面,我展示了我的能力,并且能够清晰地表达我的思路。但我也意识到,在讨论我以前项目中的特定挑战时,我可能没有充分展示我是如何具体分析问题并找到解决方案的。
为了改进这一点,我开始在准备面试时,更加注重细节,确保我能够详细说明问题解决的每个步骤,包括我所采取的方法和最终的成果。此外,我也在提高我的编码技能,特别是在数据结构和算法方面,通过在线课程和日常练习来加强这些领域的知识。
我相信,通过这些努力,我能够更好地展示我的技术能力和解决问题的方法,将我的不足转变为我成长和学习的机会。"
这种回答方式展示了你的自我反思能力,同时也表明了你积极改进并从经验中学习的意愿。
8)算法题:输出树的所有既是叶子节点又是左节点的值的总和
首先,我们需要定义一个递归函数来遍历树。在遍历过程中,我们会检查当前节点是否是叶子节点(即没有左右子节点)以及是否是其父节点的左子节点。如果满足这两个条件,我们就将其值加到总和中。
遍历方式实现一般就是递归和非递归,下面C++示例代码,递归和非递归都进行了实现,并实现测试用例测试:
注意:
写测试用例可选,为了节省面试时间,可以给面试官提下测试用例就先不写代码了,可口头列几个测试用例数据,突出你的良好的开发习惯以及对考虑周全。测试用例,也是在实际开发过程中良好的习惯,起码是对自己程序的负责,也是提升自己程序健壮性、执行效率的常用手段。
/*
* 1. 输出树的所有既是叶子节点又是左节点的值的总和
*/
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
// 定义树的节点结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// 使用初始化列表构建二叉树, 例如: TreeNode{3, 9, 20, -1, -1, 15, 7},
// -1表示空节点,层序遍历顺序
TreeNode(std::initializer_list<int> ilist) {
if (ilist.size() == 0) return;
auto iter = ilist.begin();
this->val = *iter++;
std::queue<TreeNode*> q;
q.push(this);
while (iter != ilist.end()) {
TreeNode* node = q.front();
q.pop();
if (iter != ilist.end()) {
if (*iter != -1) {
node->left = new TreeNode(*iter);
q.push(node->left);
}
++iter;
}
if (iter != ilist.end()) {
if (*iter != -1) {
node->right = new TreeNode(*iter);
q.push(node->right);
}
++iter;
}
}
}
// 二叉树的层序遍历
void levelOrderTraversal(TreeNode* root) {
if (!root) return; // 如果根节点为空,直接返回
std::queue<TreeNode*> q; // 创建一个队列
q.push(root); // 将根节点入队
while (!q.empty()) { // 当队列不为空时
TreeNode* node = q.front(); // 取出队列前面的节点
q.pop(); // 将该节点从队列中移除
std::cout << node->val << " "; // 访问节点值
if (node->left) q.push(node->left); // 如果左子节点存在,将其加入队列
if (node->right) q.push(node->right); // 如果右子节点存在,将其加入队列
}
std::cout << std::endl;
}
void deleteTree(TreeNode* root) {
if (root == nullptr) return;
deleteTree(root->left);
deleteTree(root->right);
delete root;
}
void deleteTreeNonRecursive(TreeNode* root) {
std::stack<TreeNode*> toDelete;
if (!root) {
toDelete.push(root);
}
while (!toDelete.empty()) {
TreeNode* node = toDelete.top();
toDelete.pop();
if (!node->left) toDelete.push(node->left);
if (!node->right) toDelete.push(node->right);
delete node;
}
}
};
// 辅助函数,递归计算既是叶子节点又是左节点的值的总和
int sumOfLeftLeavesHelper(TreeNode* node, bool isLeft) {
if (!node) return 0; // 如果节点为空,返回0
// 如果是叶子节点并且是左节点,返回节点的值
if (!node->left && !node->right && isLeft) return node->val;
// 递归计算左右子树,返回总和
return sumOfLeftLeavesHelper(node->left, true) +
sumOfLeftLeavesHelper(node->right, false);
}
// 递归算法主函数,计算既是叶子节点又是左节点的值的总和
int sumOfLeftLeaves(TreeNode* root) {
return sumOfLeftLeavesHelper(root, false);
}
// 非递归方式实现
int sumOfLeftLeavesNonRecursive(TreeNode* root) {
if (!root) return 0;
std::stack<TreeNode*> stack;
stack.push(root);
int sum = 0;
while (!stack.empty()) {
TreeNode* node = stack.top();
stack.pop();
if (node->left) {
if (!node->left->left && !node->left->right) {
sum += node->left->val;
} else {
stack.push(node->left);
}
}
if (node->right) {
stack.push(node->right);
}
}
return sum;
}
// 编写测试用例
using funcType = std::function<int(TreeNode*)>;
void testSumofLeftLeaves(funcType func, std::initializer_list<int> ilist,
int expected) {
TreeNode* root = new TreeNode(ilist);
root->levelOrderTraversal(root);
int result = func(root);
if (result == expected) {
std::cout << "[PASSED]: result(" << result << ") == expected(" << expected
<< ") " << std::endl;
} else {
std::cout << "[FAILED]: result(" << result << ") != expected(" << expected
<< ") " << std::endl;
}
root->deleteTree(root);
}
int main() {
// 测试用例
std::vector<std::pair<std::initializer_list<int>, int>> testCases = {
{{3, 9, 20, -1, -1, 15, 7}, 24},
{{1, 2, 3, 4, 5}, 4},
{{1, 2, 3, -1, -1, 4, 5}, 6},
{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, 24},
};
// 测试递归解法
for (const auto& testCase : testCases) {
std::cout << "sumOfLeftLeaves: " << std::endl;
testSumofLeftLeaves(sumOfLeftLeaves, testCase.first, testCase.second);
std::cout << "sumOfLeftLeavesNonRecursive: " << std::endl;
testSumofLeftLeaves(sumOfLeftLeavesNonRecursive, testCase.first,
testCase.second);
std::cout << std::endl;
}
return 0;
}
测试结果输出如下:
sumOfLeftLeaves:
3 9 20 15 7
[PASSED]: result(24) == expected(24)
sumOfLeftLeavesNonRecursive:
3 9 20 15 7
[PASSED]: result(24) == expected(24)
sumOfLeftLeaves:
1 2 3 4 5
[PASSED]: result(4) == expected(4)
sumOfLeftLeavesNonRecursive:
1 2 3 4 5
[PASSED]: result(4) == expected(4)
sumOfLeftLeaves:
1 2 3 4 5
[PASSED]: result(6) == expected(6)
sumOfLeftLeavesNonRecursive:
1 2 3 4 5
[PASSED]: result(6) == expected(6)
sumOfLeftLeaves:
1 2 3 4 5 6 7 8 9 10 11
[PASSED]: result(24) == expected(24)
sumOfLeftLeavesNonRecursive:
1 2 3 4 5 6 7 8 9 10 11
[PASSED]: result(24) == expected(24)
12)反问环节
重复环节:一般可以问些岗位、团队相关的,如:面试的岗位会大概负责什么方向?团队在公司的定位及未来的方向?这也是要求职者本质需要关注的问题,团队的问负责人会更好。
总结:
整体面试实例里的题目群来自一次实际面试,可以发现在 第三轮面试中有重复的题目,所以每次面试之后进行总结纠正,基本上面试三五家之后整体面试的大部分问题都可以掌握,再之后看面试官的偏好和公司偏好能否和你的匹配了。公司都是想招聘一个能力符合、预算符合且可补充空缺的人选,有时候还是需要运气成分的。