未分類
30 8 月 2020

分享另一道巨硬家面试题（中等难度，非编程）

分享另一道巨硬家面试题（中等难度，非编程）

資深大佬 : 0x4F5DA2 11

看到有人分享巨硬家面试题，我也来分享一个

背景：

这是一个两个人进行的游戏，后面称两人为 A 和 B 。

有四枚硬币，摆成一个正方形，初始状态正反面随机。A 看不到硬币的状态，B 能看到硬币状态并进行操作。A 能向 B 发出四种操作指令和一种查询指令：

操作指令： 1. 将一行硬币翻转 180 度（翻转哪一行由 B 决定） 2. 将一列硬币翻转 180 度（翻转哪一列由 B 决定） 3. 将一个对角线的硬币翻转 180 度（翻转哪一对角线由 B 决定） 3. 将所有硬币翻转 180 度

查询指令： 1. 所有硬币是否处于全是正面的状态（ B 回答是或者否）

问题：

假如你是 A，给出一个长度小于 20 的指令序列，使得所有硬币均为正面。

大佬有話說 (28)

  • 資深大佬 : undeflife

    有点像在文曲星上玩的猜数字.

  • 資深大佬 : Raven316

    我是不是理解错了，假如一开始 1 个正面，3 个反面，那么无论怎么翻不都是 1 个或者 3 个正面吗？

  • 主 資深大佬 : 0x4F5DA2

    @undeflife 有点像吧，但是那个没有这个难（

  • 資深大佬 : gccdchen

    @Raven316 我也是这么想,反面数量是单数的话,每次指令都是双数..应该是做不了.
    但是如果要考虑题目是双数的情况呢?

  • 主 資深大佬 : 0x4F5DA2

    @Raven316 啊，抱歉，老早之前去面巨硬的时候的题，记忆出了点偏差。还有一个操作是翻转一个硬币（翻转哪一个由 B 决定）

  • 主 資深大佬 : 0x4F5DA2

    @gccdchen 抱歉记忆出了偏差，漏了一个操作。具体见五

  • 資深大佬 : hejw19970413

    应该三种情况 如果 得一种情况走完需要 还原 最初始状态，然后进行回溯。也可以理解成深度优先遍历

  • 資深大佬 : widewing

    四种情况：a.全正，b.全反，c.两正两反，d.一正三反。
    1.首先查询，验证 a
    2.全翻转，查询，验证 b
    3.从左上分别按行，列，对角翻转并查询，验证 c
    4.随机翻转后重复 3 验证 d

  • 資深大佬 : Raven316

    目前只能一个 31 步的，首先 B 是随机翻转，而翻转 1 行等于翻转 2 行+全翻转，所以翻转行后必须：确认+全翻转+确认。列和对角线类似。

    而必须先确定是单数还是双数。所以先假定为双数。

    如果为双数：

    分为 4 种情况：（ 1 ）全翻转或者不翻就行（ 2 ）翻行（ 3 ）翻列（ 4 ）翻对角线

    第一步确认（ 1 ）：
    执行步骤：1 确认 2 全翻转 3 确认
    然后确认（ 2 ）：
    4 翻行 5 确认 6 全翻转 7 确认
    然后确认（ 3 ）：
    因为已经翻了行，所以这时一开始的对角线变成了列，列变成了对角线
    8 翻列 9 确认 10 全翻转 11 确认
    这时如果是双数，那么肯定是对角线
    12 翻对角线 13 确认 14 全翻转 15 确认

    这是已经确定是单数正面
    16 翻单个
    接下来必定是双数，所以套用上面 15 步，总共 31 步一定是全正面。。。

    能力所限

  • 資深大佬 : widewing

    @widewing 修正：
    d.一正三反或三正一反
    4. 随机翻转后重复 123 验证 d

  • 資深大佬 : Raven316

    @Raven316 所以如果在 20 步以内，双数翻转到全正必须在 9 步或者 9 步以内

  • 資深大佬 : threebr

    硬币有 2^4=16 种状态，而 A 只能确认是否处于 1 种状态，所以 A 只能枚举各种不同的状态并一一确认，转换不同的状态至少需要 1 个操作指令，如果查询指令也算 1 个长度的话，考虑最坏情况至少需要 31 个指令（ 16 次查询和 15 次操作）。

    不知道我的思路有什么问题

  • 資深大佬 : alan0liang

    @Raven316 和 #9 思路一样，能优化到 24 步：删掉 #9 中 567，最后一步不用确认一定是全正面，一共删掉 7 步，31-7=24

  • 資深大佬 : threebr

    @Raven316 哈哈哈哈哈你找出了一个 31 步的方法，我推断指令应该大于等于 31，那答案不就是 31 了吗

  • 資深大佬 : alan0liang

    @threebr 参考 #13 的优化，不一定需要挨个枚举所有状态，可以想办法合并之后一次确认两种情况甚至多种情况。

  • 資深大佬 : Raven316

    @threebr 思路很牛，我也觉得好像做不到

  • 資深大佬 : CrazyEight

    如果是全反或全正就赢那还好想一些，全正的情况太多了

  • 資深大佬 : alan0liang

    不对

  • 資深大佬 : Raven316

    @Raven316 错了 12 步改成翻行

  • 資深大佬 : threebr

    @alan0liang 没懂为什么可以删掉 #9 567，不过最后一步的确不用确认，30 步就可以

  • 資深大佬 : Raven316

    @0x4F5DA2 主快粗来公布答案了

  • 資深大佬 : ryd994

    看来国内微软很难进啊

  • 資深大佬 : ziwiwiz

    查询 反转 查询
    行 查询 反转 查询
    列 查询 反转 查询
    行 查询 反转 查询
    单转
    重复以上
    （ 3+4*3 ）* 2 +1-1 = 30

  • 資深大佬 : wshhfy

    我这种水平只能坐等答案了

  • 資深大佬 : cassyfar

    这是图论吧。按照四种状态，全正，全反，一正三反，三正一反，二正二反，二正二反（对角）有 6 个点。然后全正是终点。根据操作连边，是 bi-direction 。求一种解法，10 步内，从任何点开始都能走到全正这个终点。没走一步，可以查询一次。

  • 資深大佬 : alan0liang

    似乎能分类讨论证 #12 的结论，即至少 30 个指令，大概思路是这样：把所有状态分成 front, back, horizontal, vertical, diagonal, odd 这几种状态，front 和 back 统称 all
    0. 显然任何指令重复两遍没意义
    1. 查询指令如果不与 4 相邻则没意义
    2. 4 之后除非直接结束否则只要不跟着查询就没意义
    3. 所以「查询 4 查询」必然作为一个整体出现(除了最后)，把它叫 A
    4. 1/2 之后如果不跟着 A 则没意义
    5. odd 状态和其他没什么关系，只能通过 5 转化成 ahvd 之一，而 ahvd 转换成 odd 就更没意义了
    6. 所以 #9 就是最优解
    中间有好多跳步，但是写出来太长了……
    期待打脸

  • 資深大佬 : freelancher

    这个是一个算法题。

    四个硬币是 0.5 机率有正面或者反面。全正是 1/8 。全反是 1/8.

    每进行翻转一次。查询一次。

    第一步，先查询全状态。运气好就直接 OK 了。

    然后用排除法的思路。翻一个对角线。查询，这个应该让数学的来答会好点。应该是有解法的。

  • 資深大佬 : tsaohai

    哎哟卧槽 这题我还真被面过