2 подписчика
Medium Leetcode на собесах
Я много слышал и видел, что на собесах, где проверяют алгоритмические способности, дают задачки уровня easy с leetcode.
Услышал, подкачался, и перестал фейлить в этой секции на собесах.
Пока мне не попалась задачка medium. Их я тоже решал, но иногда они занимали много времени, и были структурированы так, что в голове не укладывалась полная картина. Особенно, когда находишься не в фокусе, когда даже концепт рекурсии удержать в голове сложно.
Я понял как ее решать с ходу, но наводящими вопросами про "за один проход", "за линейное время" заставили меня сомневаться в моих способностях, в итоге я ее не дорешал за отведенное время.
Споткнулся именно на вложенных кейсах типа "3[a2[c]]" или "3[a2[b2[c]]d".
Первая идея для решения: идем по строке, если наткнулись на буквы - сохраняем их в буфер, если на число, начинаем его запоминать в переменную, а после открытой скобки ищем ее закрывающую скобку и передаем это в рекурсивный вызов, результат которого добавляем в тот результирующий буфер (но она не O(N), т.к. в каждой рекурсии нужно снова перечитывать строку).
После собеса подумал еще, да забил. А сегодня решил решить и снова потратил целый час на написание и дебаг почти-O(N) решения, где закрывающую скобку не ищем, до рекурсивного вызова, а лучше внутри него считаем скобки, и если наткнулись на лишнюю закрывающую - возвращаем результат и позицию.
Сигнатура рекурсивной функции: extract(start int, str string) (result string, stoppedAt int), сначала вызываем ее со start = 0. Внутри str не меняем, всегда передаем дальше исходную. StoppedAt - где мы остановились во внутреннем цикле, а во внешнем надо будет перемотаться на этот символ в строке, чтоб продолжить.
1 минута
21 июля 2023