Visa OA 面试复盘｜矩阵改成 Y，数轴上的方块能不能放

Visa 的一份 2024 年 9 月校园招聘记录里，CodeSignal 给了 70 分钟、四道编程题。这里细讲其中描述完整的第 1 题和第 3 题：一道要把矩阵改成字母 Y，另一道要判断指定位置能否放下方块。两题都要优先把范围写准，错误经常出在中心点和区间端点上。 这份校园批次与美国岗位的测评安排要分开看。 加州 SDE Intern 候选人的记录 描述的是 2021 年申请后收到两题 HackerRank；Taro 上另一位美国候选人也提到两题 HackerRank。准备当次考试时，以邀请邮件里的平台和题量为准，别把不同批次拼成同一套卷子。

第一题：把矩阵改成字母 Y

题目描述

输入是边长为奇数的方阵，元素只取 0、1、2。Y 的两条斜臂从上方两个角延伸到中心，竖干从中心向下。选择一种值填满 Y，再选另一种值填满背景，求最少要修改多少个格子。Y 和背景的值必须不同。 下面用自拟的 3×3 例子手算：三行分别为 [0,2,0] 、 [2,1,2] 、 [2,1,2] 。Y 上共有四格，其中两个 0、两个 1；其余五格都是 2。把 Y 全部改成 0 或全部改成 1 都只需两次修改，答案是 2。

解题思路

设中心下标为 mid = n // 2 ，行列下标从 0 开始。上半部分只接纳两条斜臂，下半部分只接纳中间一列。把中心行交给竖干处理，条件就能写成： is_y = (r < mid and (c == r or c == n - 1 - r)) or (r >= mid and c == mid) 遍历矩阵，分别统计 Y 内和背景中 0、1、2 的数量，得到 inside[3] 和 outside[3] 。假设 Y 使用值 a、背景使用值 b，修改次数就是 Y格数 - inside[a] + 背景格数 - outside[b] 。枚举 a、b 且排除 a == b ，一共六种方案，取最小值即可。 不能各自挑出现最多的值后直接相加：两个区域的最多值会撞在一起。例如 Y 和背景都以 0 为主时，这种做法得到的方案违反题意。六次枚举的成本很小，也更容易检查。 中心格只计一次；Y 的斜臂在中心以下不能继续伸到左右下角。写完分类条件后，用 3×3 和 5×5 各画一张图，逐格对照。 复杂度 ：时间 O(n²)，额外空间 O(1)。

第三题：指定区间里有没有障碍物

题目描述

操作有两类： [1,x] 在整数坐标 x 放置障碍； [2,x,size] 检查一个长度为 size、末格为 x-1 的方块能否放下。将每次查询结果拼成二进制字符串。 按这个描述，待检查的整数坐标范围是 [x-size,x-1] ，也可写成半开区间 [x-size,x) 。这里采用“被占用的整数格不能覆盖”的规则；这与“在 x 左边任意找一段空位”的另一类放块题不同。 自拟练习：先在 4 和 10 放障碍。查询 [2,10,5] 检查 5 到 9，返回 1；查询 [2,10,6] 检查 4 到 9，返回 0；查询 [2,11,1] 只检查 10，返回 0。拼接结果为 100 。障碍恰在 x 上不影响以 x-1 结束的方块。

解题思路

维护一个有序障碍集合。查询时找到严格小于 x 的最大障碍 p：如果它存在且 p >= x-size ，方块会碰到障碍；否则整个目标区间都为空。只查一个前驱就足够，因为其余小于 x 的障碍都在 p 左边。 C++ 可以对 set 调用 lower_bound(x) ，迭代器前移之前先判断是否等于 begin() 。Java 可用 TreeSet.lower(x) 。重复插入同一坐标不会增加障碍数量。每次操作都是 O(log q)，q 为操作数。 Python 的排序列表加 bisect 能迅速写出基准解，但插入仍需搬移元素，最坏是 O(q²) 总时间。操作数较大时，可以先收集所有插入坐标做离散化，再用 Fenwick Tree 维护已占用点数。查询区间内的计数为零就能放。离散化只替换索引；判断区间范围时仍用原坐标，不能拿压缩后下标的差代替方块长度。 这一题无需维护全局最大空隙。每次查询已经固定了方块末端，维护障碍位置足够。若题目改成“任意位置放块”，才需要重新设计查询内容。

Visa OA 做题顺序如何安排

这份四题记录还提到了按学生姓名聚合成绩，以及另一种 Y 形定义。成绩题可以用总分和次数计算平均值；并列规则要读题确认。另一种 Y 的几何定义没有完整展开，因此这里不替它补题面。 练习时先完成能给出明确边界的题，再做复杂实现。矩阵题保留六种颜色组合的手算表；数轴题至少测无障碍、左端有障碍、右端 x 有障碍和重复插入。最后留几分钟检查函数签名、输出顺序和空集合分支。

FAQ

矩阵题需要 BFS 或 DFS 吗？

Y 的位置由坐标直接决定，不需要搜索连通区域。每个格子判断一次归属即可。

方块长度很大，能逐格扫描吗？

不要让运行时间跟坐标跨度绑定。查询障碍前驱或区间内的障碍数量，都不需要扫描每个整数坐标。

可以用 CodeSignal 分数判断一定能进下一轮吗？

分数只描述本次测评表现。两位美国候选人的后续结果不同，不能据此推导统一录取线；流程状态以招聘方通知为准。

参考来源

Khushiagarwal：Visa 校园实习的 CodeSignal 四题记录 LeetCode：Visa 加州 SDE Intern 申请与两题 HackerRank 经历 Taro：Visa 美国 SWE 候选人的 HackerRank 与后续流程经历

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。