Skip to content
Go back

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

Published:  at  04:09 PM

Table of contents

Open 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))

时间复杂度


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

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

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

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

解决方案 —— 多进程(multiprocessing)

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


🧠 线程 vs 进程

线程、进程定义

名称概念说明
进程(Process)操作系统分配资源的最小单位。一个进程包含代码、数据、内存、打开的文件等,是一个完整的程序运行实例
线程(Thread)CPU 调度执行的最小单位。一个进程中可以包含多个线程,它们共享该进程的资源(如内存、文件描述符等)。

线程、进程核心区别

对比维度线程进程
资源隔离同一进程内多个线程共享资源(内存空间等)不同进程资源互相隔离
开销大小创建和销毁开销小,切换速度快创建和切换的开销大
通信方式直接共享内存,通信快,但容易出错通过进程间通信(如管道、队列),通信复杂但更安全
稳定性某个线程崩溃可能影响整个进程一个进程崩溃不会影响其他进程
并行性受 GIL 限制(在 CPython 中不能并行)每个进程有独立解释器,可并行运行

线程、进程相同点

相同点说明
都是并发编程模型都可用于提高程序运行效率,利用多核资源
都由操作系统调度无论线程还是进程,最终都要被 CPU 执行
都有创建、销毁、切换的生命周期系统会分配时间片和处理上下文切换
都可被阻塞、唤醒如等待 IO、信号等

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

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

方法说明
共享内存(shmget)映射物理内存至多个进程地址空间
mmap 文件映射利用磁盘文件映射为共享内存区域
管道、队列等 IPC不共享内存,但能通信

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

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

同步机制特点/使用场景
互斥锁(mutex)最常见,适合保护单个资源
信号量(semaphore)控制并发数量,如线程池或连接池
条件变量(condition)等待特定状态,适合生产者消费者模型
自旋锁(spinlock)忙等待,不适合耗时长的锁定

🔒 自旋锁实现原理?

自旋锁是一种忙等待(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;
    }
}

为什么是原子的?


缺点


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

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


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

例子:玩家死亡事件


📶 移动网络优化方案(高丢包场景)

技术点说明
冗余包发送关键消息重复发送几次,提升成功率
客户端预测临时“假象”动作,服务器回正
差分压缩只发送变更部分,减少带宽
关键帧机制每隔 N 帧全量发一次状态包,防丢包恢复
自适应重传根据 RTT 和丢包动态调节超时和重试频率
FEC 纠错码多发校验信息,少数包丢失也能恢复数据


Suggest Changes

Previous Post
奥克兰腾讯光子工作室群 - 三面 - 面试总结
Next Post
GREEDY ALGORITHMS II