Как я решал leetcode задачу
Для начала стоит прояснить что я не просто так от нечего делать открыл leetcode и начал решать задачки. Такое решение пришло после не очень удачных собеседований, задачи на которых я хоть и решил, но со скрипом и потратив гораздо больше времени чем рассчитывал интервьювер. Конечно же это не удовлетворило его, особенно учитывая большую плотность кандидатов на должность.
Сам же я давно в IT и в том числе проводил много собеседований, стараясь избегать leetcode задач, просто потому что считал что они не показывают реальных возможностей и потенциала человека. Однако попробуй доказать подобное на собеседовании в крупную IT компанию, разговор в которой начинается с “итак давайте перейдём к лайв-кодингу”. Ну так в лучших традициях давайте перейдём непосредственно к кодингу.
Задача
Собственно сама задача:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
Constraints:
1 <= n <= 8
Если множество других задач я худо-бедно решал, пускай и не всегда за условные 30-40 минут, то эту задачу я с ходу не смог решить вообще никак, потому как про этот самый backtracking слыхом не слыхивал. И т.к. мне хотелось найти подход самому, без подсказок, то это вылилось в несколько дней поисков решения.
Поиск решения
Первой интуитивной догадкой было перебрать все возможные комбинации и потом отсеять неподходящие. Если в отсеивании всё довольно тривиально, то вот перебор всех комбинаций не так просто дался. Давайте попробуем использовать вложенные циклы - их понадобится N штук под каждую позицию которую перебираем. Например нам нужно перебрать под 3 позиции 3 элемента. Получится 3^3 (333) комбинаций. И чтобы их получить нужно расписать три вложенных цикла:
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
for k := 0; k < 3; k++ {
t.Log(i, j, k)
}
}
}
Если для заранее известного количества позиций это решение может вполне подойти то для динамического точно так не пройдёт. Как же тогда быть?
Ещё день я пребывал в раздумьях по поводу экзистенциальности бытия и стараясь отбросить самокритичные мысли я просто пытался представить себе процесс перебора комбинаций и понять как его автоматизировать. Также вспомнилось что мы проходили по информатике, а именно позиционные системы счисления с разными основаниями.
Представим себе что мы перебираем ровно 10 значений в N позиций. Напоминает обычный десятичный счёт. А что если значений 2 (как в нашем случае) то получается двоичный счёт. Если все значения можно просто пересчитать, учитывая выбранную систему счисления, то нужно просто понять максимальное количество значений и саму систему счисления. В позиционной системе счисления затем достаточно выделить каждую позицию - это и будет решением, точнее всеми возможными комбинациями. До самого решения нужно ещё проделать некоторые подсчёты о которых позже.
Для вычисления значения на каждой позиции (разложения по базису) просто используем деление по модулю и дополнительно целочисленное деление для отбрасывания остатка. Ну например для числа 789 нужно выделить число на второй позиции: (789 % 100)/10 = 8. Давайте для начала несколько примеров от простого к сложному.
3 позиции 10 значений. Всего значений 10^3=1000
for i := range 1000 {
t.Log((i%1000)/100, (i%100)/10, i%10)
}
0 0 0
0 0 1
0 0 2
...
9 9 8
9 9 9
3 позиции 2 значения (двоичная система счисления). Всего значений 2^3=8
for i := range 8 {
t.Log((i%8)/4, (i%4)/2, i%2)
}
0 0 0
0 0 1
0 1 0
...
1 1 0
1 1 1
3 позиции 3 значения (троичная система счисления). Всего значений 3^3=27
for i := range 27 {
t.Log((i%27)/9, (i%9)/3, i%3)
}
0 0 0
0 0 1
0 0 2
...
2 2 1
2 2 2
И т.д. Если попробовать представить себе решение этой задачи в геометрическом виде то получается что мы перебираем пространство всех решений N-мерного куба где мерность выбирается количеством позиций (базисом системы).
Теперь обобщим все данные и напишем решение для перебора всех комбинаций для N позиций при заданном количестве значений (это потребовало времени и отладки):
func NDimDecay(q int, n int) [][]int {
c := int(math.Pow(float64(q), float64(n)))
res := make([][]int, c)
for i := range c {
next := make([]int, n)
s := c
for j := 0; j < n; j++ {
next[j] = i % s / (s / q)
s /= q
}
res[i] = next
}
return res
}
Здесь q - количество значений (основание системы), n - количество позиций (базис системы или мерность куба). На выходе мы получаем массив массивов всех комбинаций. Например:
t.Log(NDimDecay(2, 3))
0 0 0
0 0 1
0 1 0
...
1 1 0
1 1 1
Хорошо, перебирать все комбинации мы научились. Теперь осталось решить задачу. Возьмём первый пример из исходной задачи как опорный. У нас всего 2 значения (открывающая и закрывающая скобка) для перебора и 6 позиций (n = 3, n*2):
Сначала нужно создать все комбинации (для этого у нас уже есть
NDimDecay).Затем нужно отсеять все неподходящие значения. Изначально мы предполагаем что 1 это открывающая скобка и 0 закрывающая. Представим себе некий уровень. Открывающая скобка его поднимает а закрывающая опускает. Если учесть что скобки должны быть всегда сбалансированы то уровень не должен падать ниже 0 на любой итерации. Если после всех итераций уровень в нуле то количество скобок сбалансировано. Если же значение уровня положительно то осталась незакрытая скобка.
И далее самое простое - заменить 1 и 0 на соответствующие скобки и создать результирующие строки:
func generateParenthesis(n int) []string {
// создаём все комбинации
nd := NDimDecay(2, n*2)
res := make([][]int, 0, len(nd))
var lvl int
// отсеиваем неподходящие комбинации
for _, r := range nd {
lvl = 0
for _, v := range r {
if lvl < 0 {
break
}
if v == 1 {
lvl++
} else {
lvl--
}
}
if lvl == 0 {
res = append(res, r)
}
}
resStr := make([]string, 0, len(res))
// и делаем замену 1/0 на скобки с преобразованием в строку
for _, r := range res {
st := strings.Builder{}
st.Grow(len(r))
for _, s := range r {
if s == 1 {
st.WriteRune('(')
} else {
st.WriteRune(')')
}
}
resStr = append(resStr, st.String())
}
return resStr
}
Копируем код на площадку leetcode и убеждаемся что всё работает.
В целом подход конечно не из тех что можно по-быстрому вывести. И потому я начал искать другие, более подходящие для формата собеседований варианты. Придумал ещё вариант перебора через стек, но он по сути был тем же самым решением только с формальным использованием стека.
Рекурсивное решение
Поняв что больше идей нет я всё же разузнал как решаются подобные задачи по простому. И вот решение в рекурсивном стиле которое у меня получилось:
func backtrack(res *[]string, st string, n int, lvl int) {
if len(st) == 2*n {
if lvl == 0 {
*res = append(*res, st)
}
return
}
if lvl < 0 {
return
}
backtrack(res, st + "(", n, lvl+1)
backtrack(res, st + ")", n, lvl-1)
}
func generateParenthesis(n int) []string {
res := []string{}
backtrack(&res, "", n, 0)
return res
}
Оно не лучшее, но оно работает и на глубине до n = 8 вполне подходит. Касаемо сложности очевидно что нерекурсивное решение менее эффективно, просто потому что перебирает вообще все комбинации не отсекая изначально заведомо ложных, но мне понравился сам подход и его наглядность. Не хотелось доводить его до нечитаемого состояния оптимизациями. Рекурсивное решение тоже можно оптимизировать при желании.
И вот вопрос - почему сразу не через рекурсию ? Долго пытался для себя понять почему такой простой и понятный способ мне так и не пришёл на ум. Наверное всё-таки дело в том что рекурсивные методы я никогда не использовал в реальной работе и за долгие годы они так и остались чем-то исключительно академическим. А знания без опыта тяжело поднимаются в памяти.
Немного личных размышлений
Ни в коем случае не хочу сказать что подобные задачи бессмысленны. Они позволяют разработчикам площадки leetcode кушать свой хлеб ну и в целом имеют общеукрепляющий эффект. Но что именно они проверяют в кандидате ? Знание конкретных специфичных подходов или даже скорее убедят в том что кандидат заходил на leetcode ? Вспомните, часто вам приходилось через два курсора перебирать массив на работе ? Использовал ли я подобные рекурсивные подходы в реальной работе хоть раз ? Риторический вопрос. А вот умение сосредоточиться и вникнуть в задачу всегда помогало. Но раз эта практика так устоялась, то что поделаешь, приходится подстраиваться. Хотя я всё ещё убеждён что каждое собеседование должно быть открытым диалогом.
Потому я лично на собеседованиях больше прошу людей рассуждать и объяснять свою позицию. И если уж и заставлять лайф-кодить то только с целью выяснения понимания конструкций конкретного языка и в целом логики. Кандидат может не расписать конкретное точное решение но при этом знать как решить или хотя бы в какую сторону думать и в дальнейшем раскрыть свою позицию, возможно с подсказками. Но когда тебя просто садят перед задачей да ещё и в голом блокноте и засчитывается конкретное точное решение, когда малейшее расхождение и задание считается невыполненным просто ставит в тупик. Мы же не ходячие компиляторы/интерпретаторы. Да и в эпоху ИИ подобные навыки весьма сомнительны.
Отдельное недоумение вызывают собеседования когда тебя рассматривают не в конкретную команду, а просто “щупают” (здравствуйте 3-6 этапов включая легендарный систем дизайн) и потом предлагают в команды, где ты ещё должен понравиться лично этой самой команде. Для себя просто спрашиваю сразу в какую конкретно команду меня рассматривают и если речь идёт о смотринах - сразу отказываюсь. Это прямо какое-то неуважение к кандидату. Особенно учитывая что я больше нигде кроме IT такого подхода не наблюдал, да и то только в компаниях которые считают строчку в резюме от них благословением.
Стоит ещё отметить что я так и не понял до конца систему распределения сложности задач на leetcode. Так например некоторые задачи с уровнем hard мне давались буквально за полчаса, в то же время некоторые задачи уровня easy я не мог решить довольно долго.
Заключение
Я по-прежнему считаю что собеседования должны быть открытым диалогом, но вынужден подстраиваться под рынок. Ещё лет шесть назад можно было спокойно отказаться и искать работодателя, которому ты интересен. Сейчас выбирать не приходится - работы мало, кандидатов много. Значит пора принять реальность и делать ровно то, что ожидает интервьювер. А ожидает он зачастую лишь точного ответа и желательно того самого, который сам же и заготовил и такого же точно решения задачи. В такой ситуации требовать человеческого отношения и уважения к собеседнику становится всё труднее - слишком многие кандидаты рисуют опыт, пользуются наставниками, готовыми списками вопросов и ИИ. Это не оправдывает неуважение, но объясняет почему живой диалог просто блажь.
KioskNews shows a cleaned-up reading view extracted from the publisher’s page — the original always lives on their site, not ours.