能收到Two Sigma的面试邀请，心情大概就像坐过山车，一半是顶尖量化基金光环带来的兴奋，另一半是它家面试难度都市传说带来的巨大压力。当约好时间的远程面试开始，我和面试官在屏幕两端，气氛友好但暗藏锋芒，我知道真正的挑战要来了。
简单寒暄后，面试官没有多余铺垫，直接在共享代码编辑器里贴出了今天的题目。看到题目的那一刻，我感觉空气都凝固了，这并非一道在题库里能轻易刷到的原题。
LA12 - Map Equivalence
Description
Geographical maps representing land and water forms can be stored in the form of a grid where 1 represents land and 0 represents water. In such a scenario, land equivalence is possible by comparing grids of two maps and checking if they have any matching land regions.
There are two grids where each cell of the grids contains either 0 or 1. If two cells share a side then they are adjacent. Cells that contain 1 form a connected region (e.g. an island) if any cell of that region can be reached by moving by row or column through the adjacent cells that contain 1. Overlay the first grid onto the second and if a region of the first grid completely matches a region of the second grid, the regions are matched. The task is to count the total number of such matched regions in the second grid.
Function Description
Complete the function countMatchingRegions in the editor below.
countMatchingRegions has the following parameter(s):
string grid1[n]: an array of bit strings representing the rows of map 1string grid2[n]: an array of bit strings representing the rows of map 2
Returns
int: number of matching land regions.
看完题目，我深吸一口气。这题的核心是“找相同”，但不是简单的像素点对比，而是要比较“区域”或“岛屿”的“形状”。如果两个岛屿在grid1和grid2中占据的坐标集合完全一样，它们才算匹配。
我的第一反应是，这题必须分两步走。首先，得有办法把每个网格里的所有独立岛屿都识别出来。这自然而然地指向了图搜索算法，深度优先（DFS）或广度优先（BFS）都是可行的工具。我会遍历整个网格，每当遇到一个未访问过的‘1’，就启动一次搜索，把整个相连的岛屿都找出来，并标记为已访问。
但真正的难点在第二步：如何判断两个岛屿“形状完全一样”？一个岛屿可能由几十个坐标点组成，直接比较原始坐标列表是行不通的。关键在于要给每个岛屿生成一个独一无二的、与它在网格中绝对位置无关的“身份证”，也就是一种规范化的表示。
我的思路是，对于找到的每一个岛屿，将它所有点的坐标(r, c)都收集起来。然后，为了让这个形状可以比较，我将所有坐标点相对于该岛屿自己的左上角顶点进行平移。比如，找出这个岛屿中最小的行坐标min_r和最小的列坐标min_c，然后岛屿上的每个点(r, c)都变成(r - min_r, c - min_c)。这样，无论岛屿出现在网格的哪个位置，只要形状相同，它这套相对坐标的集合就必然相同。最后再把这组相对坐标排序，存成一个元组，就成了它不可变的“指纹”。
有了这个思路，剩下的就好办了。我先用这个方法处理grid1，把所有岛屿的“指纹”都提取出来，放进一个哈希集合（Set）里，方便快速查找。接着，再对grid2做同样的操作，每得到一个grid2中岛屿的指纹，就去grid1的指纹集合里查询一下是否存在。如果存在，计数器就加一。
整个沟通过程，我一边说思路，一边在编辑器里写下函数签名和注释，让面试官能清晰地跟上我的节奏。他对我提出的“规范化岛屿形状”表示了认可，这让我信心大增。这道题完美体现了Two Sigma的风格：它基于一个经典的算法框架（图搜索），但加上了一层巧妙的逻辑包装（形状的规范化表示），考察的不仅是你的编码能力，更是你抽象问题和设计解决方案的能力。
希望能给同样在求职路上的你一点参考，祝大家都能在面试中展现最好的自己，顺利上岸！
本文的作者 石老师，在这里给大家打个硬广，csoahelp.com每日分享北美大厂面经，小红书也有更新，我们还提供种类多样的收费服务协助您进入北美科技大厂，有意向的微信扫码联系我，或者也可以通过其他方式联系我
