fun main() {
val n =4
val res = mutableListOf<String>()
tailrec fun add(startList:List<String>){
val l = mutableListOf<String>()
for (start in startList) {
val o = start.count { it == '(' }
val c = start.count { it == ')' }
if (o == c && start.length == 2 * n) {
res += start
} else {
if (o - c < 2 * n - start.length) {
l.add(start +'(')
}
if (o > c) {
l.add(start +')')
}
}
}
if (!l.isEmpty()) add(l)
}
add(listOf(""))
println("4. $res")
}
//4. [(((()))), ((()())), ((())()), ((()))(), (()(())), (()()()), (()())(), (())(()), (())()(), ()((())), ()(()()), ()(())(), ()()(()), ()()()()]
Декомпиляция из байткода, где рекурсия таки развернулась в цикл while:
public final class T1Kt {
public static final void main() {
final int n = 4;
boolean var2 = false;
final List res = (List)(new ArrayList());
<undefinedtype> $fun$add$1 = new Function1() {
// $FF: synthetic method
// $FF: bridge method
public Object invoke(Object var1) {
this.invoke((List)var1);
return Unit.INSTANCE;
}
public final void invoke(@NotNull List startList) {
while(true) {
Intrinsics.checkNotNullParameter(startList, "startList");
boolean var3 = false;
List l = (List)(new ArrayList());
Iterator var4 = startList.iterator();
while(true) {
while(var4.hasNext()) {
String start = (String)var4.next();
CharSequence $this$count$ivx = (CharSequence)start;
int $i$f$count = false;
int count$iv = 0;
CharSequence var9 = $this$count$ivx;
for(int var10 = 0; var10 < var9.length(); ++var10) {
char element$iv = var9.charAt(var10);
int var13 = false;
if (element$iv == '(') {
++count$iv;
}
}
CharSequence $this$count$iv = (CharSequence)start;
int $i$f$countx = false;
int count$ivx = 0;
CharSequence var20 = $this$count$iv;
for(int var21 = 0; var21 < var20.length(); ++var21) {
char element$ivx = var20.charAt(var21);
int var14 = false;
if (element$ivx == ')') {
++count$ivx;
}
}
if (count$iv == count$ivx && start.length() == 2 * n) {
Collection var17 = (Collection)res;
$i$f$countx = false;
var17.add(start);
} else {
if (count$iv - count$ivx < 2 * n - start.length()) {
l.add(start + '(');
}
if (count$iv > count$ivx) {
l.add(start + ')');
}
}
}
if (!l.isEmpty()) {
<undefinedtype> var10000 = (<undefinedtype>)this;
startList = l;
break;
}
return;
}
}
}
};
$fun$add$1.invoke(CollectionsKt.listOf(""));
String var3 = "4. " + res;
boolean var4 = false;
System.out.println(var3);
}
// $FF: synthetic method
public static void main(String[] var0) {
main();
}
}
я когда писал систему бэктестироваия принял такое правило: стоп выполнится заведомо хуже цены срабатывания, но вот насколько?
Мы знаем каково тело свечи, и можем взять например 2-5% от нее (но не менее минимального шага).
А в реале, раз уж у нас программный трейлинг, мы можем прикрутить к нему плавное прилижение к рыночной цене лимиткой, чтоб не платить комиссию тейкера, например в течение минуты, причем в последние 10с чтоб заявка стояла на лучшей цене.
Раздельное тестирование выхода полезно, но в некоторых случаях оно наложится на след. вход, так что полной чистоты тут не будет. )
да, пробовал в tailrec переделать, сходу не получилось. но, наверное, как-то можно перебрать варианты и без рекурсии, усложнив алгоритм. Там в постановке - нельзя сначала их все сгенерить, а потом отобрать корректные, считается ошибкой.
С чем-то соглашусь, но и вам стоило бы посерьезней относиться к чтению текста, уважаемый отличник. "а часок до собеса я спохватился и прорешал несколько задачек, что смог найти ". То есть речь вообще не о решениях на интервью, это не причина провала.
Это всего-то 4й абзац, а у вас уже внимание расфокусировано. Представьте производственный процесс (допустим разработки ПО), где исполнитель ТЗ дочитал до 3 абзаца и пошел делать, что за шлак у него получится, и как его потом переделывать придется каждые пол-часа, вот и тут примерно также.
И да, там может быть неоптимальный код, но поскольку вы не указали конкретное место - ваше сообщение бессмысленно. Почему я писал, что мне больше нравится Leetcode, там рейтингуется решение по памяти и производительности, и можно все исправить (но отличники, несомненно, от ошибок и неэффективности кода застрахованы РЕСО).
Я код и выложил-то потому, что возможно кто-то готовится, и захочет пообсуждать, попереставлять байтики, улучшить сложность в О нотации, и в ходе этого процесса повысит свои шансы.
Далее по тексту - АЛГОСЕКЦИИ ПРОЙДЕНЫ УСПЕШНО (надеюсь хотя бы сейчас прочтете). Кстати, там где интервьюеру не нравилась сложность, есть возможность улучшить, там все-таки не звери работают. А проблема в интервью по архитектуре, к которой я готовился тщательно, внимательно перечитав несколько сотен страниц толковых книжек, что никак не помогло.
на leetcode мне прям намного больше нравятся, чем платформа яши для спорт программирования, потому что там сигнатура метода указывается и дата класс (case class для scala) дают, не надо все из инпута текстом брать и в аутпут класть. что касается решения, это в разговоре с интервьюером всплывает - ты говоришь 1ю версию "ну вот так", он отвечает "а мне надо быстрее" - ну тогда вот map c O(1). Просто когда это надо сразу сказать, подвисает пауза, и ты начинаешь тупить - в IDE и с проверочными тестами а-ля Leetcode намного проще все было бы.
честно, не осведомлен о том какие грейды как называются, и какая сетка. я назвал сколько мне надо, они сказали что это сегмент выше среднего и требует пройти архитектуру. если бы оказалось, что это должность называется, например, "ведущий junior", мне не принципиально - должностями в наше время никого не удивить, и я ими уже переболел.
Хотя и с tailrec все-таки можно:
Декомпиляция из байткода, где рекурсия таки развернулась в цикл while:
я когда писал систему бэктестироваия принял такое правило: стоп выполнится заведомо хуже цены срабатывания, но вот насколько?
Мы знаем каково тело свечи, и можем взять например 2-5% от нее (но не менее минимального шага).
А в реале, раз уж у нас программный трейлинг, мы можем прикрутить к нему плавное прилижение к рыночной цене лимиткой, чтоб не платить комиссию тейкера, например в течение минуты, причем в последние 10с чтоб заявка стояла на лучшей цене.
Раздельное тестирование выхода полезно, но в некоторых случаях оно наложится на след. вход, так что полной чистоты тут не будет. )
да, пробовал в tailrec переделать, сходу не получилось. но, наверное, как-то можно перебрать варианты и без рекурсии, усложнив алгоритм.
Там в постановке - нельзя сначала их все сгенерить, а потом отобрать корректные, считается ошибкой.
С чем-то соглашусь, но и вам стоило бы посерьезней относиться к чтению текста, уважаемый отличник.
"а часок до собеса я спохватился и прорешал несколько задачек, что смог найти ". То есть речь вообще не о решениях на интервью, это не причина провала.
Это всего-то 4й абзац, а у вас уже внимание расфокусировано.
Представьте производственный процесс (допустим разработки ПО), где исполнитель ТЗ дочитал до 3 абзаца и пошел делать, что за шлак у него получится, и как его потом переделывать придется каждые пол-часа, вот и тут примерно также.
И да, там может быть неоптимальный код, но поскольку вы не указали конкретное место - ваше сообщение бессмысленно. Почему я писал, что мне больше нравится Leetcode, там рейтингуется решение по памяти и производительности, и можно все исправить (но отличники, несомненно, от ошибок и неэффективности кода застрахованы РЕСО).
Я код и выложил-то потому, что возможно кто-то готовится, и захочет пообсуждать, попереставлять байтики, улучшить сложность в О нотации, и в ходе этого процесса повысит свои шансы.
Далее по тексту - АЛГОСЕКЦИИ ПРОЙДЕНЫ УСПЕШНО (надеюсь хотя бы сейчас прочтете).
Кстати, там где интервьюеру не нравилась сложность, есть возможность улучшить, там все-таки не звери работают.
А проблема в интервью по архитектуре, к которой я готовился тщательно, внимательно перечитав несколько сотен страниц толковых книжек, что никак не помогло.
на leetcode мне прям намного больше нравятся, чем платформа яши для спорт программирования, потому что там сигнатура метода указывается и дата класс (case class для scala) дают, не надо все из инпута текстом брать и в аутпут класть.
что касается решения, это в разговоре с интервьюером всплывает - ты говоришь 1ю версию "ну вот так", он отвечает "а мне надо быстрее" - ну тогда вот map c O(1).
Просто когда это надо сразу сказать, подвисает пауза, и ты начинаешь тупить - в IDE и с проверочными тестами а-ля Leetcode намного проще все было бы.
честно, не осведомлен о том какие грейды как называются, и какая сетка.
я назвал сколько мне надо, они сказали что это сегмент выше среднего и требует пройти архитектуру.
если бы оказалось, что это должность называется, например, "ведущий junior", мне не принципиально - должностями в наше время никого не удивить, и я ими уже переболел.
да.
хорошая новость в том, что на маленькую зп достаточно алго-секций, без архитектурной.