微软技术专访:Matrix Algorithm

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

面试官问我:

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

2. 一旦纠正,函数foo做什么？请关注功能的结果,而不是实现的细节.

3. 你怎么能让foo变得更通用？解释最多三个可能的泛化方向,并为每个方向描述一个策略,无需编写代码!

我向他提到过:

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

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

Answer 1

你玩过游戏"2048"(游戏链接)吗？如果没有,这个问题可能对你没那么直观,因此,我认为这是一个糟糕的面试问题.

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

注意:这不是2048游戏的一个步骤,因为数字只向上移动一个单元格,而在游戏中它们"一直"移动直到它们击中其他东西.要获得2048游戏的一个步骤,您将重复给定的功能,直到不再发生更改.

正如您所提到的,代码中的问题是数组索引越界.它应该通过迭代来修复x = 0 to 2.

为了使这更加通用,你必须具有创造性:

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

至于你的这部分答案:

整数矩阵不能有空值,默认情况下它们被赋值为0,false表示布尔值,null表示引用类型

这在很大程度上取决于所使用的语言,所以我不会说这是伪代码中的错误(不应该是任何特定语言).例如,在弱类型语言中,您当然可以使用矩阵int和NULL值.

你没有提到你对函数行为的看法.如果我是面试官,我会希望看到有人"大声思考"并至少意识到以下情况:

• 代码试图将每个元素与它下面的元素进行比较.
• 除非下部元素是,否则什么都不会发生NULL.
• 如果两个元素相等,则较低的元素被替换,NULL并且上元素变为两倍大.
• 如果顶部元素是NULL,那么较低的非NULL元素"移动"到顶部元素的位置.

通过阅读源代码,可以直接获得有关代码的这些观察结果.你是否理解这些"规则"并注意到它(类似于)2048游戏在很大程度上取决于你之前是否玩过游戏.