刚刚结束一场 BCG X ds OA ，一小时内顺利完成。整体感受是：不难，但比纯算法题更考细节和工程习惯。 BCG 隔段时间就会换几套题的，题量大，难度还行，重要的是逻辑写清楚，边界处理好。我把每道题的思路拆开了，都贴在图片了，给大家一点参考。 现在很多北美大厂，题目都在往“细节密集 + 时间压缩”方向走。很多同学平时刷题没问题，但一到正式 OA 就节奏失控、边界漏掉、格式出错，最后差一点点。差的往往不是能力，而是临场稳定性。
Bcg X DS OA 新题分享
Q1：
题目：要求实现一个字符串压缩算法：从左到右扫描字符串，将连续相同的字符分组，如果某个字符只出现一次，则直接输出该字符；如果连续出现多次，则输出“字符 + 出现次数”。例如 "aabbccca" 压缩后为 "a2b2c3a"。字符串只包含小写字母，长度不超过 ，要求按顺序完成分组与拼接。
思路：从左到右扫一遍字符串，用一个计数器统计连续相同字符的个数，遇到新字符就把上一个字符和次数（大于 1 才加数字）拼到结果里即可。
代码：
def compressedString(message):
if not message:
return ""
p = message[0] # 当前字符
c = 1 # 当前字符计数
r = [] # 结果列表
for ch in message[1:]:
if ch == p:
c += 1
else:
# 如果计数大于1，拼接数字
r.append(p + (str(c) if c > 1 else ""))
p = ch
c = 1
# 处理最后一组
r.append(p + (str(c) if c > 1 else ""))
return "".join(r)Q2：
题目：一个由 n 个 pod 组成的系统，pod 之间通过若干连接形成多个连通区域（同一连通块视为同一“region”）。每个 pod 初始都有数据库连接；当某个 pod 失去连接后，它所在 region 内如果还有其他“活跃”pod，则数据会转发给该 region 中 ID 最小的活跃 pod；如果该 region 内已没有活跃 pod，则记录错误。需要处理两类查询：① 数据发送查询（判断最终数据写入哪个 pod，或返回 -1）；② 数据库连接失效查询（标记某 pod 失效）。最终对每个数据发送查询输出对应结果。本质是：在静态连通分量基础上，动态维护每个连通块中仍然活跃的最小编号节点。
思路：先用并查集把所有 pod 按连接关系分成若干个“区域”，然后对每个区域维护一个最小堆存活 pod 编号，查询时如果当前 pod 还活着就直接返回自己，否则就从对应区域里找还活着的最小编号，没有就返回 -1。
代码：
import heapq as hq
def recoverDeadPods(n, connections, queries):
# 并查集初始化
parent = list(range(n + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # 路径压缩
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
parent[rb] = ra
# 构建连通分量
for a, b in connections:
union(a, b)
# 每个连通块维护一个最小堆（存所有 pod）
heaps = {}
active = [True] * (n + 1)
for i in range(1, n + 1):
r = find(i)
if r not in heaps:
heaps[r] = []
hq.heappush(heaps[r], i)
result = []
# 处理查询
for t, p in queries:
if t == 2:
# pod 失效
active[p] = False
else:
# 数据发送查询
if active[p]:
result.append(p)
else:
r = find(p)
h = heaps.get(r, [])
# 弹出已失效的 pod
while h and not active[h[0]]:
hq.heappop(h)
if not h:
result.append(-1)
else:
result.append(h[0])
return resultQ3：
题目：给定 n 个节点，每对不同节点之间都可以选择“连接”或“不连接”，问一共可以构造出多少种不同的无向图配置。因为每一对节点是否连边是独立选择的，所以本质是统计所有可能的边组合数量，并对结果取模 。换句话说，需要计算在 n 个节点的无向图中所有可能的不同连边方式总数。
思路：n 个点之间一共有 n(n−1)/2 对可能的边，每条边只有“连或不连”两种状态，所以总方案数就是 2 的这些边数次方，最后用快速幂对 1e9+7 取模。
代码：
def countGraphs(n):
mod = 10**9 + 7
# 无向图中可选边的数量
edges = n * (n - 1) // 2
# 每条边都有“连”或“不连”两种选择
return pow(2, edges, mod)准备小结
如果你也在准备 Bcg X DS 或其他大厂的 OA／VO，可以直接联系 interviewAid 了解对应的面试辅助和陪跑支持。如果你想找我辅助面试，或者用 Bcg X DS 面经中的原题 mock，感受最真实的feedback，欢迎戳我。
全网唯一一家支持 L6 以上 system design mock，只放真实面经。
求职辅助服务，是关于时间和品质的较量。咨询interviewAid，获取最专业的Tech求职辅助。