2024 文远知行后端开发实习面经

type

status

date

slug

summary

2024 文远知行暑期实习面试

📎一面（2024.3.4，已通过）

自我介绍

讲最近一段实习项目，挖了一点，甚至没挖到我准备的很难的地方

Golang

讲解goroutine 的 GMP模型

为什呢需要多一个P，直接全局goroutine队列不行吗（全局锁，影响并发性能）

有一个goroutine一直持有锁循环等待要怎么办（channel 信号）

只有一个锁，能否造成死锁？（可重入锁）

Answer

假设有一个场景，其中只涉及一个可重入锁（锁L）和一个共享资源（资源R1）。我们考虑以下情况：

线程A 持有锁L 并且在操作 资源R1。

线程B 也想操作 资源R1，但由于 线程A 正在操作，所以 线程B 需要等待 线程A 完成。

此时，线程A 在完成操作前需要执行一些其他任务，而这些任务需要等待 线程B 完成一些工作。

此时导致了死锁情况

GC的原理（三色标记法+写屏障）

C++

智能指针有哪些(auto_ptr, unique_ptr, share_ptr, weak_ptr)

unique_ptr有release，但share_ptr没有，为什么？

Answer

unique_ptr：unique_ptr 表示对其所指向对象的唯一所有权。这意味着没有两个 unique_ptr 实例可以同时指向同一个对象。因此，当 unique_ptr 被销毁时，它所指向的对象也会被自动删除。release 方法是 unique_ptr 的一部分，它用于释放对对象的所有权，但不销毁对象本身。调用 release 会导致 unique_ptr 丧失对对象的所有权，因此它不再负责该对象的生命周期。这在转移所有权时非常有用，比如当你需要将一个对象的所有权从一个 unique_ptr 转移到另一个 unique_ptr 时。

shared_ptr：与 unique_ptr 不同，shared_ptr 允许多个 shared_ptr 实例共享对同一个对象的所有权。这是通过引用计数机制实现的，即每个 shared_ptr 都维护一个计数，表示有多少个 shared_ptr 实例共享同一个对象。当最后一个这样的 shared_ptr 被销毁时，或者被赋予新值时，它所指向的对象才会被销毁。因此，shared_ptr 没有 release 方法，因为单个 shared_ptr 不能单方面放弃对对象的所有权而不影响其他共享该对象的 shared_ptr 实例。如果 shared_ptr 有 release 方法，它可能会破坏对象的安全删除和资源管理，导致悬挂指针或资源泄露。

template模板（直接答不会，说没关系因为我没有C++项目）

计网

说什么TCP和UDP区别我肯定知道，直接不问了笑死

TCP连接中有一步TLS握手，讲解一下（ssl，https加密过程，对称加密和非对称加密）

密码学

看我web3做的多，刚刚对称加密和非对称加密讲的头头是道，面试官说他对密码学有研究（但我不会啊。。。），想问问，直接给我整裂了

RSA的加密过程（不会）

Answer

RSA加密算法是一种非对称加密算法，由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年提出的。它是第一个能同时用于加密和数字签名的算法。RSA的名字就是取自这三位发明者的姓氏首字母。

RSA算法的核心思想基于一个数学事实：将两个大质数相乘很容易，但要将它们的乘积分解回原来的两个质数却极其困难。这个特性是RSA算法安全性的基础。

RSA加密算法的主要步骤包括：

生成密钥：

选择两个大的质数和，计算它们的乘积。的长度，即它的位数，是密钥的长度。

计算欧拉函数。

选择一个整数，满足，且与互质。通常，被选为65537，因为它既不太大也不太小，还可以加快加密过程。

计算关于的模逆元。即找到一个整数，使得除以的余数为1。

公钥为，私钥为。

加密过程：

假设有一个明文消息，将其转换为一个整数，使得。

加密后的消息计算为。

解密过程：

使用私钥来解密消息。解密后的消息计算为。

RSA算法的安全性依赖于大数分解的难度。随着计算能力的增强和量子计算的发展，RSA算法需要使用越来越长的密钥才能保持安全。当前，常用的密钥长度通常是2048位或更长。

算法题

给定一个数组，把它切分为3个部分，small, mid, big，保证sum_small < sum_mid < sum_big，询问有多少种划分方法？ n = arr.size(), 3 < n < 1e6 0 < arr[i] < 1e9 整个数组的和 sum(arr) < 1e9

先讲解了思路，再写

求前缀和

采用滑动窗口的思想，但是需要固定住left指针: for(int left = 0; left < n; left ++) ......

通过判断pre[right] - pre[left] > pre[left] - pre[0]，二分法求出right指针的位置

right只能向后移动，移动到sum_big <= sum_mid即可停止，移动过程中计数，即可得到最终结果

📎二面（2024.3.11，被拒）

感觉就是kpi面，面试官全程就没用心在问问题。。。最后还丢了一道困难题出来

问的七零八碎贼奇怪。。。

自我介绍，然后问了比较多的项目，让我甚至以为这不会已经是easy的主管面了吧hhh，结果下面有点点被拷打

分布式

你说你对分布式有了解，你可以讲讲任何有关分布式之类的信息吗？（主从复制，数据强一致，Raft）

用过k8s吗？（没用过）

Golang

往slice里面append数据是线程安全的吗？（没答好，只答了不是线程安全，然后扯到加锁balabala）

Answer

Golang 的 slice 本身是不安全的数据结构,在并发情况下访问需要额外的同步机制。具体来说:

读写不安全

同时有多个并发的读写操作,会导致数据竞争(data race)的发生,从而导致程序行为不确定。

append 操作不安全

append 可能会导致重新分配内存,从而使其他并发读写访问的 slice 指向的内存地址发生变化,这也会造成数据竞争问题。

len 操作安全,cap 操作安全

对 slice 进行 len 和 cap 操作只是读取 slice 的元数据,不会影响底层数组,所以这两个操作是并发安全的。

因此,在并发编程中,如果需要使用 slice,需要使用诸如互斥锁(mutex)等同步机制来保护共享的 slice 不会被并发修改。此外,Go 语言中也提供了并发安全的线程安全的队列(sync.Pool)、环形队列(ring)等数据结构可以使用。

在你项目中，有因为线程并发出现过重大问题吗？可以讲一下（其实没有。。。）

深度学习 & Python

你做过完整的深度学习项目对吧，主要用了哪些框架？

python里面有支持多线程的库吗？（py不熟，说不太清楚，但肯定有能实现用户级线程的库）

操作系统

你用过多卡训练，如果多张GPU一起执行并行运算，是开一个进程还是多个进程？

Answer

在多GPU并行训练场景下,通常是采用单进程多线程的方式进行运算。具体来说:

开启单个主进程

主进程负责加载模型,准备数据,调度任务等。

为每张GPU创建一个线程

每个线程负责在对应的GPU上完成正向传播、反向传播以及梯度更新等运算。

线程之间通过显存或者内存进行通信,实现梯度同步。

数据并行

常见的做法是采用数据并行的方式。

将训练数据等分成多份,分别传递给不同线程的GPU进行训练。

在每个batch/epoch结束时,线程之间会进行梯度同步。

使用单进程多线程模式的主要优点是:

避免了进程间通信的开销。

方便梯度的同步和聚合。

方便主进程监控训练状态。

而启动多个进程会增加通信、同步和管理的复杂度。

不过,也有少部分场景可能会使用多进程,如果模型非常大,单个进程无法驱动所有GPU时。但通常情况下,业界趋向于使用单进程多线程的并行方式进行多GPU训练。

堆和栈的关系

讲一下cpu和gpu的存储区别？（根本没碰过gpu，只回答了cpu cache）

C++

new和malloc的关系？（答反了，神经。。。new是操作符，malloc是函数）

malloc一次申请任意内存都可以吗？我申请1 bit可以吗？

Answer

C++中的malloc函数申请内存时需要遵守一定的规则和限制,具体如下:

申请大小限制 malloc函数通常是按照字节来分配内存的,最小可申请1个字节。malloc(1)可以申请1个字节,但是malloc(0)一般是非法的,因为分配0字节没有实际意义。

不能申请单个bit 不能直接通过malloc申请单个bit,因为内存分配的最小单位是字节(byte)。所以malloc(0.125)是非法的,因为0.125表示1个bit。

申请内存上限 malloc申请内存大小有一定上限,通常是当前系统可用虚拟内存的大小。如果申请过大,可能会导致内存不足或段错误。

对齐限制 大多数系统要求分配的内存地址是某个数值(通常是4或8)的整数倍。也就是说,返回的指针地址值最低有效位可能会被覆盖以满足对齐要求。

整数倍 即使申请了奇数个字节的内存,大多数malloc实现也会向上舍入为最接近的2的幂次方的倍数。比如申请5字节,实际可能分配8字节。

所以在实践中,我们一般会申请适当大小的内存,避免过小或过大,并且使用free适当释放。C++11后也可以使用更安全的智能指针等RAII机制来自动管理资源。

Git

讲一下git rebase和git merge?

Answer

git rebase 和 git merge 都是用来合并分支的命令,但是它们的工作方式和结果有所不同。

git rebase:

作用是将一个分支的修改按序移植到另一个分支上。

过程是先暂存当前分支的提交,然后将目标分支上的修改临时保存为补丁,回到希望重新应用修改的地方,依次应用每个提交,最后将暂存的提交应用回来。

产生的结果是一个新的整洁的线性历史分支,没有多余的合并提交记录。

优点是保持提交历史的整洁,缺点是本质上是"rewrite history",如果分支已推送给他人,会导致分支需要强制推送。

git merge:

作用是将一个分支合并进另一个分支。

过程是直接将两个分支的最新快照合并起来。

产生的结果是一个新的合并提交(merge commit),记录了各分支合并的历史。

优点是合并来源分支的历史完全保留,缺点是引入了新的合并提交记录。

一般来说:

如果是自己的本地分支,使用 rebase 可以获得一个整洁易读的线性提交历史。

如果涉及共享分支,或者需要保留完整的提交历史,建议使用 merge 命令。

git rebase 更改提交历史,如果使用不当可能会给协作者带来麻烦,所以使用时需格外小心。相比之下,git merge 更保守一些,也更容易理解和使用。

git reset呢？

Answer

git reset:

作用: 撤销或移除已缓存(staged)和提交的更改。

分类:

git reset --soft 只撤销 commit,不会修改工作区代码
git reset --mixed(默认) 撤销 commit 并撤销 git add 操作
git reset --hard 彻底撤销,工作区代码也被修改

使用场景: 本地提交时发现错误需要撤回,或者想回到之前的某次提交状态。

危险性: -hard选项会直接修改工作区,导致代码丢失,所以通常配合使用 reflog 来恢复。

一共就问了30分钟，然后开始写算法题

算法题（给我出英文题面。。。）

现在需要实现这样一个Solution类，初始化n和blacklists，blacklists为黑名单，需要实现一个pick方法，用于生成一个0 - n-1的数字，同时这个数字不能出现在黑名单blacklists里面，并且要求不在黑名单里面的数字出现的概率是一样的

数据范围:

示例输入：

示例输出：

解释：

很明显可以输出的数字只有[0,1,5,6]，并且需要等概率出现，也就是每一个数字出现的概率为

一开始直接讲了两种方法来实现这个问题:

发牌算法

可以把除了黑名单之外的所有数字全部都放到一个set st里面，然后直接用rand() % st.size()去取数字就可以了，但被面试官否了，他说如果n太大，但balcklists里面没几个数字，st会因为放太多数字而爆内存

随机数生成法（代码成功实现）

给到经典公式（不过这次用不上）

比如Rand25= 5( Rand5()-1 ) + Rand5()可以生成1到25之间的随机数。我们可以只要1到21（3*7）之间的数字，所以可以这么写

C++ 的 rand()函数会生成一个数字

如果n较小，我可以直接调用rand() % n来获得随机数，在n比较小的情况下几乎是等概率；

如果n较大，那么只要rand()生成了一个比n大的数就舍弃，一直重新生成直到生成符合条件的数字就返回

随机数生成法比较常规，他说ok实现一下，最后也是完整敲出来了，然后他又提出了一个问题：

n = 99999999, blacklists内的数据为[1 - 99999997]，上面这个算法就会非常耗时，可能要很久才能输出结果，要怎么解决？

还没来得及想，他就说没关系下去想一下，面试时间到了，前面的方法已经写完可以输出正确结果就ok了。。。。。。

正解：

力扣 710 黑名单中的随机数（困难）

无语啦，给我出困难题 😇