algorithm - 微软技术面试 : Matrix Algorithm

Question

我最近接受了一次面试，面试官给了我一些伪代码并提出了相关问题。不幸的是，由于准备不足，我无法回答他的问题。由于时间关系，我无法向他请教该问题的解决方案。如果有人可以指导我并帮助我理解问题，以便我可以改进 future ，我将不胜感激。下面是伪代码:

A sample state of ‘a’: 
[[   2, NULL,    2, NULL], 
 [   2, NULL,    2, NULL], 
 [NULL, NULL, NULL, NULL], 
 [NULL, NULL, NULL, NULL]]

FUNCTION foo()
  FOR y = 0 to 3 
    FOR x = 0 to 3
      IF a[x+1][y] != NULL
        IF a[x+1][y] = a[x][y]:
          a[x][y] := a[x][y]*2
          a[x+1][y] := NULL
        END IF
        IF a[x][y] = NULL
          a[x][y] := a[x+1][y]
          a[x+1][y] := NULL
        END IF
      END IF
    END FOR
  END FOR
END FUNCTION

面试官问我:

1. 上面的代码有什么问题，我该如何解决？

2. 修正后，函数 foo 有什么作用？请关注函数的结果，而不是实现的细节。

3. 如何让 foo 更通用？解释最多三个可能的泛化方向并描述每个方向的策略，无需编写代码!

我跟他提过:

• 矩阵的状态看起来不正确，因为整数矩阵不能有空值。默认情况下，它们被分配为 0， bool 值被分配为 false，引用类型被分配为 null。
• 上述代码的另一个问题是在IF a[x+1][y] != NULL，当x时，该条件将产生数组索引越界错误 等于 3。

但我觉得面试官在我的回答中寻找其他东西，对解释不满意。

Answer 1

你玩过“2048”游戏(link to game)吗？如果不是，这个问题对您来说可能没有多少直观意义，因此，我认为这是一个糟糕的面试问题。

它试图做的是模拟 2048 游戏中数字向上的一步。数字将向上移动一个单元格，除非它们碰到另一个数字或矩阵边界(想想重力将所有数字向上拉)。如果这两个数字相等，则它们合并并产生一个新数字(它们的总和)。

注意:这不完全是 2048 游戏的一个步骤，因为数字只会向上移动一个单元格，而在游戏中它们会“一直”移动直到碰到其他东西。要获得 2048 游戏的一步，您需要重复给定的函数，直到不再发生任何变化。

如您所述，代码中的问题是数组索引越界。它应该通过遍历 x = 0 到 2 来修复。

要使其更通用，您必须有创意:

1. 主要概括是它应该采用“方向”参数。 (同样，如果您自己没有玩过 2048 游戏，您就不会知道这一点。)重力不会将数字向上拉，而是可以将数字拉向 4 个主要方向中的任何一个方向。
2. 也许算法不应该检查 NULL 但应该检查其他一些标记值(这是另一个输入)。
3. 将其推广到更大的矩阵也很容易。
4. 也许应该有一些其他规则来规定数字何时组合，以及它们组合的精确程度(不一定是第一个的 2 倍)。这些规则可以以 lambda 的形式给出。

---

关于这部分的回答:

integer matrix cannot have null values, by default they are assigned 0, false for Boolean and null for the reference type

这在很大程度上取决于所使用的语言，因此我不会说这是伪代码中的错误(不应使用任何特定语言)。例如，在弱类型语言中，您当然可以拥有一个包含 int 和 NULL 值的矩阵。

---

您没有提及您所说的有关函数行为的内容。如果我是面试官，我希望看到某人“大声思考”并至少意识到以下几点:

• 代码试图将每个元素与其下方的元素进行比较。
• 除非下层元素为 NULL，否则不会发生任何事情。
• 如果两个元素相等，则将较低的元素替换为 NULL，并且较高的元素变为两倍大。
• 如果顶部元素为 NULL，则较低的非 NULL 元素“移动”到顶部元素的位置。

只需阅读源代码即可直接获得有关代码的这些观察结果。您是否理解这些“规则”并注意到它(类似于)2048 游戏在很大程度上取决于您之前是否玩过该游戏。