华芯巨数面经

一面

面试官背景计算机, 面试流程总结: 个人介绍+项目介绍+C++基础+算法数学

C++基础

• shared_ptr与unique_ptr

要不是前几天才看到了里面的实现, 就一点都回答不上来, 没用过

区别:

• unique_ptr: 只能被一个对象持有, 该对象拥有该指针的唯一所有权
  • 使用场景: 自动释放内存: 避免析构函数中调用 delete 进行指针内存回收, 或调用 delete 之前已经进行了异常抛出从而跳过内存回收
  • 特点: 由于单个对象持有, 因此只能移动而不能复制
• shared_ptr: 共享所有权, 多个shared_ptr共享同一块内存(实现原理同basic_string 引用计数)
  • 使用场景: 可能需要多个对象共享同一块内存时 或 将关键线程中要进行的析构对象转移给另一个线程, 从而解放关键线程
  • 特点: 可以移动也能够复制
• static_cast与dynamic_cast

一开始根本没想起这是个强制类型转换, 答的up cast思想, 提醒后才惊觉. 竞赛里根本没用过 dynamic_cast 寄

算法里面不涉及多个类关系, 用不上正常

• static_cast: 强制类型转换(同C), 将表达式转换为对应类型, 在编译时检查, 但没有运行时类型检查确保安全性
  • 适用场景: 基类与派生类间的指针或引用转换( up-cast 安全, down-cast 因为没有类型检查所以不安全), 基本类型间的转换( intTochar ), 空指针转换为目标类型的空指针( 内存声明 ), 将任意类型转换为 void
• dynamic_cast: 运行时进行类型检查从而保证安全性, 用法如下
  • 适用场景: 类层次之间的上下行转换, 上行转换同 static_cast, 下行转换增加类型检查

// type*必须是一个有效的类类型指针
dynamic_cast<type*>(e);
// type必须是一个类类型, 且必须为左值
dynamic_cast<type&>(e);
// type必须是一个类类型, 且必须为右值
dynamic_cast<type&&>(e);

算法

• TopK问题

当年嫌麻烦, 秒答优先队列. 显然人家要你说快排结合. 大致思想清楚, 具体细节, 比如快排 partition 和整个TopK形似二分的框架有点忘记.

• 计算机图形学: 判断点在多边形内部

秒答射线查看交点个数, 脑子里还想到了一个顶点与点构成的夹角和, 但是不确定夹角和具体是多少( 忘了 ). 追问具体实现, 答解方程, 要求优化.

确实没想到怎么优化, 勉强答了一个构造特殊射线, 但自己否定了自己. 根据面试官提示, 构造水平或竖直射线, 通过射线的 (x,y) 信息与线段两点的坐标分类讨论

• 最小生成树

忘记定义, 经过提醒之后口胡 dijkstra, 立马改成 Prim

追问另一种实现, 忘记名字( 实际是 Kruskal ), 只记得枚举边了, 具体实现有点忘了. 一边答题一边纠结最终的生成树是否连通, 后面试官答树的概念, 通过边数与点数解答

数学

• 单随机序列概率论问题: 一个已知长度的序列 nums, 求能拿到其最大值的概率

毫无头绪( 面试官说正常 ), 面试官拆解问题为”经典主持人提醒你3选1奖品, 拿最好的”的条件概率问题. 秒答策略与50%概率( 还好我似乎在知乎看着玩类似的东西 ).

然后推广至长度为 n 的选择, 进一步提醒前 m 步观察比较, 第 k 步进行选择. 毫无头绪, 猪脑过载, 全身出汗. 进一步提醒拆分成两个事件乘积.

后续勉强答了一个二重求和公式套后 (n-m) 序列中存在最大值 乘 第 k 步是最大值的概率, 给定 m k 的求和范围.

比喻: 这一部分基本属于我和面试官两人在泥地摔跤, 有点像两人共同解决这个问题?

小结

C++ 炸中炸, 个人准备也是偏向 STL 的源码实现, 这种水滴石穿的东西也有可能是我没背 C++ 基础的考点? 算法答的还行, 除了有点紧张脑抽, 其中图形学真的是我一生之痛, 我就知道要考但我真的准备不过来. 后续数学部分emmmmm, 也是, 面试的时候只可能考概率论嘛, 怎么可能考你微积分呢, 然而我概率论真的不行, 不过别人也知道.

后续加强策略: 经典算法 > 图论 » C++

内推人反馈总结: 涉险过关, 等待二面

二面

给了一篇 EDA 相关的论文, 具体要求不详, 看完之后安排二面

自己看了论文, 翻了源码核心部分, 整理了一个粗糙的报告

个人介绍: 实验中的更细一点的流程与步骤和研究重点

挺顺利的, 毕竟我自己做的

个人介绍: 对 EDA 的了解

回答的不好, 之前看 EDA Introduction 的时候过了一遍但没怎么记住流程. 大体套了一个本科阶段的 TinyOS 对硬件设计 toolchain 的评价. 自我评价我觉得这部分很不熟悉 EDA

论文: 论文中的一个错误点

完全没料到这个地方有错误, 可能太过于关注代码实现. 代码实现中, 因为对电路图解析这一部分不熟悉, 所以也没太看出有什么问题. 他提出问题之后我才觉得没问题.

这个错误点没回答出来, 然后提醒后问算法流程如何优化来避免这个情况.

答: 套用后文的 diamond_search.

追问避免更多的计算量, 没回答出来. 提醒优先搜索可用点而非优先进行优化(我感觉我答的意思大致差不多)

论文: 介绍论文流程

把自己总结的结合论文说出来, 加上了对论文的一些质疑. 有一些地方有点问题, 似乎追问了一些东西但我没听出这是个问题?

至此开始, 后面的交流逐渐费力了起来.

论文: 问后文自己画蛇添足补充的 diamond_search

回答的这个的通用流程, 但是和代码中的不一样. 交流过程逐渐复杂, 因为我其实还是不太懂这个东西. 后面回答的有点偏向论文而非我看到的代码了. 代码也确实没怎么看懂.

其他: 数学上的一些优化方法

还好之前看模拟退火的时候看到了一些, 说的梯度下降+基于动量的梯度下降+模拟退火. 问有约束情况下: 想起笔试的题目, 回答拉格朗日乘数.

这一部分过的很快, 因为深入下去我也确实不知道怎么回答了.

其他: 平时研究的算法

早知道说 KMP 了, 结果说了自己最早写的忘得最多的背包问题. 只能说回答到了皮毛, 根本没办法深入, 都忘了完全背包和 01背包 dp 的具体方向了.

追问 dp 与贪心的区别: 感觉答到点上了, 贪心 < dp, 要满足贪心策略, 贪心进行子问题划分, 每个问题求最优解, dp当前状态不一定是先前子状态的最优和.

小结

我懂的沟通的很顺利, 我不太清楚的时候沟通异常费力(我个人角度), 等后续通知吧

后续, 涉险过关, 准备最终面( BOSS面? )

三面(终面)

准备工作

本来得到内部消息, 说是评价不算太高可能加试, 加试是系统设计手撕算法, 感觉还行阿, 算得上终面之前增加一些好印象. 后面通知没有加试直接终面.

终面内容未知, 据说看感觉? 然后去年被刷率看着巨高, 北大20进1?

心态逐渐躺平, 从一面极度紧张->二面心态放松->终面躺平等死

打算准备工作: 维持刷题保持手感和心态, 仔细过一遍自己写过的 blog 把之前的知识熟悉一下

人员

大老板+一个leader(?)

类似人力的问题

了解个人背景(职业规划, 优缺点, 过去遗憾的点), 了解过往项目背景

我印象比较深刻的是问代码量, 原来是不算刷的题的代码行数的. 答了个 5000, 我也没预估阿, 都是实验代码, 两组做完的+两组没做完的怎么着也有个一万了吧?

语言基础

• C++ Vector的 append 以及内存申请情况

还好之前看了连续序列, 能答上一点根据 cap 加倍扩充当前容量的东西. 追问优化方向, 答的每次扩充固定 buffer 长度. 然后面试官觉得这个有问题, 嘶, 可能是因为我回答的偏向 push_back 而非 append 一整个数组?

补充提前申请空间, 答 reserve, 不知道对不对阿.

让计算长度为 L_1 … L_N 的数组依次 append 的时间复杂度

答: 求和, 错! 我考虑太多了, 考虑到内存声明与分配了. 共同梳理了一下分配过程: 分配内存, 逐个拷贝赋值

真的不是底层继承 deque, 用指针实现的吗? 现在反应过来确实不是阿, 要不然不能 O(1) 随机访问阿

拷贝赋值这个提醒就很大了, 加权和咯, 内存声明次数就 N 次咯.

• 操作系统的内存申请过程

没背八股, 寄! 谁让我之前往那个方向考虑, 人家顺着我问已经很善良了!

算法理解

• 应用题, 先问的点与多边形的关系, 之前问过了就跳过

25匹马, 5个赛道, 选出最佳3匹马.

首先筛出15个局部前三. 后面卡住了, 提示前三存在额外信息. 还是卡住, 给了一个我自己都觉得好笑的错误解. 再提示, 第一名逐一对比. 坑坑洼洼答出来了, 第一名的组剩3, 必定确定第一个, 第二名组剩2, 第三名组剩1. 一共 5 + 1 + 1 = 7 次

• 数据结构熟悉吗? 你让我手撕红黑树撕不出来, 你要我撕什么线段树什么字典树我他妈用脚写(并没那么狂, 只是心里这样想的)

看起来是很熟悉, 然后跳过了

• 快排! 分析空间复杂度!

我了个大草! 根本没想到递归栈要分析. 感觉答的七零八落的, 一开始分析思路是每次一次交换比较就产生 O(1) 的空间复杂度, 然后判断交换次数, 完全蒙蔽应该是错的. 后来提示递归次数, 化了一个分治树的情况, 答 O(logN), 问是最佳还是期望. 我感觉是期望阿, 后来反应过来只有二分分布的时候左右递归栈才会平衡. 最差结果 O(n), 链表

其他

薪资: 感觉前面答的挺差的, 最好情况也就是中规中矩, 说了个总包20w, 本来想说base 20k的, 感觉别人很不耐烦, 我说完之后人家迅速确定了.

方向: 接受测试不? 不是很接受, 最好还是开发. 人家说测试岗里也有开发…哎, 强人所难

最终: 要求实习之后转正, 感觉偏向给了一个实习 offer 的意思? 只是口头保证大概率转正? 问了一下有关实习的事项.

总结

面试体验还行吧…算得上是很基础了, 不愧是招的许多开发都完全无计算机背景的公司呢. 面下来感觉自己确实基础很薄弱阿, 偏八股那边真的几乎为0, 现在微软也要问八股基础了. 本来觉得微软那边面试手撕算法我就去撕, 打死也不背八股的, 哎现在不知道什么情况.

给开发 offer 的话, 目前心中第二优先级吧. 微软那边本来是第一优先级的, 但是似乎两者有点冲突, 我又确实是不想背八股了, 算个第1.5优先级吧.

总之大方向上来看, 还是属于基础偏向薄弱了, 有点太注重”顶层设计”了? 之前微软模拟面的第一问归并排序我就有点离谱, 答不上来. 后面还是要多看看基础书, 操作系统+语言+网络都过一遍吧. 数据库这玩意儿嘛…实在是不想碰, 套一个 linux web-server 里面带的 SQL 操作就行了吧.