Я писал в блоге в прошлом об интересных вопросах, которые мне задавали во время интервью, и как на них отвечать.

В этом посте я хочу обсудить популярный вопрос интервью и как на него ответить. Причина, по которой я хочу поговорить об этом конкретном вопросе, заключается в том, что алгоритм, используемый для его решения, очень похож на то, как человек подошел бы к той же проблеме.

Вопрос

Вопрос следующий:

Допустим, у вас есть длинная строка текста со множеством круглых скобок, вложенных друг в друга (например, очень длинная программа LISP). Вы хотите убедиться, что предложение отформатировано правильно и что каждая открытая скобка имеет соответствующую закрывающую скобку.

Прежде чем я напишу решение в коде, давайте немного подумаем о том, как мы, люди, подойдем к этой проблеме.

Разумным подходом было бы подсчитать все открывающие круглые скобки и все закрывающие скобки и убедиться, что числа совпадают.

Давайте попробуем это в JavaScript:

function parenthesesChecker(text) {
  var open = 0
  var close = 0
  for(i = 0; i < text.length; i ++) {
    if(text[i] === "(") {
      open += 1
    } else if(text[i] === ")") {
      close += 1
    }
  }
  return open === close
}

Давайте рассмотрим этот код построчно.

Первым делом мы объявляем две переменные с именами open и close и устанавливаем для них значение 0.

Затем мы перебираем текст и для каждой открытой круглой скобки, которую мы обнаруживаем, увеличиваем значение open на 1, а для каждой закрывающей круглой скобки мы увеличиваем значение close.

Наконец, мы проверяем, совпадают ли значения для open и close. Если они есть, мы возвращаем true, иначе мы возвращаем false.

Простой.

Это работает?

Давайте проверим алгоритм на нескольких тестовых строках, чтобы убедиться, что он работает.

Начнем с самого простого: "()"

У нас есть одна открытая скобка и одна закрытая, которые возвращают true. Идеально.

"()()()" также возвращает true.

Давайте попробуем использовать вложенные круглые скобки: "((()))", "(()())", "(()(()))" все вернут true.

Теперь давайте посмотрим на некоторые плохие строки и посмотрим, все ли они возвращают false: "(", "(()", "(())()((" все возвращают false, как должны.

Но затем мы сталкиваемся с некоторыми проблемами: ")(" "(()))(" return true, даже если они плохо отформатированы. Число открытых и закрытых скобок одинаковое, но они либо начинаются закрывающей скобкой, либо заканчиваются открывающей скобкой.

Мы могли бы добавить оператор if, чтобы проверить первую и последнюю круглые скобки, но как насчет этого случая: "())(()"? Первая и последняя круглые скобки допустимы, количество открывающих и закрывающих скобок одинаковое, но это все равно плохая строка.

Нам нужен новый подход.

Давайте еще раз подумаем, как бы мы, люди, взглянули на этот вопрос? Лучше всего вместо подсчета открытых и закрытых скобок отслеживать, сколько скобок осталось открытыми. Итак, мы проходим предложение, каждый раз, когда доходим до открытой круглой скобки, мы говорим «это одна открытая», «это две открытых» и т.д. «Нет открытия» и т. Д. Если мы когда-либо опустимся ниже нуля, мы знаем, что у нас проблемы, а если мы дойдем до конца, оставив круглые скобки открытыми, мы узнаем, что у нас тоже проблемы.

Как это будет выглядеть в JavaScript? Очень похоже на нашу последнюю функцию:

function parenthesesChecker(text) {
  var open = 0
  for(i = 0; i < text.length; i ++) {
    if(text[i] === "(") {
      open += 1
    } else if(text[i] === ")") {
      open -= 1
    }
    if(open < 0)
      return false
  }
  return open === 0
}

Единственное отличие состоит в том, что вместо отслеживания двух переменных, open и close, мы отслеживаем только одну переменную с именем open. Когда мы достигаем открытой круглой скобки, мы увеличиваем нашу переменную open, а когда мы достигаем закрывающей скобки, мы уменьшаем ее. Если значение open когда-либо опускается ниже 0, мы автоматически возвращаем false, а если в конце это что-то ДРУГОЕ, кроме 0, мы также возвращаем false.

Это решение работает во всех случаях. Если я что-то пропустил, уверен, вы укажете на это в комментариях.