# 计算机科学面试题：先讲清假设，再写算法

> 5 道原创计算机科学面试题，覆盖算法复杂度、数据结构、递归、二分查找与数据表示。每题给出面试官视角的考点、分步思路和常见追问，帮助你把思路讲清楚。所有题目均为原创练习。练的时候先给朴素解，标出复杂度，再找反例并优化一档，每一步都说出来。适合录音复盘与限时模拟，也适合同学互练。每题都可单独使用。

[本页排版版本](https://www.frontiervue.com/zh/interviews/questions/computer-science)

计算机科学面试不只看你会不会写代码。面试官更想知道你能否判断一个方案为什么可行、代价在哪里、边界情况是什么。下面 5 道题都是**原创练习**，题面用英文给出，附中文译文；每题的思路都强调「先说假设，再说做法」。

## 先说结论
- 先问清楚输入规模与限制，再决定用什么算法。
- 能说出时间与空间复杂度，比写出漂亮代码更加分。
- 主动给一个反例，证明你知道方案会在哪里失效。

### 计算机科学面试速览

| 项目 | 数值 |
| --- | --- |
| 常见形式 | 口头设计，逐步加条件 |
| 题目类型 | 算法、数据结构、边界 |
| 重点 | 假设、复杂度、正确性 |
| 准备方式 | 每题说出代价与反例 |

> 面试可能要求你在纸上或共享白板上写伪代码，先把输入输出和边界说清楚。

> 面试形式：面试通常围绕一道题逐步加条件：先让你给一个朴素做法，再问能不能更快，最后问如果输入变大或存储受限会怎样。写不写代码因学校而异，但口头解释复杂度几乎是必考。

## 目录
1. 计算机科学面试在考什么
2. 怎样用这 5 道题练习

## 1. 计算机科学面试在考什么

面试官通常不期待你直接写出最优解。他们更常从一个小例子开始，让你描述一个笨办法，然后逐步追问：如果数据量变成一百万呢？如果只能顺序读取呢？如果内存放不下呢？

所以真正的考点是「把问题形式化」：输入是什么、输出是什么、允许哪些操作、最坏情况是什么。把这些说清楚，算法往往自己就出来了。

> 一个万能开场：**「我先假设输入是……，如果这个假设不成立，做法会变成……」** 面试官很看重你是否意识到假设的存在。

## 2. 怎样用这 5 道题练习

1. **先给朴素解**
不要一上来追求最优。先说一个肯定正确的做法，再分析它慢在哪里。

2. **标出复杂度** (必答)
对每一步说明时间与空间代价，并指出哪一项会先成为瓶颈。

3. **找一个反例**
空输入、重复元素、已经有序、极端大或极端小，至少试两个。

4. **再优化一档**
通常只需要换一个数据结构或利用一个不变量，不必推翻重来。

## 计算机科学面试题：5 道原创练习

下面每道题都是本站原创练习，不是往年真题。先读题、出声做一遍，再对照思路找自己的断点。

### 第 1 题

**问：** You have a sorted list of one million integers. To decide whether a value is present, how many comparisons does binary search need at most? What changes if the list is stored as a linked list?

**译文：** 你有一个排好序的一百万个整数。要判断某个值是否存在，二分查找最多需要比较多少次？如果这些数存在链表里，会有什么变化？

**这道题在考什么：** 考对数复杂度与数据结构前提。很多人会背 O(log n)，却说不清二分查找依赖「随机访问」这个隐藏假设。

**可以这样往下想：**
1. 因为 2²⁰ = 1,048,576，超过一百万，所以最多约 20 次比较。
2. 链表不能 O(1) 找到中点。每次取中点都要从头走，单次就是 O(n)，二分退化成 O(n) 甚至更慢。
3. 替代方案：先转成数组，或使用平衡树、跳表等支持有序查找的结构。要说明额外空间与预处理成本。

**面试官可能追问：** If the data sits on a hard drive and is read in blocks, is binary search still the right choice?

**译文：** 如果数据在硬盘上、按块读取，二分查找还合适吗？

### 第 2 题

**问：** Describe an algorithm that finds the first character that appears twice in a string. What are its time and space complexity? How would you test it?

**译文：** 描述一个算法，找出字符串中第一个重复出现的字符。它的时间与空间复杂度是多少？你会怎么测试它？

**这道题在考什么：** 考哈希表的使用与边界情况。题目简单，但「第一个」和「重复」都需要精确定义，测试设计能看出工程习惯。

**可以这样往下想：**
1. 从左到右扫描，用集合记录见过的字符。遇到已在集合里的字符就返回它，否则加入集合。
2. 时间是 O(n)，空间是 O(k)，k 是字符集大小；对固定字母表可以视为 O(1)。
3. 测试：空串、没有重复、首字符重复、末字符重复、大小写不同、Unicode。先明确「重复」是否区分大小写。

**面试官可能追问：** If the string contains only 26 lowercase letters, can you do it with O(1) extra space?

**译文：** 如果只含 26 个小写字母，能不能用 O(1) 额外空间？

### 第 3 题

**问：** What does this function compute? `f(n) = 1` when `n = 0`, otherwise `f(n) = n × f(n − 1)`. Rewrite it without recursion. If n is very large, what breaks first?

**译文：** 这个函数在算什么？`f(n) = 1`（当 `n = 0`），否则 `f(n) = n × f(n − 1)`。把它改写成不用递归的版本。如果 n 非常大，先出问题的是什么？

**这道题在考什么：** 考递归、栈与数值增长。面试官想看你是否知道递归深度与整数溢出是两件不同的事。

**可以这样往下想：**
1. 这是阶乘 f(n) = n!。用循环从 1 乘到 n，用一个变量保存结果。
2. 递归版先撞上调用栈深度限制；迭代版没有栈问题，但结果会先超出固定宽度整数的范围。
3. 如果只需要末位或模某个数，可以在每一步取模，避免大数。

**面试官可能追问：** Without computing 2026!, how would you find its last digit?

**译文：** 不计算 2026!，怎样求它的末位数字？

### 第 4 题

**问：** Two people each hold a sorted list of 1,000 numbers. You may only ask “what is the k-th number in your list?”. Using as few questions as possible, find the median of the combined 2,000 numbers.

**译文：** 两个人各有一份排好序的 1000 个数字。你只能问「你列表里的第 k 个数是多少」。用尽量少的问题，找出合并后 2000 个数的中位数。

**这道题在考什么：** 考二分答案与不变量。关键不是合并，而是意识到中位数只取决于两边的分割点。

**可以这样往下想：**
1. 合并后长度是 2000，中位数是第 1000 与第 1001 个数的平均。
2. 在 A 中二分选 i，令 B 中取 j = 1000 − i，使左边共 1000 个数。检查 max(left) ≤ min(right)。
3. 满足条件后，中位数由左边最大值与右边最小值决定。每次询问把候选范围减半，约 10 次足够。

**面试官可能追问：** If the two lists have different lengths, how does the partition condition change?

**译文：** 如果两份列表长度不同，分割条件要怎么改？

### 第 5 题

**问：** A census records the exact age in years of 50 million people, from 0 to 120. How would you store the data if memory is tight? How would you answer “how many people are aged 30 to 40?” quickly?

**译文：** 一次人口普查要记录 5000 万人的确切年龄，范围是 0 到 120 岁。如果内存很紧，你会怎么存？如果还要快速回答「30 到 40 岁有多少人」，方案要怎么改？

**这道题在考什么：** 考数据表示与「不存个体也能回答聚合问题」的洞察。很多人第一反应是存 5000 万条记录，忽略了问题只需要计数。

**可以这样往下想：**
1. 如果只需要年龄分布，用 121 个计数器，每个 32 位，总共不到 500 字节，逐人加一即可。
2. 如果必须保留个体记录，每个年龄只需 7 位（2⁷ = 128），比 32 位整数省很多。
3. 范围查询用前缀和：对 121 个计数器做一次前缀和，任意区间就是两个前缀值相减，O(1) 回答。

**面试官可能追问：** If you also need the age distribution by region, how does the shape of the counter array change?

**译文：** 如果还要按地区看年龄分布，计数器的维度会怎么变？

## 常见问题
**必须会写代码吗？**

多数面试以口头设计和伪代码为主，不要求完整可运行的代码。但你需要能清楚写出循环、条件和数据结构操作，并解释每一行的代价。
**没有竞赛背景会不会吃亏？**

竞赛经历有帮助，但不是必需。面试官更看重你能否把一个问题拆开、验证自己的假设、在提示下改进。这些能力可以通过反复开口练习获得。

## 官方来源
- [牛津大学：本科面试指南（时间、形式与准备建议）](https://www.ox.ac.uk/admissions/undergraduate/applying/guide-for-applicants/interviews)
- [牛津大学：申请时间线（2027 年 1 月 12 日放榜）](https://www.ox.ac.uk/admissions/undergraduate/applying/admissions-timeline)
- [剑桥大学：面试安排（2026 年 12 月 7 日至 18 日主面试期）](https://www.undergraduate.study.cam.ac.uk/apply/after/cambridge-interviews)
- [剑桥大学：如何准备面试（含线上面试的设备与环境清单）](https://www.undergraduate.study.cam.ac.uk/apply/after/interview-preparation)

## 相关页面
- [全部学科面试题](https://www.frontiervue.com/zh/interviews/questions)
- [数学面试题](https://www.frontiervue.com/zh/interviews/questions/mathematics)
- [工程面试题](https://www.frontiervue.com/zh/interviews/questions/engineering)
- [牛津面试安排](https://www.frontiervue.com/zh/interviews/oxford)
- [剑桥面试安排](https://www.frontiervue.com/zh/interviews/cambridge)
- [TMUA 分数怎么读](https://www.frontiervue.com/zh/results/tmua)
