多益网络游戏服务器端开发工程师校招笔试题

面试题目

一、选择题（22道）

知识点涵盖数据结构基础，包括：

• 队列（Queue）
• 栈（Stack）
• 树（Tree）

二、简答题（4道）

1. 多线程与多进程的区别
2. Chrome 浏览器采用多进程架构的优点
3. 用两个栈模拟实现一个队列
4. （另外两题作者未记录）

三、编程题（1道）

给定一个 4×4 的二维数组 arr[4][4]，满足以下性质：

• 每行从左到右递增
• 每列从上到下递增

输入一个目标数，用最简洁的方式判断该数是否存在于数组中。

---

参考解析

多线程 vs 多进程

• 进程是资源分配的基本单位，线程是 CPU 调度的基本单位。
• 多线程共享同一进程的内存空间，通信开销小，但线程崩溃可能影响整个进程。
• 多进程相互独立，稳定性更高，但进程间通信（IPC）开销较大。
• 创建线程比创建进程代价小，上下文切换也更快。

Chrome 使用多进程架构的优点

• 稳定性：每个标签页或插件运行在独立进程中，单个页面崩溃不影响其他页面。
• 安全性：进程间相互隔离，沙箱机制可限制恶意网页的权限。
• 性能：可充分利用多核 CPU，各进程并行运行。
• 代价是内存占用较高（每个进程有独立的内存空间）。

两个栈模拟队列

• 使用 stack_in 负责入队，stack_out 负责出队。
• 入队：直接 push 到 stack_in。
• 出队：若 stack_out 为空，则将 stack_in 所有元素依次弹出并压入 stack_out，再从 stack_out pop；若 stack_out 不为空，直接 pop。
• 均摊时间复杂度 O(1)。

有序二维数组查找（编程题）

采用右上角（或左下角）起点搜索法，时间复杂度 O(m+n)：

bool findInMatrix(int arr[4][4], int target) {
    int row = 0, col = 3; // 从右上角出发
    while (row < 4 && col >= 0) {
        if (arr[row][col] == target) return true;
        else if (arr[row][col] > target) col--; // 当前值偏大，左移
        else row++;                              // 当前值偏小，下移
    }
    return false;
}

• 每次比较可排除一行或一列，最多 m+n 次比较即可得出结论。
• 暴力枚举为 O(m×n)，本方法是最优解。