Техническое интервью Microsoft: матричный алгоритм

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. Условие будет приводить к ошибке индекса массива вне пределов, когда x равно 3.

Но я чувствовал, что интервьюер искал что-то еще в моем ответе и не был удовлетворен объяснением.

Answer 1

После исправления, что делает функция foo?Пожалуйста, обратите внимание на результат функции, а не на детали реализации

Вывод будет:

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

Answer 2

Вы играли в игру "2048" ( ссылка на игру )? Если нет, то этот вопрос, скорее всего, не будет иметь для вас особого интуитивного смысла, и поэтому я думаю, что это плохой вопрос для собеседования.

То, что он пытается сделать, это смоделировать один шаг в игре 2048, где числа идут вверх. Числа будут перемещаться вверх на одну ячейку, если они не достигают другого числа или границы матрицы (представьте себе, что гравитация тянет все числа вверх). Если два числа равны, они объединяются и производят новое число (их сумма).

Примечание: это не совсем один шаг в игре 2048, потому что числа перемещаются только на одну клетку вверх, в то время как в игре они движутся «все в одну сторону», пока не столкнутся с чем-то другим. Чтобы пройти этап игры 2048, вы должны повторять данную функцию до тех пор, пока больше не произойдет никаких изменений.

Проблема в коде заключается в том, что, как вы упомянули, индекс массива выходит за пределы. Это должно быть исправлено путем итерации вместо x = 0 to 2.

Чтобы сделать это более общим, вы должны быть креативными:

1. Основным обобщением является то, что он должен принимать параметр "направление". (Опять же, вы бы этого не знали, если бы сами не играли в игру 2048.) Вместо гравитации, вытягивая числа вверх, гравитация может вытягивать числа в любом из 4 основных направлений.
2. Возможно, алгоритм не должен проверять NULL, но должен проверять какое-либо другое значение часового (которое является другим входом).
3. Также довольно просто обобщить это на более крупные матрицы.
4. Может быть, должно быть какое-то другое правило, которое предписывает, когда числа объединяются, и как точно они объединяются (необязательно 2 раза по сравнению с первым). Эти правила могут быть даны в виде лямбд.

---

Что касается этой части вашего ответа:

целочисленная матрица не может иметь нулевые значения, по умолчанию им присваивается 0, ложно для логического значения и ноль для ссылочного типа

Это в значительной степени зависит от используемого языка, поэтому я бы не сказал, что это ошибка в псевдокоде (который не должен быть на каком-либо конкретном языке). Например, в слабо типизированных языках вы можете иметь матрицу со значениями int и NULL.

---

Вы не упоминаете, что сказали о поведении функции. Если бы я был интервьюером, я бы хотел, чтобы кто-то «подумал вслух» и понял, по крайней мере, следующее:

• Код пытается сравнить каждый элемент с элементом под ним.
• Ничего не произойдет, если нижний элемент не будет NULL.
• Если два элемента равны, то нижний заменяется на NULL, а верхний элемент становится в два раза больше.
• Если верхний элемент равен NULL, то нижний не NULL элемент «перемещается» на место верхнего элемента.

Эти замечания о коде просто получить, просто прочитав исходный код. Понимаете ли вы эти «правила» и замечаете ли вы, что это (похоже на) игра 2048 года, во многом зависит от того, играли ли вы в нее раньше.