Google VO 面试真题解析：IP 地址映射城市名称（区间查找）

I have a file with the following format, each line: startIP, endIP, cityName.

Question: Write a function that takes as input an IP address and outputs its associated cityName.

Example:

File format:

startIP, endIP, cityName
1.0.1.1, 1.0.1.10, NYC
1.0.1.20, 1.0.1.30, SF
...

If the input is 1.0.1.9, the output should be NYC.

这道题本质上是一个区间查找问题：给定若干条 IP 段区间 <code>[startIP, endIP]</code> 与对应城市名，要求对输入 IP 快速找到命中的区间并返回城市。实现时通常先把 IP 地址转换成可比较的整数形式，再将所有区间按起点排序，使用二分查找定位目标 IP 所在的区间；如果数据规模很大，也可以考虑区间树等结构。题目重点是正确处理 IP 的字典序与数值序差异，以及边界是否包含端点。