BCG X OA 使用 HackerRank 平台，时长 90 分钟，题型构成相对固定：20–25 道 MCQ（涵盖 SQL、Python/Pandas、基础统计和商业逻辑） + 2 道 Coding / Data Analysis 题（一道偏业务分析，一道偏代码实现）。整体难度中等，但时间压力较大，尤其需要同时兼顾准确率和编码效率。
和传统互联网公司的纯算法 OA 不同，BCG X 更注重“数据 + 业务”的结合，考察你能否用数据工具快速解决实际业务问题。
题目 1：字符串压缩算法
題目描述
为减少互联网传输的消息大小，某压缩算法会对字符串中连续重复的字符进行编码。
你的任务是按照以下规则压缩给定字符串：
- 从左到右扫描字符串，将连续相同的字符分为一组。
- 如果某个字符仅出现一次，则直接将该字符添加到输出结果中。
- 如果某个字符连续出现多次，则将字符和它的连续出现次数拼接后，添加到输出结果中。
示例：
输入字符串 message = "aabbccca"
输出结果："a2b2c3a"
約束條件：
- 字符串中的所有字符均为小写字母
a-z。 - 字符串长度 ≤ 10⁵。
解題思路
- 遍历字符串，用变量记录当前字符和连续计数。
- 遇到不同字符时，按规则拼接结果并重置计数。
- 最后一组字符也需要单独处理。
Python 实现
def compress_string(message: str) -> str:
if not message:
return ""
result = []
current_char = message[0]
count = 1
for char in message[1:]:
if char == current_char:
count += 1
else:
result.append(current_char)
if count > 1:
result.append(str(count))
current_char = char
count = 1
# 处理最后一组字符
result.append(current_char)
if count > 1:
result.append(str(count))
return "".join(result)
# 测试
print(compress_string("aabbccca")) # 输出: a2b2c3a
题目 2：服务 Pods 与数据库查询
題目描述
一个系统有 n 个服务 Pod，编号为 1 到 n，通过 m 条链路互联（由数组 connections 表示）。直接或间接相连的 Pod 属于同一个区域。
每个 Pod 都有数据库连接。当一个 Pod 的连接失效时，该区域的所有流量会自动转发到该区域内ID 最小的正常 Pod；如果区域内没有正常 Pod，则无法写入数据。
处理 q 个查询，分为两类：
- 数据发送查询：
"1 pod_id"→ 向该 Pod 发送数据，返回最终写入数据的 Pod ID（或 – 1）。 - 数据库连接失效查询：
"2 pod_id"→ 标记该 Pod 为失效状态。
返回一个数组，包含所有数据发送查询的结果。
示例：
n = 3m = 2connections = [[1, 2], [2, 3]]queries = [[2, 2], [1, 2], [2, 1], [2, 3], [1, 1]]
過程：
- Pod 2 失效。
- 向 Pod 2 发送数据，转发到区域内 ID 最小的正常 Pod（1），结果为 1。
- Pod 1 失效。
- Pod 3 失效。
- 向 Pod 1 发送数据，区域内无正常 Pod，结果为 – 1。
返回：[1, -1]
解題思路
- 先用并查集（Union-Find）预处理每个 Pod 所在的连通区域，记录每个区域的最小 ID。
- 维护每个 Pod 的状态（正常 / 失效）。
- 处理查询时，根据区域和状态返回结果。
Python 实现
class DSU:
def __init__(self, size):
self.parent = list(range(size + 1))
self.min_id = list(range(size + 1)) # 每个集合的最小ID
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
xr, yr = self.find(x), self.find(y)
if xr == yr:
return
if xr < yr:
self.parent[yr] = xr
self.min_id[xr] = min(self.min_id[xr], self.min_id[yr])
else:
self.parent[xr] = yr
self.min_id[yr] = min(self.min_id[yr], self.min_id[xr])
def pod_queries(n, m, connections, queries):
dsu = DSU(n)
for u, v in connections:
dsu.union(u, v)
active = [True] * (n + 1)
result = []
for query in queries:
t, pod_id = query
if t == 2:
active[pod_id] = False
else:
root = dsu.find(pod_id)
min_active = -1
# 找区域内最小的正常Pod
for i in range(1, n + 1):
if dsu.find(i) == root and active[i]:
min_active = i
break
result.append(min_active)
return result
# 测试
print(pod_queries(3, 2, [[1, 2], [2, 3]], [[2, 2], [1, 2], [2, 1], [2, 3], [1, 1]]))
# 输出: [1, -1]
题目 3：图的不同构型数量
題目描述
給定 n 个节点，每个不同的节点对之间可以选择连边或不连边（无自环、无重边）。求所有可能的不同构型的无向图总数，结果对 10⁹ + 7 取模。
示例 1：n = 3
节点间共有 C(3,2) = 3 条可能的边，每条边可选 / 不选，总共有 2³ = 8 种不同构型，因此返回 8。
示例 2：n = 4
节点间共有 C(4,2) = 6 条可能的边，总共有 2⁶ = 64 种不同构型。
解題思路
- 无向图中，n 个节点的无向边总数为组合数
C(n, 2) = n*(n-1)/2。 - 每条边有两种状态（存在 / 不存在），因此总构型数为
2^(n*(n-1)/2) mod (10⁹+7)。
Python 实现
MOD = 10**9 + 7
def count_graph_configurations(n: int) -> int:
if n < 2:
return 1 # 0或1个节点时，只有1种构型
edges = n * (n - 1) // 2
return pow(2, edges, MOD)
# 测试
print(count_graph_configurations(3)) # 输出: 8
print(count_graph_configurations(4)) # 输出: 64题目 4：字符串解压算法
題目描述
为还原被压缩的互联网传输消息，需实现对应的字符串解压算法，解压规则与题目 1 的压缩规则反向对应，具体要求如下：
- 扫描字符串，识别字符与紧跟的连续数字（数字仅表示当前字符的连续出现次数，且为正整数）。
- 若字符后无数字，说明该字符仅出现 1 次，直接保留到输出结果中。
- 若字符后有数字，说明该字符连续出现该数字次，将字符重复对应次数后拼接至输出结果中。
- 输入字符串仅包含小写字母
a-z和数字0-9，且数字仅紧跟在对应字符后出现，无无效格式。
示例
示例 1
输入字符串："a2b2c3a"
输出结果："aabbccca"
示例 2
输入字符串："x5y3z"
输出结果："xxxxxyyyzz"
約束條件
- 输入字符串长度 ≤ 10⁵
- 数字范围为 1 ≤ 数字 ≤ 1000
- 字符与数字的对应关系合法，无单独数字、无连续数字等非法格式
Python 实现
def decompress_string(s: str) -> str:
if not s:
return ""
result = []
n = len(s)
i = 0
while i < n:
# 提取当前字符（一定是小写字母）
char = s[i]
i += 1
# 提取连续的数字（可能多位）
count_str = ""
while i < n and s[i].isdigit():
count_str += s[i]
i += 1
# 确定重复次数（无数字则为1）
count = int(count_str) if count_str else 1
# 拼接重复后的字符
result.append(char * count)
return "".join(result)
# 测试示例
print(decompress_string("a2b2c3a")) # 输出: aabbccca
print(decompress_string("x5y3z")) # 输出: xxxxxyyyzz
print(decompress_string("ab2c3d")) # 输出: abbccc d
解題思路
- 双指针遍历：用指针
i遍历字符串，先提取当前字符，再提取紧跟的数字（处理多位数字情况）。 - 规则匹配：无数字则计数为 1，有数字则转换为整数作为重复次数。
- 结果拼接：将字符按计数重复后加入结果列表，最终拼接列表得到解压字符串。
- 效率优化：使用列表存储结果（避免字符串拼接的性能损耗），单遍遍历时间复杂度为 O(n)，空间复杂度为 O(n)（存储结果），满足长度≤10⁵的约束要求。
寫在最後
以上就是我这次 BCG X DS OA 的真实题目分享和备战心得。
如果你正在准备 BCG X、QuantumBlack 或其他咨询公司的 Data Science / Analyst OA，感觉 SQL、Pandas 或时间管理方面压力比较大，可以了解一下 Programhelp 的服务，支持 HackerRank、牛客网、CodeSignal 等平台，提供 OA 代写和辅助，确保所有测试用例通过，不通过不收费，操作也比较安全。
有需要的同学可以自己去了解一下。感谢阅读，祝大家早日通过 OA，拿到满意的 Offer！
