我最近参加了一次软件工程面试，被问到一系列知识领域之外的问题，我觉得这里有一些科学计算原理（我多年前参加了一些 scicomp 课程，当提出了这些问题）。我想知道是否有人知道这是什么问题？我怀疑这是伪装的某种经典问题。

给定一个长度 = n 且宽度 = m 的大矩形。矩形被分成许多不相交的区域，这些区域有各种形状（不一定是凸面的）和大小。每个不相交的区域都分配有一个不同的 ID。假设大约有 200 个这样的不相交区域/ID。此外，假设您有一个巨大的矩阵mat，mat[i][j]对应于某个坐标(x=i, y=j)并mat[i][j]表示该坐标处的 ID。但是mat太大了，无法将其存储在内存中。（我在这里有点困惑，因为他说你得到了这个矩阵，但它没有存储在内存中，所以我不太明白你是如何“给定”矩阵的）

我被问到的第一个问题：

您将如何mat使用易于存储且更高效的内存结构？面试官在这里想要的想法是不断地将大矩形分成非常小的正方形，直到该区域由一个 ID 组成（此时您停止将该区域切割成更小的正方形）。然后保存这个正方形。这听起来很简单，就像网格一样。

我被问到的第二个问题是：

你将如何存储这些正方形？你会使用什么数据结构？我认为他想要某种排序方式，但我不知道他指的是什么。

有谁知道这里有什么好的存储结构？看起来它只是一个正方形的网格，而且我知道有存储结构化和非结构化网格的传统方法（我非常怀疑这是面试官想要的，因为这对于软件工程师来说非常偏离主题）。

然后最后一个问题是

给定一个 (x,y) 坐标，您想快速查询该坐标属于哪个 ID。你会怎么做？我说你可以使用某种二进制搜索（此时，我只是在编造一些东西……），面试官希望我考虑“同时压缩 x 和 y”。我什至不知道这意味着什么。

有谁知道如何快速查询上一个问题中的正方形列表？我想这个问题的答案取决于它的存储方式。

第三个问题让我想起了在不对应于网格元素质心的“示踪剂”坐标处求解欧拉方程，但在那种情况下，我只是找到了最近的邻居并在那里输出了解。但是，不要认为这就是这里想要的答案。