作者：sometimes
昨天社区有同学发了一道测开面试题，求解？我把链接发给我开发同事，他说测试要求现在这么高吗？不是点点点就可以了么？（鄙视链低端日常）。那这是一道什么题目呢？让我们来看看：
算法与问题求解 要验证导航系统的软件，需要创建一个自动化测试用例。您可以自动截屏 (1080x490px) 导航内容，并提供以下信息：
开发规范描述了显示内容的设计和行为方面
此外，可以通过全局变量访问汽车导航电脑上的如下信息：
任务：
请用伪代码写出算法以验证如下信息：
从性能角度考虑，地图中每四分之一的部分中不能显示超过三个 POI 标识
到达信息框中显示的预期到达时间应该始终基于到达目的地之前的预期平均速度
考虑可以使用给定信息自动验证的更多规范，写出相关算法
近一步说明：
汽车电脑提供的信息总是正确的
其他所有信息都需要从截图中提取
从左上角开始计算 x 和 y 的坐标
只能使用标准的 Python/Java/库
(⊙o⊙)…，说实在，题目就没有看懂。讨论很精彩，也有高手回答了，比如：
--- From 恒捷 ---
感觉这个像是比较另类的算法题，包了个导航的壳，实际考察内容和导航算法啥的没半毛钱关系。题目里已经给了可用的变量和函数（function 翻译为模块感觉怪怪的，个人更喜欢用函数这个名字），并且限制只能用标准库，意思就是根据变量和函数的组合来解题。
大概写了下：
a.从性能角度考虑，地图中每四分之一的部分中不能显示超过三个 POI 标识
```defis_more_than_3_label_in_each_quater_screen():
"""
判断地图中每四分之一的部分中不能显示超过三个 POI 标识。如果超过返回 True ，否则返回 False
"""
# 把图拆为4部分（每个大小540*245）
areas = [
{"startX": 0, "startY": 0, "endX": 540, "endY":245},
{"startX": 541, "startY": 0, "endX": 1080, "endY":245},
{"startX": 0, "startY": 246, "endX": 540, "endY":490},
{"startX": 541, "startY": 246, "endX": 1080, "endY":290}
]
for area in areas:
# 每个部分分别先用 getText 看下有没有文本。没有文本说明没有标签，直接略过
if getText(area["starX"], area["startY"], area["endX"], area["endY"]):
# 有文字，进一步判定有没有标签。实际这个判断可以融合到上面 if 里面，只是为了便于阅读单独拎出来
if _is_has_more_than_3_label(area):
return True
return False
def_is_has_more_than_3_label(area):
"""
判断当前区域里面是否有3个 PIO label
Args:
area: 一个记录区域起始结束位置的字典。示例：{"startX": 0, "startY": 0, "endX": 540, "endY":245}
"""
label_count = 0
label = {"width": 100, "height": 30}
# 判定下有没有标签。标签特征是大小为100*30，且最外面2px是红色。可以通过获取像素颜色值判定下
current_x = area["startX"]
current_y = area["startY"]
# 遍历每个像素点
while current_x <= area["endX"]:
while current_y <= area["endY"]:
# 判定是不是红色，是的话说明有标签，因为只有标签会有红色
if getColor(current_x, current_y) == "red":
label_count += 1
# 有标签，直接可以跳过这个标签大小区域了。
# 如果刚好某个标签横跨2个区域，那它在当前区域的大小就不一定是这个固定值
# （这里暂且把这种只有一部分在区域内的也算作这个区域内标签，实际可能还得搞个判定算法，达到几分之几才算在这个区域内）
# ，不过也不可能会在跳过的位置中间藏了一个标签漏检测，所以不影响标签数量判定。
# 但如果加上标签可能会重叠，那就会更复杂。实际项目个人实在不推荐这么玩哈，直接拿原始接口数据更好
current_x += label["width"]
current_y += label["height"]
# 标签边框里的红色宽度是2，但考虑到有可能命中红色的时候并不是刚好就是边框，所以还是逐个像素遍历吧，也没多少次循环。
y += 1
x += 1
return label_count > 3
```
到达信息框中显示的预期到达时间应该始终基于到达目的地之前的预期平均速度
写代码有点花时间了，写思路吧：1、根据 variable 拿到平均车速、当前时间 2、用 getText 直接拿整个地图的 text ，用正则提取出到达信息里的 剩余距离、预计到达时间 (当然也有点风险，比如刚好就有个 PIO Label 也符合正则表达式内容可能就会误判了。最靠谱还是遍历整个图像找那个显示剩余距离剩余时间的框，再从框里提取文字) 3、预计到达时间-当前时间获得背后程序计算出来的剩余时长，然后用剩余距离/剩余车速再手动算一个剩余时长，比较一下。特别注意的是 24 小时制这个点，不确定标准库意思是能不能用 datetime 之类的，不允许的话要自己写个小函数来算两个时间差异的小时值
最后，多提一嘴，如果是实际项目，问题一还是找开发去开放一些接口，用于获取背后的数据吧。用图像识别纯黑盒测试，效率不高，投入不少（比如还得像上面这样自己像个算法），直接基于数据简单多了。问题二的话，这个计算逻辑应该不太复杂，直接 review 代码可能效率更高。
--- end ---
--- From magicYang ---
我来说下我如果来分析大概会怎么做吧：问题 1：
首先是判断图标的准确度的函数是否可靠。这里使用的是什么算法，该算法是否支持旋转，图片的获取源是从哪里拿到的，是外部设备截屏，还是系统截屏。
根据判断图片准确度的算法来设计遍历 POI 的算法，如果 1920*490 每个像素遍历，我认为时间复杂度会很高，所以 1 我必须了解。同时我需要设计去重的判断标准。
获取到所有的 POI，根据边界，判断落在哪个区域，注意一个 POI 可能落在多个区域。
至于问题 2：1.首先保证平均时速的准确性。2.保证目的地距离的准确性。如果三方提供，已经过实际应用，不考虑 1，2 前置。3.验证在 1，2 变化的情况下，到达时间。时间计算需要用当前系统时间+速度时间，如果精度是秒，需要考虑时速转化，KM/H 转化成 M/S。4.遍历图片，获取时间 ARRIVAL ICON。通过字符识别，获取时速和到达时间，和前面获取到的信息进行比对。
--- end ---
网友评论