题目没看懂。。。

题目没看懂

这题目太长，放弃

如果控制算法没接触过，估计悬。
这题很难读么？

每个文字都看得懂，连起来就看不懂了

谢绝骗方案、骗代码型面试

好深奥的题目呀

本咸鱼弃疗

无所适从

知道想考啥，但就是不会

我觉得是要验证导航算法的正确性和性能吧，第一个是验证下从地图云端拉取 POI 点的性能，第二个是验证到达时间的准确性。

应该不是吧，我看上去是考察基础算法，和对未知业务的理解和解决问题的能力。
可能是外企的高端测试岗吧，要考察基本能力，需要有一定的数学理解，而不是简单的背八股文。
当然也可能是我猜错了，没事写英文的，要么装 b，要么是真的高大上。

确实是外企的测开岗，就是题目比较绕，不熟悉业务看着比较晕

感觉说的也有道理

感觉 a.每 1/4 面积的图中不能包含大于三个点——个人感觉就是任意四个点组成的面积应该大于 1/4 面积就行。
b. 剩下距离/预期平均速度算个到达时间

感觉没毛病，但是怎么做呢

通过简单算法找模块的位置还是比较容易的，但是不借助三方库去识别文字信息还是有点难

感觉这个像是比较另类的算法题，包了个导航的壳，实际考察内容和导航算法啥的没半毛钱关系。题目里已经给了可用的变量和函数（function 翻译为模块感觉怪怪的，个人更喜欢用函数这个名字），并且限制只能用标准库，意思就是根据变量和函数的组合来解题。

大概写了下：

a.从性能角度考虑，地图中每四分之一的部分中不能显示超过三个 POI 标识

def is_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 代码可能效率更高。

你说要测这个导航系统吧，但是给的 api 全是这么底层的，明明只要开放一点接口就能做到的事情，非要从底层 api 堆叠回本应该提供的接口，何苦呢。

而且如果提供真正的公有接口，测试能把从接口到实际 ui 显示都给测了。现在这样你只能测 ui，出问题你还是得再 debug 确定问题是接口数据，还是画 ui 的时候出得问题，自己给自己添麻烦

第一个用鞋带定理

从性能角度考虑，每 1/4 区域应该是任意 1/4 区域吧~我觉得不划区域直接算面积比较合适

直接划 1/4 是有点粗暴了，确实任意 1/4 好点。但没想好具体要怎么判定，直接连接 4 个 label 中心点，有可以出现凹多边形，面积不够 1/4 但如果忽略凹点可能就够 1/4，应该也算作有问题

可以直接写下伪代码分享一下完整算法？

就是上面的高斯面积公式（鞋带公式），凹凸四边形都能算。

我来说下我如果来分析大概会怎么做吧：
问题 1：

1. 首先是判断图标的准确度的函数是否可靠。这里使用的是什么算法，该算法是否支持旋转，图片的获取源是从哪里拿到的，是外部设备截屏，还是系统截屏。
2. 根据判断图片准确度的算法来设计遍历 POI 的算法，如果 1920*490 每个像素遍历，我认为时间复杂度会很高，所以 1 我必须了解。同时我需要设计去重的判断标准。
3. 获取到所有的 POI，根据边界，判断落在哪个区域，注意一个 POI 可能落在多个区域。

至于问题 2：
1.首先保证平均时速的准确性。
2.保证目的地距离的准确性。
如果三方提供，已经过实际应用，不考虑 1，2 前置。
3.验证在 1，2 变化的情况下，到达时间。时间计算需要用当前系统时间 + 速度时间，如果精度是秒，需要考虑时速转化，KM/H 转化成 M/S。
4.遍历图片，获取时间 ARRIVAL ICON。通过字符识别，获取时速和到达时间，和前面获取到的信息进行比对。

问题一的解法，方便花点时间直接写下代码么，代码看起来更清晰，只是文字描述思路总有些不理解的地方。

判断图标的这个函数，我理解对于 POI 标签这个场景，会不会容易受到里面文字内容不同干扰导致识别错误？

要看 MatchImage 的算法了，可以每个标签做一个 LABEL。
然后针对两种场景：
1.如果是从系统拿出来的图，可以保证没有旋转，那就直接按像素匹配。
2.如果还得第三方截图，那就得自己做图像识别算法了。
比如：
简单算法的如颜色直方图，准确度就可能有问题。
用模板匹配会好一点，阈值什么的也得调。

系统都不是孤立的，要把前后端串起来，也就是端到端吧 O(∩_∩) O。

题目就这么长......

瞎写的，不知道有没有问题，反正不是我面试。。。233333

public void isMoreThanThreePOI(pic){
    //一帧图片上最多有12个POI，如果超过12个，肯定有1/4的区域有大于3个POI.POINum>12,return true;
    //同理，如果POI一张图片小于等于3个，那么肯定是不会有区域大于3个POI的.POINum<=3,retrun false;
    //如果4<=POI个数<=12，那么任意四个点的面积只要小于1/4图片面积，即为false
    //需要选择尽可能小面积的四个点，首先划分平均四个区域，如果4个区域内就有超过4个点，return false;
    //然后再看由2-4个区域的点构成的四边形是否有小于1/4面积的情况，再进行遍历
    List<MyPoint> points=getAllPoi(pic);
    if points.size()>12 return true;
    else if points.size()<=3 return false;
    else{
        Stack<MyPoint> stack = new Stack<MyPoint>();
        List<double> s=getPointCombiArea(points,4,0,0);
        for si....
            if si<1080x490/4 return true;
        return false;
    }
}

Stack<MyPoint> getPointCombiArea(List<MyPoint> points,int targ, int has, int cur){
    if(has == targ) {

            return stack;
        }

        for(int i=cur;i<points.size();i++) {
            if(!stack.contains(points.get[i])) {
                stack.add(points.get[i]);
                getPointCombiArea(points, targ, has+1, i);
                stack.pop();
            }
        }
}

//鞋带算法，这里的4就是四个点的意思。
public  double area(MyPoint[] points){
        double s=0.0;
        for(int i = 0; i < 4; i++){
            if (i != 3){
                s += points[i].getX() * points[i + 1].getY() - points[i].getY() * points[i + 1].getX();
            } else{
                s += points[i].getX() * points[0].getY()- points[i].getY() * points[0].getX();
            }

        }

        return Math.abs(s/2);
}

//获取图片中的所有POI点
public List<MyPoint> getAllPoi(pic){
List<MyPoint> points=new ArrayList<>();
    for(int current_x = 0; current_x <= end_x; current_x++){
        for(int current_y = 0; current_y <= end_y; current_y++){
            if(getColor(current_x, current_y) == "red"){
                points.add(new MyPoint(current_x+50,current_y+15));
                current_x += 100;
                current_y += 30;
            }
        }
    }
    return points;
}

这莫复杂，看题目人都炸了

看了下代码，2 个疑问点：
1、f(points, targ, has+1, i); ，这里的 f 函数是什么？看参数就是 getPointCombiArea 自己？
2、area 这个计算多边形面积的函数在哪里用到？搜了下这个函数定义后好像就没被调用过，所以关键的判定面积方面的算法还是没太看出来是怎么做。

1.可以反着来吗？确定图上的所有 POI，然后任意 3 个 POI 边界点算面积 是否超过 1/4？

f 就是递归调用达到 12 点选 4 点的目的，是 getPointCombiArea。
area 计算面积是在排列组合 C12(4) 之后，用这四个点集算个面积。写这个的时候恰好有人找我，赶紧胡乱结束了。看着是有点不清晰。1080x490/4 这里应该是 4，也就是 1/4 面积。
最后的那点其实就是 12 点选 4 点的所有情况（去重）遍历计算面积，有小于 1080x490/4 return true;

这个遍历像素找 POI 的算法，找到一个 POI 后，把从 current_x 到 current_x += label["width"] 之间的一竖排屏幕区域都跳过了，如果下方还有个 x 位置一样的 POI，会被忽略吧

感谢指出，这确实是一个 bug。会导致遍历起始点直接往 label 右下角移动，label 下方和左方剩余区域都被忽略。

不应该直接跳过，应该只是对这个区域做标记，遇到这片区域的点直接跳过 getColor 就好。

题目没看懂