Как я решал leetcode задачу

[nurix]

Хороший разбор, круто, что вы честно показали путь к решению, а не только финальный код:)
Пара мыслей:

for mask := 0; mask < 1<<(2*n); mask++ {
    lvl := 0
    for j := 2*n - 1; j >= 0 && lvl >= 0; j-- {
        if mask>>j&1 == 1 { lvl++ } else { lvl-- }
    }
    // lvl == 0 → маска валидна
}

Для n = 8 это 65 536 вариантов, из которых подходят только 1 430 (число Каталана C8), так что перебор с фильтрацией вполне жизнеспособен на этих ограничениях.

if open < n  { backtrack(..., open+1, close) }
if close < open { backtrack(..., open, close+1) }

Тогда ни одна ветка не уходит в тупик, и каждая дошедшая до длины 2n строка - сразу ответ, без проверки в конце.

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

[Chemist_modeler]

Использовал ли я подобные рекурсивные подходы в реальной работе хоть раз ? Риторический вопрос.

В обычных задачах для бизнеса, видимо, в этом нет большого смысла - цена ошибки в рекурсии слишком велика.

А вот в решении научных задач рекурсия используется довольно часто. Одна из причин, но не единственная, - это привычка довольно многих ученых упрощать уравнения, которые с рекурсией нередко выглядят сильно короче и "красивше", и переделывать такое уравнение в обычное - чревато ошибкой. А иногда рекурсия в разы и более ускоряет вычисления.

Мне как-то пришлось руками писать функцию для быстрой сортировки - было это давно... Особенность была в том, что массив, хотя и был довольно большим, обычно содержал очень много одинаковых или почти одинаковых значений. В типе float это "почти" может казаться критически важным для точного различения, но на самом деле это не нужно было: достаточно было разделить массив на кластеры так, чтобы в каждом кластере разница значений не превышала определенной величины, и потом тупо слить их в порядке возрастания средних значений. Решил я эту задачу через рекурсию: сначала дробил массив на крупные кластеры, а потом каждый из них с помощью той же самой функции дробил на более мелкие - до тех пор, пока внутри каждого кластера все значения не становились равными друг другу в пределах заранее заданной "вилки" (скажем, 0.1% от всего диапазона). Ускорило это процесс раз где-то в тысячу или больше, ибо в итоге кластеров оказывалось реально мало.

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

[neon1ks]

Передаю большой привет всем, кто решает задачи дня на leetcode ;)

[pMalice]

Для меня логичным и простым кажется такое рассуждение: скобки уровня N могут либо окружать все комбинации для N-1, либо быть слева, либо быть справа. Тогда решается так:

let n=3;
function comb(n) {
    if (n==1) return ["()"];
    let res=new Set(); // чтобы схлопнулись дубли
    comb(n-1).forEach(
        x=>{
            res.add("(" +x +")");
            res.add("()" +x);
            res.add(x+"()");
        });
return [...res];    
}    
console.log(comb(n));

[Deosis]

для 4 пропадет такой вариант: (())(())

[pMalice]

Хм… правда. Логичный и простой алгоритм оказался неверным ) Попытка исправить приводит к такому рассуждению: каждую новую пару скобок надо вставить во все возможные позиции предыдущих перестановок. Тогда решение такое:

function comb(n) {
    if (n==0) return [""];
    let res=new Set(); 
    for (const x of comb(n - 1)) {
        for (let i = 0; i <= x.length; i++) {
            res.add(x.slice(0, i) + "()" + x.slice(i));
        }
    }
    return [...res];    
}

Тоже выглядит как костыль )

[wataru]

Правильное рассуждение выводится из определения в условии. Или у вас n-1 скобка внутри новой пары. Или у вас сначала комбинация из k пар, неразрывная, а потом комбинация из n-k пар. Чтобы первая была неразрывная, она должна быть обрамлена парой скобок. Или еще логичнее: любая комбинация из n скобок - это (), внутри которой комбинация из 0<=k<=n пар скобок, а потом комбинация из n-k-1 скобок.

[lightln2]

По-моему, тут рекурсия сама собой получается:

Рассмотрим первую скобку: очевидно, она открывающая. Где будет ее закрывающая скобка? В какой-то позиции через четное число скобок от нее. Также очевидно, что между ними, а также после закрывающей скобки - тоже правильные скобочные последовательности длины 2i и 2(n-i-1).

Сгенерим все такие последовательности рекурсивно.

Кстати, рекуррентная формула для чисел каталана из этого принципа и выводится.

@cache
def generate(n):
    if n == 0: return [""]
    result = []
    for i in range(n):
        for x in generate(i):
            for y in generate(n - i - 1):
                result.append(f"({x}){y}")
    return result

[capslocky]

При построении строки мы делаем последовательные решения: открыть или закрыть скобку. Это образует дерево решений с 2N уровнями, а деревья удобно обходить через рекурсию. 

Из моего опыта, для таких интервью достаточно освоить около 10 структур (tree, linked list, hashset, hashmap, stack, queue ...) и около 10 алгоритмов (two pointers, prefix sum, binary search, dfs ...) Но чтобы их уверенно применять нужно решить больше сотни популярных задач (Blind75, Neetcode150), и при этом научиться быстро распознавать в новых.

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

PS. я сам не особо любитель литкода, но пришлось научиться решать такие задачи.

[Mr_Makadamia]

Ваш подход:

...лично на собеседованиях больше прошу людей рассуждать и объяснять свою позицию...

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

Как-то на одном известном ресурсе, попробовал пройти тестовое задание на go, было 2 задачи, обе на сортировку... ничего сложного, но само решение именно для go было крайне громоздким, то есть решили не "париться", и, даже, не адаптировали ее, просто, "скопипастили"... это говорит о том, что в компании нет системы и автоматизации в сфере управления персоналом. Коммуникация и контроль отсутсвуют. Казалось бы, перед глазами дворец с позолоченными статуями на входе, лепнина, фонтаны, фуагра... а по факту внутри изба со скрипучими полами, и удобствами на улице. Классическое : ожидание / реальность. ) ... со всеми вытекающими... однако "ничего страшного"// тяу-тяу-тяу...(не удержался)) не произошло. В любом случае оборачиваю подобные ситуации в мотивацию. Просто, реально, бывало, ощущал себя как и Вы с этой задачей. Крутяк.

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

просто имхо, мини-рефлексия на тему.

Нет плюсов для расчихления плюсомёта, поэтому поддержка в комментах.)

Добра.

[wataru]

Еще есть быстрый нерекурсивный метод.

Код (нейрослоп, ибо я на го не пишу)

// nextBalancedSequence transforms the parenthesis slice in-place to the lexicographically next valid one.
// Returns true if a next sequence exists, or false if the current sequence is already the last one.
func nextBalancedSequence(s []byte) bool {
	n := len(s)
	balance := 0

	// 1. Scan from right to left to find the first '(' that can be replaced by ')'
	for i := n - 1; i >= 0; i-- {
		if s[i] == '(' {
			balance--
		} else {
			balance++
		}

		// A '(' can be replaced if moving right-to-left yields a positive balance of closing brackets
		if s[i] == '(' && balance > 0 {
			s[i] = ')'
			balance--

			// 2. Greedily fill the remaining positions to maintain the lexicographically smallest valid suffix
			remLen := n - 1 - i
			openCount := (remLen - balance) / 2
			closeCount := remLen - openCount

			idx := i + 1
			for j := 0; j < openCount; j++ {
				s[idx] = '('
				idx++
			}
			for j := 0; j < closeCount; j++ {
				s[idx] = ')'
				idx++
			}
			return true
		}
	}
	return false
}

// GenerateAllParentheses generates all valid parenthesis strings for n pairs in lexicographical order.
func GenerateAllParentheses(n int) []string {
	if n <= 0 {
		return []string{}
	}

	// Start with the lexicographically first valid sequence: n '(' followed by n ')'
	current := make([]byte, 2*n)
	for i := 0; i < n; i++ {
		current[i] = '('
		current[n+i] = ')'
	}

	var result []string
	for {
		// Append a copy of the current valid string state
		result = append(result, string(current))

		// Find the next lexicographical sequence in-place
		if !nextBalancedSequence(current) {
			break
		}
	}

	return result
}

Можно написать компактнее, но так понятнее идея.

Если решаете задачи на литкоде, то наверняка встречали задачу о перестановках и знакомы с алгоритмом Нарайаны.

Многие комбинаторные объекты можно генерировать похожим образом. Начните с самой лексикографически минимальной строки, потом каждый раз меняйте ее минимальным способом, чтобы получить следующую лексикографически строку. Это надо поменять самый правый символ на чуть больший в алфавите так, чтобы потом строку можно было достроить до валидной. Так же тут. Начните со строки (((((...))))).

Вот что можно поменять в строке, чтобы она стала дальше в словаре? Первый измененный символ должен быть "(", замененный на ")". Обратная замена сделает строку меньше лексикографически. Чтобы эта замена была корректной, баланс (количество незакрытых пока скобок) перед этим символом должен быть больше 0, иначе ")" уйдет в минус. Чтобы изменение было минимально, надо взять самый правый такой символ. Дальше надо достроить строку до минимальной - взяв сначала все "(", потом все ")". Очевидно, что такая строка будет валидной.

Вот пример: начали мы с ((())). Самый правый (, который не на нулевом уровне, это третий символ. Заменив его мы получаем (() и надо оставшиеся скобочки жадно поставить: получаем (()()). Если хотим опять получить следующую строку, самый правый (, который можно заменить - опять третий. Получаем начало (()), дополняем: (())(). Теперь уже третий ( нельзя заменять, он никуда не вложен, заменив второй, получим ()(()).

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

Работает это так же быстро, как самый оптимизированный рекурсивный перебор с отсечениями. У вас отсечений в рекурсии нет, но можно же глядя на баланс понять, можно ли тут ставить ")" или "(" в рекурсии и никогда не доходить до конца с ненулевым балансом.

[boolka989]

Спасибо, уловил суть