Я писал в блоге в прошлом об интересных вопросах, которые мне задавали во время интервью, и как на них отвечать.
В этом посте я хочу обсудить популярный вопрос интервью и как на него ответить. Причина, по которой я хочу поговорить об этом конкретном вопросе, заключается в том, что алгоритм, используемый для его решения, очень похож на то, как человек подошел бы к той же проблеме.
Вопрос
Вопрос следующий:
Допустим, у вас есть длинная строка текста со множеством круглых скобок, вложенных друг в друга (например, очень длинная программа 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
.
Это решение работает во всех случаях. Если я что-то пропустил, уверен, вы укажете на это в комментариях.