奥克兰腾讯光子工作室群 - 二面 - 面试总结

Table of contents

🧮 Part 1：最小生成树问题（MST）——Kruskal算法

题目简述

大山里有 N 个村落，人们通过长时间勘测，确定了 M 条道路的修建方案。每条道路连接且仅连接 2 个村落。请在这 M 个方案里，挑选适量的道路，使得挑选出来的方案建成后能让所有村落之间都能互相连通，且建设长度最小。

输入说明

第一行输入2个整数 N 和 M。 接下来 M 行，每行 X Y Z 共 3 个整数，代表第 i 个方案连通 X 和 Y 村，长度为 Z（村落从 0 开始编号）。

输出说明

如果所有道路都建设后也仍不能全部连通，输出 IMPOSSIBLE；否则输出建设的道路总长度。

解题思路分析

本题可以抽象为图的最小生成树（MST）问题，即：在一个无向加权图中，选择一些边，使得所有节点连通，且边的权值总和最小。

由于边的数量不一定形成连通图，我们还需考虑无法连通的情况。

我们选择使用 Kruskal 算法 来求解，核心思路如下：

1. 初始化：每个村落看作一个节点，所有道路看作无向边，边权为道路长度。

2. 贪心排序：将所有边按照权重从小到大排序。

3. 并查集辅助判断连通性：

   • 每次从小权重边开始尝试加入结果集中；
   • 使用并查集判断两个端点是否属于同一集合（是否已连通）；
   • 若不连通，则将这条边加入最小生成树，并合并两个集合。

4. 终止条件：

   • 成功加入 N-1 条边时（生成树的特性），算法结束，输出当前总权重；
   • 若遍历完所有边仍未连通所有节点（加入边数 < N-1），说明原图不连通，返回 IMPOSSIBLE。

Python 实现（Kruskal + Union-Find）

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 路径压缩
    return parent[x]

def union(parent, rank, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)
    if rootX == rootY:
        return False
    if rank[rootX] < rank[rootY]:
        parent[rootX] = rootY
    else:
        parent[rootY] = rootX
        if rank[rootX] == rank[rootY]:
            rank[rootX] += 1
    return True

def kruskal(N, edges):
    edges.sort(key=lambda x: x[2])  # 按照权重排序
    parent = [i for i in range(N)]
    rank = [0] * N

    total_weight = 0
    edge_count = 0

    for u, v, w in edges:
        if union(parent, rank, u, v):
            total_weight += w
            edge_count += 1
            if edge_count == N - 1:
                break

    return total_weight if edge_count == N - 1 else "IMPOSSIBLE"

# 读取输入
N, M = map(int, input().split())
edges = []
for _ in range(M):
    u, v, w = map(int, input().split())
    edges.append((u, v, w))

# 输出结果
print(kruskal(N, edges))

时间复杂度

• 排序：$O(M \log M)$
• 并查集操作：接近常数时间，整体近似 $O(M \log M)$

🔧 为什么 Python 不能使用多线程并行计算？

核心原因是 GIL（全局解释器锁）。GIL，全称是 Global Interpreter Lock（全局解释器锁），是 CPython（最常用的 Python 实现）中的一个机制。它的作用是：同一时间只允许一个线程执行 Python 字节码。

在 CPU 密集型任务 中（如：图像处理、大量计算、加密解密等），即使开了多个线程，由于 GIL 的存在，它们依然是轮流执行的，不是并行。

但对于 IO 密集型任务（如网络请求、文件读写等），Python 多线程仍然有意义，因为线程会在等待 IO 时释放 GIL，其他线程就可以继续执行。

解决方案 —— 多进程（multiprocessing）

为了实现真正的并行计算，Python 提供了 multiprocessing 模块，它通过多个进程来绕过 GIL。

• 每个进程都有自己的 Python 解释器和内存空间；
• 所以它们可以真正并行运行在多个 CPU 核心上；
• 适合处理 CPU 密集型任务。

🧠 线程 vs 进程

线程、进程定义

线程、进程核心区别

线程、进程相同点

如果是多进程模型，能否实现进程之间内存共享？

虽然多进程模型下每个进程的内存是隔离的，但操作系统提供了共享内存机制，可以让多个进程访问同一块物理内存。共享内存是最快的进程间通信方式，但需要借助同步原语避免数据冲突。这在高性能系统中非常常见，比如数据库、图像处理等场景。

⚖️ 在同一进程内多个线程共享资源时，操作系统或程序是如何解决资源冲突/同步问题的？

核心问题：多个线程共享内存时如何同步？

🔒 自旋锁实现原理？

自旋锁是一种忙等待（busy-wait）锁机制。它通过不断轮询一个共享变量（通常是原子变量）来判断锁是否可用，常使用 原子操作（如 CAS: compare-and-swap） 来实现加锁与解锁，从而避免线程上下文切换的开销，适合锁持有时间非常短的场景。

CAS = Compare-And-Swap：比较当前值与预期值，如果相等则替换为新值

bool CAS(addr, expected, new) {
    if (*addr == expected) {
        *addr = new;
        return true;
    } else {
        return false;
    }
}

为什么是原子的？

• 因为 CPU 提供了原子指令支持（如 x86 的 CMPXCHG）；
• 保证在执行过程中不会被中断、切换线程。

缺点

• ABA问题：值从 A→B→A，CAS 不知道其实变过；
• 自旋浪费 CPU：尤其在多核激烈竞争下；
• 一次只操作一个变量：不能原子更新多个内存块。

🎮 联机FPS游戏的传输层协议应该如何选用？

✅ UDP 为首选：低延迟、无连接，适合实时数据； ❌ TCP 会引入拥塞控制、队头阻塞，破坏游戏体验

如何保证 UDP 下重要数据不丢？

• 使用 应用层协议模拟可靠传输机制
  1. 为重要消息添加唯一编号（sequence ID）
  2. 发送后等待 ACK（确认）
  3. 超时未收到 ACK → 自动重发
  4. 收到重复包时进行“去重”
  5. 关键消息列表缓存机制

例子：玩家死亡事件

• 玩家死亡后发送一个 player_dead 消息（带 msg_id=555）；
• 服务端确认后回复一个 ACK 555；
• 客户端记录该消息已确认；
• 如果 ACK 没收到，客户端将在 300ms 后再次发送 msg_id=555；
• 服务端如果重复收到 msg_id=555，可丢弃或仅处理一次（幂等）。

📶 移动网络优化方案（高丢包场景）