Algorithms study cheatsheets
Coding interview 的 Math cheatsheet
Math 学习指南，包含练习题、技巧、时间复杂度与推荐资源
Introduction
Math 是 Computer Science 的基础，每个程序员和计算机科学从业者都需要具备基本数学知识。好消息是，coding interview 通常不会涉及太多复杂数学，但掌握一些基础数学技巧会很有帮助，因为面试官可能让你实现数学运算。
Things to look out for during interviews
- 如果代码涉及除法或取模，记得处理除以 0 的情况。
- 使用 Java/C++ 等强类型语言时，检查并处理 overflow/underflow。至少要在面试中提到可能会溢出，并确认是否需要处理。
- 考虑负数与浮点数。虽然看起来显而易见，但在面试压力下容易忽略。
Corner cases
- Division by 0
- Multiplication by 1
- Negative numbers
- Floats
Common formulas
| Formula | |
|---|---|
| Check if a number is even | num % 2 == 0 |
| Sum of 1 to N | 1 + 2 + ... + (N - 1) + N = (N+1) * N/2 |
| Sum of Geometric Progression | 20 + 21 + 22 + 23 + ... 2n = 2n+1 - 1 |
| Permutations of N | N! / (N-K)! |
| Combinations of N | N! / (K! * (N-K)!) |
Techniques
Multiples of a number
当题目问“是否是 X 的倍数”，modulo 是最直接的工具。
Comparing floats
处理浮点数时要注意 rounding 错误。建议使用 epsilon 比较而不是直接相等。比如用 abs(x - y) <= 1e-6 代替 x == y。
Fast operators
如果需要实现 power、square root、division 且要求快于 O(n)，通常可以用 doubling（fast exponentiation）或 halving（binary search）。Examples: Pow(x, n), Sqrt(x)
Essential questions
这些是该 topic 必练题。
Recommended practice questions
这些是在掌握基础后推荐练习的题目。