跳到主要内容

计算机科学面试

计算机科学面试题:先讲清假设,再写算法

7 个小节1,259 字约 4 分钟读完4 条官方来源

面试形式

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

阅读缩放
第 1 部分

计算机科学面试在考什么

面试官通常不期待你直接写出最优解。他们更常从一个小例子开始,让你描述一个笨办法,然后逐步追问:如果数据量变成一百万呢?如果只能顺序读取呢?如果内存放不下呢?
所以真正的考点是「把问题形式化」:输入是什么、输出是什么、允许哪些操作、最坏情况是什么。把这些说清楚,算法往往自己就出来了。
一个万能开场:「我先假设输入是……,如果这个假设不成立,做法会变成……」 面试官很看重你是否意识到假设的存在。
第 2 部分

怎样用这 5 道题练习

01

先给朴素解

不要一上来追求最优。先说一个肯定正确的做法,再分析它慢在哪里。
02必答

标出复杂度

对每一步说明时间与空间代价,并指出哪一项会先成为瓶颈。
03

找一个反例

空输入、重复元素、已经有序、极端大或极端小,至少试两个。
04

再优化一档

通常只需要换一个数据结构或利用一个不变量,不必推翻重来。
原创练习

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

下面每道题都是方添优学独家原创。先读题,边做边把思路讲出来,再对照解题思路,找出自己卡在哪一步。

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?
你有一个排好序的一百万个整数。要判断某个值是否存在,二分查找最多需要比较多少次?如果这些数存在链表里,会有什么变化?
Frontier ACE 模拟练习3 步提示
  1. 这道题在考什么
    考对数复杂度与数据结构前提。很多人会背 O(log n),却说不清二分查找依赖「随机访问」这个隐藏假设。
  2. 1
    第 1 步
    因为 2²⁰ = 1,048,576,超过一百万,所以最多约 20 次比较。
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?
描述一个算法,找出字符串中第一个重复出现的字符。它的时间与空间复杂度是多少?你会怎么测试它?
Frontier ACE 模拟练习3 步提示
  1. 这道题在考什么
    考哈希表的使用与边界情况。题目简单,但「第一个」和「重复」都需要精确定义,测试设计能看出工程习惯。
  2. 1
    第 1 步
    从左到右扫描,用集合记录见过的字符。遇到已在集合里的字符就返回它,否则加入集合。
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 非常大,先出问题的是什么?
Frontier ACE 模拟练习3 步提示
  1. 这道题在考什么
    考递归、栈与数值增长。面试官想看你是否知道递归深度与整数溢出是两件不同的事。
  2. 1
    第 1 步
    这是阶乘 f(n) = n!。用循环从 1 乘到 n,用一个变量保存结果。
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 个数的中位数。
Frontier ACE 模拟练习3 步提示
  1. 这道题在考什么
    考二分答案与不变量。关键不是合并,而是意识到中位数只取决于两边的分割点。
  2. 1
    第 1 步
    合并后长度是 2000,中位数是第 1000 与第 1001 个数的平均。
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 岁有多少人」,方案要怎么改?
Frontier ACE 模拟练习3 步提示
  1. 这道题在考什么
    考数据表示与「不存个体也能回答聚合问题」的洞察。很多人第一反应是存 5000 万条记录,忽略了问题只需要计数。
  2. 1
    第 1 步
    如果只需要年龄分布,用 121 个计数器,每个 32 位,总共不到 500 字节,逐人加一即可。

方添优学旗下

把思路真的说出口,再上考场

Frontier ACE 是方添优学旗下的 AI 面试练习站,面向牛津、剑桥与帝国理工申请者。它提供限时视频练习与模拟面试,并按五个维度给每次作答打分。适合练「边想边说」,再回到这里的学科题做深度练习。

Frontier ACE 是方添优学旗下站点。链接在新标签页打开,并带有来源标记。

出处

官方来源

4 条官方来源,点开查看
FAQ

常见问题

必须会写代码吗?
多数面试以口头设计和伪代码为主,不要求完整可运行的代码。但你需要能清楚写出循环、条件和数据结构操作,并解释每一行的代价。
没有竞赛背景会不会吃亏?
竞赛经历有帮助,但不是必需。面试官更看重你能否把一个问题拆开、验证自己的假设、在提示下改进。这些能力可以通过反复开口练习获得。

UAT-UK、Pearson、OCR、剑桥大学、帝国理工学院等名称与标识,归各自所有者所有。

下一步:把计算机科学面试练成对话

先把 5 道题全部开口练一遍,再用 FrontierACE 模拟一整场面试。两者都由方添优学团队制作。