Mar 28, 2026

上海量化私募C++开发实习笔试+面试复盘

约 12 分钟阅读

背景介绍

我在2026年3月9号申请了上海某中小型量化私募公司的C++开发工程师（实习生）岗位，流程如下：在3月14号收到了笔试试题，规定完成时间为3天。这是一个算法题，我估计难度约为Leetcode Hard级别。在3月19号我收到笔试通过的结果，并约定在3月24号进行一轮面试（技术面）。随后我收到了HR的通知：公司更期望得到全职开发的职员和考虑转正的实习生，虽然他们对我的表现比较认可，但是我的优先级被放低了，暂时没有收到第二轮面试（CEO面）的通知。以下是对本次经历的总结。

笔试部分

问题描述

在一条直线上有 $N$ 个农场，编号为 $1,2,\dots,N$ 。每个农场可选择生产 $0,1,2$ 个作物，最终需要正好 $1$ 单位作物。
在第 $i$ 个农场生产作物的单位成本为 $g_i$ 。在第 $i$ 个农场和第 $i+1$ 个农场之间，每运输 $1$ 单位作物的成本为 $d_i$ 。
求最小能满足需求的总成本。

思路分析

1.核心观察

设 $p_i$ 为第 $i$ 号农场生产作物量，其中 $p_i$ 只能取 $0,1,2$ 。由于每个农场刚好需要 $1$ 单位作物，可以定义对每个节点的“净盈余”： $a_i=p_i-1$ ，其中 $a_i$ 可以取 $-1,0,1$ 。

2. 运输成本与盈余的关系

在处理完前 $i$ 个农场后，假如没有恰好完成“自给自足”，则必须通过 $d_i$ 的路径流入或流出这些“盈余”。可以想象为某个截面，必须通过这个截面流入/流出才能实现平衡。因此，我们定义前缀盈余 $S_i$ ，含义为处理完前 $i$ 个农场后的盈余。注意： $S_i$ 可正可负。公式如下：

S_i=\sum_{j=1}^{i}a_j

3. 问题转化

总成本=生产成本+运输成本，其中生产成本为：

T\_Cost_\text{produce}=\sum_{i=0}^{N-1} p_i \cdot g_i

沿整条链的运输成本为：

T\_Cost_\text{transfer}=\sum_{i=0}^{N-1} |S_i| \cdot d_i

额外约束：对于第 $N$ 个节点， $S_N$ 必须为0。可以通过动态规划求解。

解法1：动态规划

1.状态定义

$dp[i][S]$ ：前 $i$ 个农场处理完后，当总净盈余为 $S$ 时的最小总成本。

2.状态转移

对于 $a_i \in \{-1,0,1\}$ ：

S_i=S_\text{i-1}+a_i

dp[i][S]=\min(dp[i][S],dp[i-1][S_\text{i-1}]+prod\_cost[i]+trans\_cost[i])

其中

prod\_cost[i]=p_i \cdot g_i

trans\_cost[i]=|S_{i-1}| \cdot d_{i-1}

3.状态边界

令 $dp[0][0]=0$ ，为了代码一致性补齐运输成本 $d_0=0$ 。最终答案存放在： $dp[N][0]$ 。

4.代码实现

solution（原始 HashMap DP，正确性基准）：

class solution {
public:
	vector<int> ma = { -1,0,1 };	// a = p-1，对应生产量 p=0/1/2
	long long minCost(int N, vector<int>& d, vector<int>& g)
	{
		// dp[i][S]：处理前 i 个农场、净盈余为 S 时的最小代价
		vector<unordered_map<int, long long>> dp(N + 1);
		dp[0][0] = 0;
		for (int i = 1; i <= N; i++) {
			for (auto it = dp[i - 1].begin(); it != dp[i - 1].end(); ++it) {
				int prev_S = it->first;
				long long prev_cost = it->second;
				for (int a : ma) {
					int S = prev_S + a;
					if (i == N && S != 0) continue;	// 最终盈余必须为 0
					int p = a + 1;
					// 代价 = 前状态代价 + 本农场生产代价 + 通过截面 i-1 的运输代价
					long long cand = prev_cost + 1LL * p * g[i - 1] + 1LL * abs(prev_S) * d[i - 1];
					auto it = dp[i].find(S);
					if (it == dp[i].end()) dp[i][S] = cand;
					else it->second = min(it->second, cand);
				}
			}
		}
		return dp[N][0];
	}
};

5.复杂度分析

时间复杂度： $O(N*3*S)=O(N^2)$ ，其中 $S$ 在每个结点不超过 $N$ 的规模。

空间复杂度： $O(N*S)=O(N^2)$ ，其中 $S$ 在每个结点不超过 $N$ 的规模。

6.代码优化与实现

经过思考，提出以下优化方向：

滚动数组压缩：将 $dp[i][S]$ 压缩为 $dp[S]$ ，其中 $S$ 的取值范围为 $[-N,N]$ 。这样可以将空间复杂度降低到 $O(N)$ 。
使用数组替代哈希表： $S$ 的取值范围为 $[-N,N]$ ，固定为一个大小为 $2N+1$ 的数组，以避免哈希表的计算。
dp剪枝：观察到前缀盈余 $S$ 不可能无限大，并且到达 $N$ 节点时， $S$ 必须“收敛”到 $0$ 。由于经过每个节点， $a_i\in\{-1,0,1\}$ ，所以对于第 $i$ 个节点， $S_i$ 必须在剩余的 $N-i$ 次变化中能够收敛到 $0$ 。综上所述，必须满足如下关系：

\forall i\in[0,N],\quad |S_i| \le \min\{N-i,i\}

代码实现（solution_refine，数组 DP + 有效范围剪枝）：

class solution_refine {
public:
	vector<int> ma = { -1,0,1 };
	long long minCost(int N, vector<int>& d, vector<int>& g)
	{
		// 用偏移 N 将盈余 S∈[-N,N] 映射到数组下标 [0,2N]
		vector<long long> dp(2 * N + 1, LLONG_MAX);
		vector<long long> dp_bak(2 * N + 1, LLONG_MAX);
		dp[N] = 0;	// 初始状态：S=0，代价=0

		for (int i = 1; i <= N; i++) {
			// 有效盈余范围：|S| <= min(i, N-i)，超出此范围无法在剩余步内归零
			int prev_range = min(i - 1, N - i + 1);
			int new_range  = min(i,     N - i);

			// 仅重置本步有效区间，避免全数组 fill
			fill(dp_bak.begin() + (N - new_range),
			     dp_bak.begin() + (N + new_range + 1),
			     LLONG_MAX);

			for (int prev_S = -prev_range; prev_S <= prev_range; prev_S++) {
				long long prev_cost = dp[prev_S + N];
				if (prev_cost == LLONG_MAX) continue;
				for (int a : ma) {
					int S = prev_S + a;
					if (abs(S) > new_range) continue;
					int p = a + 1;
					dp_bak[S + N] = min(dp_bak[S + N], prev_cost + 1LL * p * g[i - 1] + 1LL * abs(prev_S) * d[i - 1]);
				}
			}
			swap(dp, dp_bak);	// 滚动数组，避免重新分配内存
		}
		return dp[N];
	}
};

复杂度分析：

时间复杂度： $O(N*3*S)=O(N^2)$ ，但通过剪枝，有效 $S$ 范围更小，实际系数约为原版的一半。
空间复杂度： $O(N)$

7. 进一步常数优化

在 solution_refine 的基础上，solution_optimized 通过以下工程手段进一步降低常数因子约 30%∼50%：

提取公共子表达式：将三次转移共享的运输代价 $|S_\text{prev}| \cdot d_i$ 提取到内层循环外，每个 prev_S 只做一次乘法。
三路手动展开：将 for(int a : {-1,0,1}) 展开为三段独立代码块，消除内层循环开销和分支预测压力。
预计算生产代价：在进入 prev_S 循环前预计算 $g_i$ 、 $2g_i$ ，减少循环内乘法次数。

class solution_optimized {
public:
	long long minCost(int N, vector<int>& d, vector<int>& g)
	{
		vector<long long> dp(2 * N + 1, LLONG_MAX);
		vector<long long> dp_bak(2 * N + 1, LLONG_MAX);
		dp[N] = 0;

		for (int i = 1; i <= N; i++) {
			int prev_range = min(i - 1, N - i + 1);
			int new_range  = min(i,     N - i);

			fill(dp_bak.begin() + (N - new_range),
			     dp_bak.begin() + (N + new_range + 1),
			     LLONG_MAX);

			const long long gi    = (long long)g[i - 1];
			const long long di    = (long long)d[i - 1];
			const long long cost1 = gi;		// p=1 的生产代价
			const long long cost2 = 2 * gi;	// p=2 的生产代价

			for (int prev_S = -prev_range; prev_S <= prev_range; prev_S++) {
				const long long prev_cost = dp[prev_S + N];
				if (prev_cost == LLONG_MAX) continue;
				// 三次转移共享的运输代价，提取到循环外只算一次
				const long long base = prev_cost + (long long)abs(prev_S) * di;

			// 手动展开 a∈{-1,0,+1} 三路，消除内层循环开销
			// a = -1 (p=0，不生产)
			{
				int S = prev_S - 1;
				if (abs(S) <= new_range) {
					long long& ref = dp_bak[S + N];
					if (base < ref) ref = base;
				}
			}
			// a = 0  (p=1，生产 1 单位)
			{
				int S = prev_S;
				if (abs(S) <= new_range) {
					long long& ref = dp_bak[S + N];
					long long cand = base + cost1;
					if (cand < ref) ref = cand;
				}
			}
			// a = +1 (p=2，生产 2 单位)
			{
				int S = prev_S + 1;
				if (abs(S) <= new_range) {
					long long& ref = dp_bak[S + N];
					long long cand = base + cost2;
					if (cand < ref) ref = cand;
				}
			}
			}
			swap(dp, dp_bak);
		}
		return dp[N];
	}
};

复杂度分析：

时间复杂度： $O(N^2)$ ，系数约为 solution_refine 的 $2/3$ 。
空间复杂度： $O(N)$

总结与测试分析

本解答设计了动态规划算法，三个版本依次为：solution（HashMap DP，正确性基准）、solution_refine（数组 DP + 剪枝）、solution_optimized（三路展开 + 常数优化）。

提供以下测试案例供读者尝试：

//Format:
//N个农场
//d: N-1条边运输成本
//g: N个农场生产成本

//Example 1
4
1 2 3
100 100 1 1

//Example 2
3
100 100
1 2 3

//Example 3
2
3
1 5

经HR提示，算法中有两个需要注意的地方：

由于单个代价为int型，累加必须使用long long保证不会溢出。
我的算法在一个数据量最大的测试案例上超时，经过我分析，目前时间复杂度为 $O(N^2)$ 的算法无法在规定的时间内完成。该测试案例包括18W+的数据量，因文章篇幅限制不给出，若读者想通过所有测试用例，可能需要进一步思考 O(N log N) 或 O(N) 的优化方向（例如凸包优化、斜率优化或其他数学性质）

面试部分

面试官对待我比较轻松，主要询问了一些C++11的专业知识，关于项目没有太多过问。以下记录了一些我没有答上来的问题：

Q: STL中vector的底层实现，包含哪些成员函数？

Ans: 如果按接近标准库实现来讲，一个 std::vector 本质上就是一段连续内存的轻量封装，核心通常只需要三个指针（或等价的三个成员）：

指向当前数据起始位置的指针（begin）
指向当前已使用元素末尾的指针（end）
指向已分配容量末尾的指针（end_cap）也就是说，它通过 $[begin, end)$ 表示已存元素，通过 $[begin, end\_cap)$ 表示整个已分配的连续空间。这样设计的好处是： $size = end - begin$ ， $capacity = end_cap - begin$ ，所有操作都可以通过指针运算高效完成，同时保证数据连续，支持随机访问。

Q: STL中vector单次 `push_back()` 触发扩容的复杂度是 $O(N)$ ，那么是如何做到平均每次扩容的复杂度是 $O(1)$ 的？

Ans: 因为std::vector每次扩容一般是将总长度扩容为1.5-2倍，以2倍为例，假设最后一次扩容时长度为 $N$ ，则总开销为 $1+2+4+\cdots+N\approx2N$ 由于此时一共从空串push_back()了 $N$ 次，所以平均每次的代价是 $O(1)$ 。

Q: 假如用一个基类指针操作派生类，为什么必须要给基类析构函数设计虚函数？

Ans: 因为运行时多态中，这种场景下，当基类指针析构时，如果基类析构函数设计了虚函数，则会根据先根据虚函数表调用派生类析构函数，再调用基类析构函数。如果没有设计虚函数，则只会调用基类的析构函数，导致错误的资源释放。这个问题实际上是利用虚函数的机制保证析构环节的安全性。

Q: 函数返回一个大的 `std::vector` 时，直接 `return v;` 和 `return std::move(v);` 在性能上是否有差别？

Ans: 首先，结论是没有差别，甚至会更差。这是因为C++编译器会使用返回值优化(RVO/NRVO)，在这种优化中，会直接在返回值的内存处构造将要返回的对象，这样优化后没有拷贝和移动的开销。但如果你写成 return std::move(v);，你把 v 强制转成右值，反而可能阻止 NRVO，编译器就必须走移动构造。这虽然比拷贝便宜，但仍然不是 0 成本（需要搬指针、置空原对象等）。所以实际情况是三种：

return v;：理想情况 → NRVO，0 开销
return v;：没触发 NRVO → 走移动构造（C++11 起有保证）
return std::move(v);：通常 → 一定走移动构造，可能错过 NRVO 因此工程上的建议很明确：返回局部变量时不要手动 std::move，让编译器自己优化。

反问问题中，我询问了以下问题：

公司的部门和业务。
希望实习生从事何种工作，能否给一些具体的示例？
实习生对接的leader是谁？是否有code review流程？
开放问题：询问面试官对于我面试表现和学习的建议。

经验总结

小公司中HR跟求职者1对1交流的机会更多，和HR谦虚友好地交流，通常能获得更紧密的交流。
笔试题如果给了几天做，在有余力的情况下，还是多钻研下不同方法和优化，把文档写漂亮点，给人好印象。
有的C++知识不清楚，也可以尽量根据知道的说一说，讲一讲自己的分析和推断。
来自面试官：答不出一些专业问题是正常的，他设计这些问题就没指望面试者能全答出来。如果都答出来了，他反而可能怀疑面试者作弊了。