Viktor
Посмотрел на решение задачи 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--;
}
}
Вывод: важен порядок роста потребления памяти, а не конкретные значения. Когда говорят «решить без дополнительной памяти» значит уровень потребления дополнительной памяти не должен зависеть от входных данных, т.е. O(1). Если надо создать пару переменных или массив для обмена, это ок.
Dmitriy
Dmitriy
Viktor
Viktor
Надо убирать функции и обмен через массив, оставить одну tmp переменную. Читаемость правда пострадает 🙂
Viktor
@dudagod спасибо за тщательное ревью!
Dmitriy
пожалуйста )
Evgeniy
Evgeniy
Разобрался. Здесь массив строк используется
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Что думаете?
Viktor
Я бы не удивился. Например почти по всем фанге стажёрам поотменяли оферы совсем. Люди прошли драконовские собеседования, но сказали, сорян, приходите в следующем году.
Evgeniy
Хочется верить, что не на новое собеседование
Viktor
https://twitter.com/tilek/status/1255880784218435584
Viktor
Насчёт нового собеседования, наверное, всё же нет. Может просто через год офер выставят если всё пойдёт хорошо. Я так понимаю ещё и с визами ж в США связано.
Viktor
Всё одно на одно.
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Это же...
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Неужели у Я так упали доходы? Хотя… В целом экономика падает, и до Я дойдет, только через время
Evgeniy
У всех упало
Evgeniy
По цепочке
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Я про это и сказал
Порридж В Ко-ливинге
Если бы были вливания, может быть через 2 месяца стало бы все как раньше
Порридж В Ко-ливинге
(у нас же намекают Белорусский сценарий сделать)
Evgeniy
Evgeniy
Но государственная политика, конечно, играет важнейшую роль
Evgeniy
Какие сферы экономики поддерживать, а какие — как-нибудь сами
Uladzimir
Порридж В Ко-ливинге
Uladzimir
Это по телевизору забили болт, сознательные люди дома сидят)
Viktor
Uladzimir
Но на работу в гос предприятия загоняют, спору нет
Uladzimir
Он самый, да 🙂
Много грязи в комментах когда-то про него прочитал)
Uladzimir
То ли на vc, то ли на хабре. Идея ведь та же, что в лямбде скул.
Типа пацаны и сами могут пробиться, а это такая сволота, хочет поиметь с умных ребят
Evgeniy
Как вам сегодняшняя задача?
Evgeniy
https://pastebin.com/CsxuFcSJ
Evgeniy
вот набор тестов, который я прогонял
Viktor
Viktor
Чтобы догадаться до жадного алгоритма пришлось написать дофига тестов.
Evgeniy
Viktor
Evgeniy
https://leetcode.com/problems/remove-k-digits/discuss/630388/C-O(n)-timespace-solution-using-Stack
Evgeniy
Неудивительно, что у задачи всего 26% принятых отправлений
Viktor
Меня первый тест сперва смутил. Я снимал со стека если пошёл негативный тренд только один символ и шёл сразу дальше, но это неверно: надо снимать со стека пока негативный тренд не закончится вовсе.
Viktor
Я бы сказал сложная задачка.
Evgeniy
Evgeniy
Поначалу все тесты, которые подбирал, проходили
Viktor
Намеренно подобран тест чтобы сбить с толку :-)
Evgeniy
Но потом попался непроходимый
Evgeniy
Evgeniy
Evgeniy
Тоже через стек, получается
Иван
Да уж, задачка сегодня порадовала) 3 часа потратил а в итоге сделал n^2 и успокоился))
Evgeniy
Прошло по времени?
Evgeniy
Там же вроде 10000
Иван
Да, причём с запасом небольшим. Вот именно поэтому и прошёл что 10000) вот лимон уже никак бы не втиснулся
Иван
Зато понятный человекам код.
Viktor
Иван
Ну там не совсем ведь перебор. Скорее выборка наиболее подходящего значения
Viktor
А, не. Ты написал n^2, я думал в степени n.
Иван
Да, ну и там с обрезанием строки. Наверное это самая затратная операция вышла. Конструирование новых строк
Порридж В Ко-ливинге
Так
Порридж В Ко-ливинге
Товарищи, члены профсоюза Инжинеров
Порридж В Ко-ливинге
Вчерашнюю лучше чем за O(N) O(N) никак?
Порридж В Ко-ливинге
Строку на месте можно менять
Viktor
ну вот если её менять на месте, без вспомогательного стека, то какой-то адский треш получается, в котором я не могу не запутаться 🙂
Viktor
короткий ответ такой: может быть и можно, но лично я хз.
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Я, кстати в C++ листах неразобрался
Порридж В Ко-ливинге
Они отвратительные