大厂真题 / 备考技巧

大厂笔试必知必会

复杂度

在介绍具体的数据结构与算法之前，我们需要学习有关复杂度的概念，因为一切不考虑时空间复杂度的算法都是扯淡！对于校招生来说，需要熟练掌握时空复杂度，才能够在笔试中的有限时间内写出满足题目条件、可以正确运行并不超时的代码；对于自己在面试过程中写的代码，也需要能快速地分析出代码的时空间复杂度，才可以应对面试官的一些问题（例如：这道题你提供的代码时间复杂度是多少？有没有更快的做法…）

复杂度是一个关于输入数据量 n 的函数，下面将分别从时间和空间两个维度对复杂度进行详细介绍。

时间复杂度

假设某一个程序的时间复杂度为 O(n)，则说明该程序的执行效率与输入的数据量 n 线性相关。假设某一个程序的时间复杂度为 O(n^2)，则说明该程序的执行效率与输入的数据量 n 的平方线性相关。

时间复杂度与程序的执行效率成反比，例如当 n = 1000 时，时间复杂度为 O(n) 的算法比时间复杂度为 O(n^2) 的算法执行效率约快 1000 倍左右。

时间复杂度的计算有以下几个计算规则：

• 复杂度与具体的常数系数无关，例如 O(2n) 和 O(n) 表示的是相同程度的复杂度
• 一段程序的时间复杂度，只看最高项，例如 O(n^2 + 2n + 3log(n))，这段程序的时间复杂度应该取最高项，为 O(n^2)

为什么时间复杂度很重要？

因为所有的笔试题，题目都会给一个时间限制，这个时间限制的意思是，你写的代码在运行后台提供的测试样例中，需要在规定的时间内运行完，一般给的时间为 1s，有的会卡 500ms。

一般情况下，计算机 1s 可以执行 10^7 ~ 10^8 次操作，因此我们需要把我们程序执行的最大次数控制在这个区间内，一般控制在 3 × 10^7 较为安全。例如题目给定数据范围是 n <= 10^5，我们就不能设计出 O(n^2) 的算法，因为一定会被后台的一些测试样例卡住，然后提交代码只会显示部分通过（遇到严格的测试样例，只有 10% 左右的通过率），如果我们设计出 O(n) 或者 O(nlogn) 的算法，那就可以 100% 通过这道题的所有测试样例。

O(nlogn) 的最坏情况是：O(10^5 × log(10^5))，其中 log(10^5) = 5log(10) ≈ 6 × 3 = 18

（log(8) = 3, log(10) = 3.32）

因此 O(10^5 × log(10^5)) ≈ O(10^5 × 15) = O(1.5 × 10^6)，因此可以在 1s 中执行完。

根据时间复杂度反推数据结构与算法

下面的 n 就是题目给定的数据规模，建议大家对这个模块一边刷题一边回过头来反复理解，会加深自己的印象：

• n <= 20：这一类题目的数据范围较小，可以直接使用 DFS 算法，来枚举所有的情况，例如 DFS 专题中的二进制枚举，对应的复杂度为 O(2^n) 或者 O(n × 2^n)，在当前给定数据范围内，O(n × 2^n) 的最坏执行次数为 O(20 × 2^20) ≈ O(20 × 10^6) = O(2 × 10^7)，其中 2^10 = 1024 ≈ 10^3

• n <= 100：这一类题目可以使用 O(n^3) 以内复杂度的算法求解，这一类题型可能会涉及到二维前缀和、动态规划等算法。

• n <= 10^5：这一类题目可以使用 O(n) 或者 O(nlogn) 复杂度的算法求解，这一类题型可能涉及到堆（优先队列）、排序、动态规划、树状数组、堆优化版 dijkstra、二分查找、二分答案、质数筛等。

• n <= 10^9：这一类题目可以使用 O(√n) 或者 O(logn) 复杂度的算法求解，这一类题型可能涉及到判断质数、因子个数计算、二分答案、快速幂、最大公约数等。

• n <= 10^1000：这一类题目可以使用 O(logn) 或者 O((logn)^2) 复杂度的算法求解，这一类题型很大概率是数位 DP。

空间复杂度

空间复杂度的概念和时间复杂度很类似，时间复杂度是反映程序执行的效率，空间复杂度是反映程序执行所需存储空间的大小。例如，输入数据量为 n，你申请了一个长度为 n 的一维数组，那么对应的空间复杂度为 O(n)，如果申请的是二维数组，那么对应的空间复杂度为 O(n^2)。

一般题目给定的空间内存要求为 64MB，64MB = 2^6 × 1MB = 2^6 × 2^10 KB = 2^6 × 2^10 × 2^10 Byte = 2^26 Byte

如果申请的是 int 型的数组，每个元素占用 4 个字节（Byte），因此可以申请 2^24 长度的空间，也就是近似 10^7 左右的范围。

一般对于给定的题目来说，申请一维数组的长度尽量不要超过 5 × 10^6，申请二维数组的长度尽量不要超过 3 × 10^3，大家当结论记就行。

备战笔试必看

笔试介绍

• 笔试一般时间为 90-120 分钟，除了美团是五道编程题，字节、携程、微众银行等个别公司是四道编程题，其他大部分公司（例如阿里系（其中包含阿里淘天、蚂蚁、银泰百货、阿里大文娱、阿里国际等等）、华为、米哈游、小红书等公司）都是三道编程题，当然也有一些公司是两道编程题，我们要对整个笔试的难度有所把握，尽可能达到编程总成绩的 60% 及以上，这样进面试的机会会大一些

编程总成绩 = ∑ 每道题的通过率 × 每道题的总分值

特殊情况：例如华为三道题的分值分别为 100、200、300，那么你只需要保证第二题在 75% 以上的通过率，即使不做第一题、第三题也可以通过笔试，但是像米哈游这种要求很高的公司，基本上需要笔试成绩接近满分（AK）才有机会进入面试。

各公司笔试时间线

• 美团：春招/暑期实习笔试开始时间约为 3 月中上旬，秋招约为 8 月上旬。此后每隔一周会发一次笔试，一般会有 8 场笔试，也就是共计 2 个月的时间。美团的笔试成绩是作为参考，没有明确的分数线，会结合学历、简历综合考量来决定是否能够进入面试，当然也取决于投递部门的竞争力。（ps：从去年秋招美团笔试内容开始发生变化，算法岗 5 道编程题，开发岗 3 道编程题）

• 阿里：春招/暑期实习笔试开始时间约为 3 月中下旬 4 月初，秋招约为 8 月中下旬 9 月初。此后每隔 7~10 天会发一次笔试，一般会有 6~8 次笔试，笔试持续时间为 90~120 天。阿里系的笔试是有明确筛选标准的，因此想去阿里系的同学，需要格外重视一下笔试。阿里系（阿里淘天、阿里云、蚂蚁、阿里国际、达摩院等）阿里的各个部门是单独招聘的，因此需要单独去进行简历投递、笔试、测评、面试环节。

• 京东：春招/暑期实习笔试开始时间约为 3 月上旬，秋招约为 8 月上旬。此后每隔一周会发一次笔试，一般会有 8 场笔试，也就是共计 2 个月的时间。京东的笔试成绩是作为参考，没有明确的分数线，会结合学历、简历综合考量。

• 字节跳动：春招/暑期实习笔试开始时间约为 3 月中旬，秋招约为 8 月下旬 9 月初。字节笔试也是进入面试的一个重要指标，大家需要认真对待。

• 米哈游：春招/暑期实习笔试开始时间约为 3 月中旬，秋招约为 8 月上旬。此后每隔两周会发一次笔试，一般会有 2~4 次笔试，笔试持续时间为 30~60 天。米哈游也是进入面试的一个重要指标，一般三道编程题，需要做对 2.5 道左右才有面试机会，大家需要认真对待。

• 滴滴：春招/暑期实习笔试开始时间约为 3 月中旬，秋招约为 9 月上旬。此后每隔一周会发一次笔试，一般会有 2~4 次笔试，笔试持续时间为 15~30 天。

• 小红书：春招/暑期实习笔试开始时间约为 3 月中旬，秋招约为 8 月下旬 9 月上旬。此后每隔一周会发一次笔试，一般会有 3~6 次笔试，笔试持续时间为 30~60 天。注意：小红书笔试可能会考原题，例如第二场笔试可能会有第一场笔试的原题！

• 携程：春招/暑期实习笔试开始时间约为 3 月中旬，秋招约为 9 月上旬。此后每隔两周会发一次笔试，一般会有 2~4 次笔试，笔试持续时间为 30~60 天。

• 华为：暑期实习笔试开始时间约为 3 月中下旬，秋招约为 8 月中下旬。华为的笔试是有明确分数线：150 分的，因此笔试非常重要！不过线就没有面试机会！ 华为没有春招，只有暑期实习和秋招，并且不同地区的笔试时间是不一样的。

笔试难度

笔试中每道题的对应难度：

• 五道编程题：前 2 题 easy，第三题 easy~medium，第四题 medium~hard，第五题 hard
• 四道编程题：前两题 easy，第三题 medium~hard，第四题 hard
• 三道编程题：第一题 easy，第二题 medium，第三题 hard

笔试术语

笔试技巧

1. 做笔试题切记不要死磕

笔试中，大部分互联网公司是分为选择题、填空题和编程题这三个部分的，也有一些互联网公司（美团算法岗、拼多多、携程）是只考察编程题的。

一道题如果 20 分钟甚至 30 分钟都没有思路或者有思路实现的时候有问题，立刻去往后看看后面的题目是否有自己可以写的，一旦死磕一道题，时间很容易白白浪费，错失良机。

2. 笔试的题目，难度并不一定是严格递增的

有以下两种情况：

情况 1：这套题的实际难度并不是 T1 < T2 < T3，有可能是 T1 > T3 > T2 或者 T2 > T3 > T1。

情况 2：每个人擅长的算法和数据结构不一样，因此笔试题的难度只能说作为一个整体的难度来定义，可能有的 hard 题对于一些做过这种套路性题的同学来说堪比 easy，但有的 medium 题目对于一些从来没做过这类题型的同学就是 hard 级别。因此一定要至少每道题花个 3-5 分钟浏览一下题意，然后大致有一个判断来决定是做这道题还是继续回去磕前面的题目。

3. 不会做的题要会骗分

例如，数据范围 n <= 10^5，很明显只能使用 O(n) 或者 O(nlogn) 的算法来求解，但是如果一时想不到优化策略，可以先写一个 O(n^2) 的算法，去拿部分通过率的分数，有时候遇到出题人样例出的很弱，甚至可以通过 50% 以上的样例，但是大部分情况下，一般通过率都是只有不到 20%，但是有总比没有强。

还有一些情况，答案要求你输出一个方案数，你就可以输出一个跟输入数据规模 n 相关的一个数字，例如 n^2, n^3, n × (n-1), n/2 等等，碰碰运气，有时候会有意外收获。

4. 对于有自信能 100% 通过的题，但是只有很低的通过率，要学会从以下几点去找原因

• 数据范围：对于 C++ 和 Java 选手，题目数据范围给的是 2 × 10^5，你的数组是否开小了
• 数值范围：对于 C++ 和 Java 选手，题目数值范围给的是 -10^9 <= val <= 10^9，你的答案很多时候就不能用 int 型变量来作为输出了，要使用 long long 或者 long 输出，这个地方初学者经常容易犯错，必须要吃过一两次亏才长记性 hh
• 图论问题：题目只要没有明确说是有向图，就一定要按照无向图的模版来构建图，初学者很容易出错的一点是，题目给定了根节点的编号（一般为 1），但是他自己构建的时候按照有向图来构建，导致可能样例通过了，但是通过率极低，就是因为需要构建无向边（因为样例给定的两个点 a 和 b 可能恰好和图中的方向一致）
• 数值范围（Python 选手忽略）：如果执行运算操作，是需要分析处理之后最终的结果以及中间结果的数值是在什么范围内，然后考虑是定义 int 类型的变量，还是 long 类型的变量。int 型变量可以存储的数值范围是 -2^31 ~ 2^31 - 1，long 型变量可以存储的数值范围是 -2^63 ~ 2^63 - 1。我们可以记住 2^31 约为 21 亿，也就是 2 × 10^9。因此，如果执行运算的过程中极端情况下不会超过 2 × 10^9，那么我们就可以使用 int 型变量来存储，否则我们就需要使用 long 型变量来存储。Python 选手不需要考虑数值范围，因为在 Python 中，整数类型是动态的，Python 会自动处理大整数，不需要担心 int 和 long 的区别。

5. Python 同学推荐使用 PyPy 提交

Python 在笔试中虽然有很多好用的内置函数，但是诟病的一点是执行效率很低（哪怕设计的算法时间复杂度和 C++ 相同，但执行效率也不如 C++）。

PyPy 是一个替代的 Python 解释器，PyPy 使用了 JIT（即时）编译器，而 CPython 是标准的解释器，所以 PyPy 在运行某些类型的代码时速度更快。特别是那些有大量循环的程序，很多互联网公司的笔试都是可以使用 PyPy 提交的，因此推荐 Python 同学首选 PyPy 提交。

题目难度说明

题单中的每道题，都会标记一个难度系数 k，k 的范围为 1 <= k <= 9：

• 1 <= k <= 3：对应的是模板题或者是简单模拟题，对应笔试中的第一题签到题的难度

• 4 <= k <= 6：对应的是中等难度的题目，一般出现在笔试题的中间位置，例如美团的第三题、第四题，阿里系的第二题。有的题目的题面比较复杂，需要有一定抽象问题的能力（把问题转化为某一个算法问题求解，比如转化为区间加法问题，然后使用差分数组求解，或者转化为图的顺序访问问题，使用拓扑排序求解），也有的题目需要使用到一些小技巧，如二分答案，前后缀分解等

• 7 <= k <= 9：对应的是困难难度的题目，一般是笔试题的压轴题，可能会涉及一些数学题或者思维题（比如数学问题中的组合数学，贡献法计数，正难则反/逆向考虑这种思想），又或者一些比较笔试中考的很难的算法，比如树形 DP、树状数组、逆元等。

注意：本难度只是一个大致的说明，并没有绝对的标准，有的 6 分题可能有些同学做起来比 8 分题还难，有些 7 分题可能对于一些同学来说并没有那么难，每个同学擅长的考点和题型是不完全相同的。

ACM 模式

ACM 模式介绍

刷习惯 LeetCode 的同学，刚开始做笔试题可能会很不适应，因为 LeetCode 是核心代码模式，只需要写具体的处理逻辑，下面给出这二者具体的一些区别，大家可以了解一下，在后面多做几道算法题基本上就可以快速上手 ACM 模式了！

LeetCode 模式 vs ACM 模式

1. 输入输出处理：

• LeetCode（核心代码模式）通常只需要编写函数或方法，输入通过参数传递，输出通过返回值，不需要处理输入输出格式
• ACM 模式：需要自己编写完整的程序，包括读取输入、处理数据、输出结果，输入可能来自标准输入（如控制台），输出需要严格符合格式要求

2. 代码结构：

• LeetCode 用户只需关注算法逻辑，不需要处理主函数或其他辅助代码
• ACM 模式需要完整的程序结构，包括 main 函数，可能需要处理多组测试用例，循环读取输入直到结束

3. 调试与错误处理：

• LeetCode 提供错误信息和测试用例示例，帮助调试
• ACM 模式在笔试中没有详细的错误提示，需要自己处理边界条件和格式错误，尤其是当某道题的通过率没有 100% 的时候，也不会提供给你没有通过的样例的，这个是很重要的，需要自己分析原因，一般原因有以下几个方面（算法时间复杂度较大，部分样例超时未通过；边界情况未考虑清楚；算法设计错误，例如有些算法题只能使用动态规划求解但是却使用了贪心算法求解）

4. 代码风格和全局变量：

• LeetCode 通常使用纯函数，避免全局变量
• ACM 模式可能允许或需要使用全局变量来简化代码，尤其是在递归或回溯算法中

Python ACM 模式模板

import sys
input = sys.stdin.readline

# 读取单个整数
n = int(input())

# 读取一行多个整数
a, b = map(int, input().split())

# 读取一行数组
arr = list(map(int, input().split()))

# 多组测试用例
T = int(input())
for _ in range(T):
    n = int(input())
    arr = list(map(int, input().split()))
    # 处理逻辑
    print(result)

提示：import sys; input = sys.stdin.readline 是 Python 笔试中加速输入的标准写法，比内置的 input() 快很多，在大数据量时可以避免 TLE。