Предисловие

Для начала стоит прояснить что я не просто так от нечего делать открыл 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. Давайте для начала несколько примеров от простого к сложному.

  1. 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

  1. 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

  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):

  1. Сначала нужно создать все комбинации (для этого у нас уже есть NDimDecay).

  2. Затем нужно отсеять все неподходящие значения. Изначально мы предполагаем что 1 это открывающая скобка и 0 закрывающая. Представим себе некий уровень. Открывающая скобка его поднимает а закрывающая опускает. Если учесть что скобки должны быть всегда сбалансированы то уровень не должен падать ниже 0 на любой итерации. Если после всех итераций уровень в нуле то количество скобок сбалансировано. Если же значение уровня положительно то осталась незакрытая скобка.

  3. И далее самое простое - заменить 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 я не мог решить довольно долго.

Заключение

Я по-прежнему считаю что собеседования должны быть открытым диалогом, но вынужден подстраиваться под рынок. Ещё лет шесть назад можно было спокойно отказаться и искать работодателя, которому ты интересен. Сейчас выбирать не приходится - работы мало, кандидатов много. Значит пора принять реальность и делать ровно то, что ожидает интервьювер. А ожидает он зачастую лишь точного ответа и желательно того самого, который сам же и заготовил и такого же точно решения задачи. В такой ситуации требовать человеческого отношения и уважения к собеседнику становится всё труднее - слишком многие кандидаты рисуют опыт, пользуются наставниками, готовыми списками вопросов и ИИ. Это не оправдывает неуважение, но объясняет почему живой диалог просто блажь.