Посмотрел на решение задачи Reverse Words in a String - https://www.notion.so/Reverse-Words-in-a-String-050ce82be6764c84816fd06e09e89055. Как всегда пытаемся решить с минимальным потреблением памяти. Но в функции reverse есть код с обменом значениями в массиве через создание нового массива на каждую итерацию. И выглядит так, что это не может быть бесплатно, т.е. память на создание таких массивов полюбому должна тратится. Если конечно в js нет какой-то хитрой оптимизации в этом случае. /** * Разворачивает символы в интервале [i, j] * @param {string[]} s * @param {number} i * @param {number} j * @return {void} */ function reverse(s, i, j) { while (i < j) { [s[i], s[j]] = [s[j], s[i]]; i++; j--; } }

Память на создание массива разумеется тратится, но так же будет и на создание переменных тратится, если скажем обменять значения через `tmp`-переменную. Я сомневаюсь, что будет большая разница.

Разница есть, но да, небольшая. Переменная с символом займет 2 байта, а массив с двумя символами занимает 4 байта.

Вывод: важен порядок роста потребления памяти, а не конкретные значения. Когда говорят «решить без дополнительной памяти» значит уровень потребления дополнительной памяти не должен зависеть от входных данных, т.е. O(1). Если надо создать пару переменных или массив для обмена, это ок.

Для функции reverse создание массивов ведь будет - O(N). Чем длинее строка, тем больше перестановок и соответственно больше массивов создается. В общем, проблему бы решило вынесение tmp массива или переменной выше из функции reverse. Тогда бы не создавали ее постоянно по новой.

В JS строки неизменяемые, так что нельзя. Но в данной задаче идёт работа с массивом символов как раз поэтому.

Я бы не удивился. Например почти по всем фанге стажёрам поотменяли оферы совсем. Люди прошли драконовские собеседования, но сказали, сорян, приходите в следующем году.

Хочется верить, что не на новое собеседование

У всех упало

Если бы были вливания, может быть через 2 месяца стало бы все как раньше

https://twitter.com/tilek/status/1255880784218435584

(у нас же намекают Белорусский сценарий сделать)

А что такой «белорусский сценарий»?)

О, а это не тот товарищ, что за процент от зп в фаанг готовит?

Он самый, да 🙂

Много грязи в комментах когда-то про него прочитал)

вот набор тестов, который я прогонял

Нормальный набор. Решил, в итоге?

Да, решил. Через стек

Меня первый тест сперва смутил. Я снимал со стека если пошёл негативный тренд только один символ и шёл сразу дальше, но это неверно: надо снимать со стека пока негативный тренд не закончится вовсе.

Намеренно подобран тест чтобы сбить с толку :-)

Чтобы догадаться до жадного алгоритма пришлось написать дофига тестов.

Кстати, а как тут жадным будет?

Стек это и есть жадный же. Не перебор полный.

Понятно. Жадность в том, что собираешь все числа, подряд возрастающие

Да уж, задачка сегодня порадовала) 3 часа потратил а в итоге сделал n^2 и успокоился))

Вчерашнюю лучше чем за O(N) O(N) никак?

ну вот если её менять на месте, без вспомогательного стека, то какой-то адский треш получается, в котором я не могу не запутаться 🙂

Я этим и занимался больше часа