Algorithms study cheatsheets
Coding interview 的 Geometry cheatsheet
Geometry 学习指南，包含练习题、技巧、时间复杂度与推荐资源
Introduction
Geometry 是数学中研究空间性质的分支，涉及距离、形状、大小与相对位置。高级几何（如 3D geometry）在多数 Computer Science 课程里并不常见，所以面试通常只考 2D geometry。
在算法面试中，geometry 通常不是题目核心（毕竟不是真的考数学），更多是配合其他算法或数据结构使用。
Corner cases
- Zero values。这个很容易坑到人。
Techniques
Distance between two points
比较两点距离时，用 dx2 + dy2 即可，不需要开根号。Examples: K Closest Points to Origin
Overlapping circles
判断两个圆是否重叠：检查圆心距离是否小于半径之和。
Overlapping rectangles
两个矩形重叠的条件：
overlap = rect_a.left < rect_b.right and \
rect_a.right > rect_b.left and \
rect_a.top > rect_b.bottom and \
rect_a.bottom < rect_b.top
这里有个 可视化。Examples: Rectangle Overlap
Sample questions
- 你有一个平面，上面有很多矩形，如何判断有多少矩形相交？
- 你会用什么数据结构来查询 2D 平面中 k 近邻的点？
- 给你很多点，找出距离原点最近的 k 个点。
- 如何对一个多边形进行三角剖分？
Essential questions
这些是该 topic 必练题。
Recommended practice questions
这些是在掌握基础后推荐练习的题目。