微软技术面试：矩阵算法

Question

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

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

面试官问我：

以上代码有什么问题，我该如何解决？
改正后，函数foo的作用是什么？请关注函数的结果，而不是实现的细节。
如何使 foo 更通用？最多解释三个可能的泛化方向，并为每个方向描述一个策略，无需编写代码！

我跟他提过：

矩阵的状态看起来不正确，因为整数矩阵不能有空值。默认情况下，它们被分配 0，布尔值分配 false，引用类型分配 null。
上述代码的另一个问题是在IF a[x+1][y] != NULL，当x等于3.

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

Answer 1

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

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

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

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

要使这个更通用，您必须要有创意：

主要概括是它应该采用 "direction" 参数。（同样，如果您自己没有玩过 2048 游戏，您就不会知道这一点。）重力可以将数字拉向 4 个主要方向中的任何一个，而不是将数字向上拉。
也许算法不应该检查 NULL 但应该检查其他标记值（这是另一个输入）。
将其推广到更大的矩阵也很容易。
也许应该有一些其他规则来规定数字何时组合，以及它们组合的精确程度（不一定是第一个的 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 值的矩阵。

你没有提到你所说的关于函数行为的内容。如果我是面试官，我想见一个人 "think out loud" 并至少意识到以下几点：

代码试图将每个元素与其下方的元素进行比较。
除非下部元素是 NULL，否则什么也不会发生。
如果两个元素相等，则将较低的元素替换为 NULL，并且较高的元素变为原来的两倍。
如果顶层元素是NULL，那么下层非NULL元素"moves"到顶层元素的位置。

这些关于代码的观察很容易通过阅读源代码获得。您是否理解这些 "rules" 并注意到它（类似于）2048 游戏很大程度上取决于您之前是否玩过该游戏。

Answer 2

Once corrected, what does function foo do? Please focus on the result of the function, not the details of the implementation

输出将是：

4 null 4 null
null null null null
null null null null
null null null null

Answer 3

这是同一程序的 python 代码。我已经修复了这段代码中的索引越界问题。希望这有帮助。

null = 0
array = [[2,null,2,null],[2,null,2,null],[null,null,null,null],[null,null,null,null]]
range = [0,1,2]
for y in range:
   for x in range:
       if array[x+1][y] != null:
           if array[x+1][y] == array[x][y]:
               array[x][y] = array[x][y]*2
               array[x+1][y] = null
           if array[x][y] == null:
               array[x][y] = array[x+1][y]
               array[x+1][y] = null
print(array)

微软技术面试：矩阵算法

Microsoft technical interview: Matrix Algorithm

algorithm

pseudocode

matrix