gpt4 book ai didi

algorithm - 微软技术面试 : Matrix Algorithm

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:29:10 27 4
gpt4 key购买 nike

我最近接受了一次面试,面试官给了我一些伪代码并提出了相关问题。不幸的是,由于准备不足,我无法回答他的问题。由于时间关系,我无法向他请教该问题的解决方案。如果有人可以指导我并帮助我理解问题,以便我可以改进 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

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

最佳答案

你玩过“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

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


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

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

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

关于algorithm - 微软技术面试 : Matrix Algorithm,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50338479/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com