Подготовка к собеседованию в Google - Хитрая задача на Стек
ฝัง
- เผยแพร่เมื่อ 22 มิ.ย. 2020
- Разбираем довольно сложную алгоритмическую задачу по программированию с применением стека. Ее могут спросить на собеседовании в Google, Amazon и Facebook.
Эта задача на LeetCode: leetcode.com/problems/daily-t...
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
Вы прекрасно объясняете алгоритмы и структуры данных. Это очень большая редкость. Надеюсь что Вы вернётесь к ведению канала и будете продолжать просвещать начинающих it-специалистов.
Это не только для начинающих. :-))
Лучшее объяснение алгоритмов, нет слов, просто потрясающще!!!
Интересная задача и очень понятное объяснение решения! Спасибо!
Парень прирожденный препод! :) Очень доходчиво.
С таким кайфом вообще смотрю, спасибо огромное
Спасибо за пример и хорошее объяснение! 👍
Александр, очень нравится как вы объясняет материал. Спокойно и понятно. Спасибо.
Решение со Stack прошло проверку. Спасибо за видео! лайк и подписка
Спасибо за видео, понятно объясняете
Классное объяснение!
Очень хорошее объяснение и залача, спасибо
Спасибо большое бро! Канал топовый!
Отличное объяснение! У меня сначала появилась идея просто отсортировать массив по убыванию с сохранением индексов и потом бежать по нему и выделять в подмассив длинны n ответы по индексу элемента в подмассиве, но ваш вариант определенно лучше во всех случаях)
Интересная задача. Спасибо вам за такое хорошее и понятное объяснение!)
Красава вапще, я не могу просто над тобой, лайк, подписка, и high recommended
Позитивная подача и интересный материал !
Какой же ты крутой бро, лайк тебе)))
Отличное видео, жаль что нет новых.
Спасибо. Всё шикарно
Очень крутая подача, автору респект!
Хорошее решение. Нет необходимости хранить в стеке значения температур, достаточно класть туда только индексы:
public int[] warmDays(int[] days) {
result = new int[days.length];
Stack stack = new Stack();
for(int day = days.length-1; day >= 0; day--) {
while (!stack.isEmpty() && days[stack.peek()]
Постоянно дергать базу чтобы из индекса вытащить температуру может быть тоже плохо
Интересная опция! На сложность (О) не влияет, но может быть принципиальным если значение не просто цифра, а сложный тяжелый объект.
@@by0uki это алгоритмическая задача, здесь не идет речь о работе с базой, данные находятся в памяти. Если хранить в стеке только индесы, то памяти потребуется в два раза меньше, а скорость не изменится
Можно идти по списку и в прямом порядке:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = [] # [(i1, t1), (i2, t2), ...]
result = [0] * len(temperatures)
for i, t in enumerate(temperatures):
while stack and stack[-1][1] < t: # stack[-1] means the last element
prev_i = stack.pop()[0]
result[prev_i] = i - prev_i
stack.append((i, t))
return result
Понятно и без воды, лайк 👍
Крутое решение! 💪
Array.prototype.last = function() {return this[this.length - 1] ?? undefined}
let n = [13, 12, 15, 11, 9, 12, 16]
let stack = []
let answer = new Array(n.length).fill(0)
n.forEach((el, idx) => {
while (n[stack.last()] < el) {
let val = stack.pop()
answer[val] = idx - val
}
stack.push(idx)
})
console.log(answer)
У меня получилось такое решение (JS), до того как посмотрел разбор. Спасибо большое за задачу :)
Прекрасное лаконичное изложение материала, спасибо. В стек не обязательно сохранять значения, достаточно просто индексы. По ним в исходном массиве находим значение.
Кстати, да. LinkedList - тоже вариант
хорошее дополнение 👍👍
Читать список не последовательно довольно тяжело для процессора (почитайте про кеширование). Так что лучше все же сохранять значения также.
@@MaratAshrafzianov 1.Если все данные записаны в кеш процессора, то разницы никакой.
2. Размер данных меньше минимум в 2 раза. Неизвестно, что станет бутылочным горлышком в дальнейшем и какие данные поместятся в кеш полностью.
3. При текущем алгоритме данные тоже пишутся не последовательно (попеременное обращение в разные области).
4. Экономия на спичках, коим является учитывание кэш процессора, является самым затруднительным и с минимальным приростом по производительности действием. Тем более, когда пример дан на Java
Если не ошибаюсь, то стек тут не нужен, проблему можно решить за это же время без дополнительной памяти:
vector arr = {13, 12, 15, 11, 9 , 12, 16};
vector res;
res.resize(arr.size(), 0);
for(int i = res.size() - 2; i >= 0; --i) {
int j = i + 1;
while(res[j] != 0 && arr[j] arr[i]) res[i] = j - i;
}
Не ошибаешься, скрипач не нужен.
Что-то подсказывает, что ты прав, и сложность в твоем случае линейная, несмотря на то, что здесь цикл в цикле, и while иногда выполняется несколько раз. Можешь сказать, так ли это?
@@bohdansolonenko6554 да, теперь понял. Действительно, количество прыжков не больше, чем количество stack.pop() из реализации в видео и сложность не возрастает. Красиво, спасибо
Да, круто)
Линейное время неочевидно. В варианте со стеком линейное время доказывается доказывается через работу со стеком:
- В итерации цикла добавляется 1 элемент, и рассматривается [1 + количество удаляемых элементов].
- За время работы всего алгоритма каждый элемент удаляется один раз.
- Итого линейное количество итераций и линейное количество операций со стеком за весь алгоритм
Здесь тоже нужно как-то доказывать что res[i] рассматривается константное количество раз.
Круть, спасибо)
Спасибо, хорошее решение. Сам решал так же со стеком, однако массив проходил в прямом порядке. Как по мне так короче и проще для понимания, при аналогичной сложности по времени и памяти:
def weather(arr):
stk = [] # ( temperature, i )
res = [0] * len(arr)
for i, cur in enumerate(arr):
while stk and stk[-1][0] < cur:
_, ix = stk.pop()
res[ix] = i - ix
stk.append((cur, i))
return res
import random
import time
l = [random.randint(-40, 40) for _ in range(1000000)]
s = time.time()
r = weather(l)
t = round((time.time() - s)*1000, 3)
print(r, t, sep="
")
Изящно! :)
Спасибо 🔥
Я Андрей и я работаю кассиром в Пятерочке. Надо начинать не с последнего элемента а предпоследнего так как у последнего всегда будет 0.
Если в вашем языке нет стека - как к примеру в дарте то можете использовать такое решение:
Solution {
List dailyTemperatures(List temperatures) {
final List result = List.filled(temperatures.length, 0);
for (var i = temperatures.length - 2; i >= 0; i--) {
if (temperatures[i] < temperatures[i + 1]) {
result[i] = 1;
} else {
int j = i + 1;
while (result[j] != 0) {
j = j + result[j];
if (temperatures[i] < temperatures[j]) {
result[i] = j - i;
break;
}
}
}
}
return result;
}
}
Спасибо!
С временной сложностью не совсем очевидно, но именно взаимодействий со стеком (вставок и удалений) в худшем случае
Спасибо
Тут на помощь придет ещё одно наблюдение: на каждом шаге мы вставляем ровно один элемент и удаляем ноль или более. Поскольку мы всего вставляем максимум n элементов, то и удаляем мы всего максимум n элементов. Операции со стеком занимают время O(1), так что тут все достаточно просто: общая амортизарованная сложность по времени O(n). И по памяти тоже O(n).
int main() {
std::vector t = {13, 12, 15, 11, 9, 12, 16};
std::vector days = {};
int j = 0;
int i = 1;
while (days.size() - 1 != t.size() - 2) {
if (t[j] < t[i]) {
days.push_back(i - j);
j++;
i = j;
}
else i++;
}
days.push_back(0);
for (int c : days) std::cout
Не смотрите это видео зимой! По ролика мозг перед числами рисовал мне минус. Поэтому у меня возникал постоянный вопрос: "Какого хрена 15, теплее чем 9. - 9 это же теплая зимняя погода, а - 15 это ближе к дубаку)))
Еще не просмотрел видео, только прослушал условие и начал думать, а тут на глаза попалось название... Зачем же так сразу все палить :)
Видео про Google интервью - th-cam.com/video/1EFwLkbiTng/w-d-xo.html
Жду Ваших комментариев.
Like и Subscribe приветствуются!
вот блин, в названии видео был ответ, а я уже думал о сортировке с сохранением индексов и прочие усложнения
Я бы загнал в бинарное дерево с сохранением индекса. Тогда для ответа нужно просто пройти по дереву в глубину в режиме inOrder.
И для каждого значения посчитать разницу с предыдущим индексом.
Тогда будет O(nlogn) + бинар дерево писать
Само создание дерева уже O(n*log(n)). И это мы ещё решать не начали. :-))
💪👍
Стек не дает преимуществ. Кажется вроде он по памяти оптимизирован, но можно исполбзовать массив ответов и массив индексов следующего теплого дня. Да, массив индексов будет как массив ответов по длине, но у тебя нет лишней коллекции чтобы хранить температуры дней.
Хотя ладно, пока писал понял, что если исходный массив огромный, а мы ожидаем, что стек по ходу программы будет маленький, то выигрышь есть. А мои предыдущие размышления имеют вес только для вырожденного случая. Ты прав
Можно не создавать ещё коллекцию по хранению температур, можно обойтись самой высокой, чтобы потом перепрыгивать по элементам. Не особо хотел подробно описывать, может некоторым захочется самому подумать.
Не совсем понял второй ответ, возможно потому что далек от програмирования.
Разве для 4 элемента массива (9) следующим большим не будет 5элемент (12) ? Просто исходя из полученной информации в стеке на 4 элемент соответственно выдаст нижний элемент (16)?
И если первый элемент массива будет наибольшим, что мы получим на выходе? Не заметил проверку на это.
Да, правильно, для 4-ого элемента ответом будет 5-ый элемент и алгоритм из ролика так и считает. Когда мы доходим до этого самого 4-ого элемента мы уже прошли 5-ый и 6-ой, поэтому наш стек будет выглядеть так: 12(5), 16(6). А начинаем мы проходить по нему с вершины, то есть с 12, и поскольку сразу натыкаемся на число больше 9-ти, берём его ответом. Таким образом для 4-ого элемента ответом будет 5-ый.
@@kostya_superovotes8610 Спасибо!
Теперь понял.
Думал сперва полностью формируется стек для всего массива, а потом осуществляется перебор.
чувствую как становлюсь умнее...🤗
Я смотрю, многие пишут, что сложность не поменялась и всё ещё O(n^2). Нет, сложность будет O(n), потому что для каждого элемента мы выполняем максимум 3 операции: проходим по нему в массиве, добавляем в стек и удаляем его в из него. Рассмотрим на примере в видео.
13 12 15 11 9 12 16
Стек: пуст
1. Находим 16 в массиве.
2. Добавляем 16 в стек.
Стек: 16
3. Находим 12 в массиве.
4. Добавляем 12 в стек.
Стек: 12 16
5. Находим 9 в массиве.
6. Добавляем 9 в стек.
Стек: 9 12 16
7. Находим 11 в массиве.
8. Удаляем 9 из стека.
9. Добавляем 11 в стек
Стек: 11 12 16
10. Находим 15 в массиве.
11. Удаляем 11 из стека.
12. Удаляем 12 из стека.
13. Добавляем 15 в стек.
Стек: 15 16
14. Находим 12 в массиве.
15. Добавляем 12 в стек.
Стек: 12 15 16
16. Находим 13 в массиве.
17. Удаляем 12 из стека.
18. Добавляем 13 в стек.
Можно пронаблюдать, что с одним числом делается максимум 3 операции. Вообще, операций может быть немного больше, ведь мы можем какие переменные ещё подключать и тд, но суть в том, что из конечное, небольшое и с фиксированным максимумом количество.
Мне еще помогает понять сложность тот факт, что ни один элемент массива не попадет в стек более одного раза, а значит внутренний цикл while В СУММЕ будет выполняться O(n) раз.
У тебя ещё есть прогонка в стеке. А стек у тебя может по размеру быть как массив. И что бы найти в стеке нужный ты по факту получаешь O(n*n). Сложность же считается для алгоритма, а не для определённого решения. По этому O(n*n/2) тут
@@lawamoril прогонки не будет каждый раз, а максимум один раз, после чего элементы удалятся. Поэтому О(n).
Чтобы другим способом понять можно на примере рассмотреть крайние примеры "6 1 2 3 4 5" и "5 4 3 2 1 6" и увидеть, как красиво работает в обоих случаях стек. В то время как в 2 примере решение без стека, с циклом, будет выполняться за O(n^2) ((если про количество итераций, то (n*n/2), но 1/2 в O нотации опускаем).
@@lawamoril амортизированно по всем шагам мы удаляем из стека максимум n элементов, добавляем всегда n элементов. Не будет квадратичной сложности.
@@KirillFrolov77 Амортизированно == суммарно?
На уникальных значениях температур оба алгоритма отрабатывают одинаково. Но пропустите через них массивы с неуникальными значениями - результаты кого-то могут удивить. А так тема интересная, объяснено замечательно. Спасибо Саша!
Ничего подобного, совершенно не одинаково. Возьмите массив уникальных температур отсортированный по убыванию. В одном случае будет O(n^2), а в другом O(n).
Тема неуникальных значений не раскрыта. И если массив из одинаковых чисел, то должны быть все нули.
@@serged5689 это не соответствует условиям задачи. Требуется явно найти дни, когда температура ВЫШЕ. А условия не нахождения таких дней не заданы. И это был бы хороший вопрос на собеседовании.
Чем второй способ с созданием, добавлением и удалением объекта в стекле лучше первого? Не разобрали такты процессора и работу с кэшем.
блин, я тоже сразу решил идти с конца. но так как вообще не работал со стеком. не подумал про него. а подумал про обычный массив🤔
Можно сделать еще проще:
Не сохранять индексы. А кол-во суток через которое будет более теплый день будет показывать количество удалений элементов из стека + 1
На первый взгляд ваше утверждение кажется логичным, но на видео контрпример для самого левого элемента = 13. Кол-во удалений из стека на этом этапе явно больше двух
Все замечательно, только маленький диссонанс: с одной стороны собеседование в Гугл, а с другой стороны объясняем что такое стек.
Большая дорога начинается с первого шага. :)
Ахах) только утром решал задачу и тут вечером под чийочик смотрю разбор)
Решал банальным брутфорсом (двойным циклом)
n
Отличный материал, шикарная подача, спасибо! Только насчёт удобного класса для 2-х значений, есть Point, не подходит?)
А что произойдет в случае, если у нас день среди недели был самым жарким? Как будто бы этот нюанс не обработан в решении. Не знаю, как в джаве это будет выглядеть. Джаваскрипт бы выбросил ошибку
Но за объяснение спасибо большое
Почему так мало видосов? Мне кажется, надо заняться каналом и запилить новые алгоритмы.
Если в стеке нет элементов, в массив ответов нужно записать 0, а то в твоем тесткейсе, как я понимаю, последний день, ровно как и день с максимальной температурой, не обрабатывается никак.
Однако это не так уж и сложно обрабатывается, здесь важнее алгоритмика нежели полнота
массив ответов - это массив маленьких интов, что значит по умолчанию они все 0 и нет необходимости этот 0 еще раз проставлять.
Массив примитивов (например, int[]) в Java инициализируется значениями 0. Поэтому массив уже заполнен элементами, равными 0.
@@gandibaat3637 а при чем тут джава? это алгоритмическая задача
@@projeqt9243 претензии-то к конкретной реализации. А пример в видео написан на Java. Я и объясняю, почему принудительно писать в массив ответов нули не нужно.
Ох блин, я несколько дней думал над задачей, решение сам придумал, но двигался слева направо и код получился куда менее лаконичным (на С++). На leetcode по сложности тоже прошел тесты.
вот более эффективный алгоритм (быстрее примерно в 10-17 раз), без (явного) использования стека:
static int[] temperature(int[] t) {
int[] answer = new int[t.length];
for (int i = t.length - 1, head = -1; i >= 0; i--) {
while (-1 != head && t[head]
Объясните плиз, почему в первом случае сложность считается как О(n^2). больше похоже на О(n^2 / 2). Из примера в видео с n = 7 получаем, что мы в худшем случае пройдем по массиву 6+5+4+3+2+1 = 21 раз, или тут деление на 2 это как константа и потому отбрасывается?
Константы выностяся за нотацию, да
Для меня было проще обратное решение: проходить массив слева направо, добавлять в стэк кортеж: (температура + индекс) , и до этого вынимать из стека все показатели с температурой меньше, чем текущая и записывать в результат разность их индексов.
Здорово, но зачем стек, если в массиве answer уже хранятся отностительные данные об индексах отработанных элементов?
Вроде можно вообще без стека
+
Классы Stack и C занимают место в куче, тратится время на инициализацию (конструкторы). Накладные расходы на объекты всегда велики. В целом, решение с обычными итерационными циклами покажет лучшую производительность и экономию памяти.
От количества данных зависит. На малом объёме - да.
В подобных задачах не учитываются расходы на инициализации и прочее, тк это задача на построение алгоритма, он мог работать с парами, что было бы быстрее, но это в задаче не рассматривается
При инициализации стека фиксированного размера мы получим лишь одну единственную концанту по инициализации. В практическом же смысле куча или стек не имеют значения когда в одном цикле мы обращаемся по указателям в непрерывную область памяти, т.к. это всегда будут затраты на помещение непрерывного блока в кэш L3 и незначительные на этом фоне затраты обращения к кэшу. Более того, если размер массива значительно будет превышать размер блока для кэша L3 (например 10^6 целых) то решение O(n*n/2) с обращением к массиву в цикле будет еще и иметь огромный штраф типа 10х по сравнению со стеком за счет оптимизаций обращения к кэшу процессора, на фоне чего затраты на разовую инициализацию стека меркнут.
@@kostyajan L3 есть не везде. Нацеливаться только на L3 это ошибка.
Интересно, почему вместо прямолинейного решения с проходом слева направо выбрано по сути эквивалентное с проходом справа налево :)
Если ты идешь слева направо и хочешь решить задачу за один проход - ты ничего не знаешь о будущих температурах, соответственно ничего не знаешь о расстоянии до ближайшего дня, когда будет теплее.
Если бы условие стояло "найти количество дней до дня в прошлом, когда было теплее", тогда бы можно было пройти слева направо и нельзя - справа налево.
@@gandibaat3637
def f(t_list, default=None):
ans = [default] * len(t_list)
stack = [0]
for i in range(1, len(t_list)):
cur_t = t_list[i]
last_t = t_list[stack[-1]]
while cur_t > last_t:
last_i = stack.pop()
ans[last_i] = i - last_i
if not stack:
break
last_t = t_list[stack[-1]]
stack.append(i)
return ans
@@Avorthoren справедливо и вроде работает на первый взгляд. Справа налево логичнее и проще для понимания как-то, на мой взгляд - считаем ответ для дня в массиве в тот момент, когда проходим по нему
@@gandibaat3637 Ну такое :) Вроде не менее логично пройти элемент, и, когда дойдём до элемента с большей температурой, вычислить ответ для исходного :)
@@gandibaat3637 Справа налево можно вообще без стека решить, просто использовать инфу о уже пройденных днях.
А вы в тактах процессора считали, что дороже циклы в кэше проца x86_64 крутить или стек городить с new + delete. Вот это как раз и есть разница в ява программистах и тех, кто на ассемблере работать умеет.
Разница инженера и кодера в том что инженер понимает что происходит при n -> стемящихся к большим числам.
@@serged5689 "Я это сделал не в интересах истины, а в интересах правды" (с)
Вы чего этим сказать то хоть хотели по разбору конкретно этого прикладного кейса?
Я что-то не понял условие задачи - ведь для каждого дня в данном примере самая высокая температура будет последняя, почему для пнонедельника будет другой день?
Перечитал условие в другом месте, более понятно.
Нужно найти день после выбранного дня, температура которого превышает температуру выбранного дня.
9:29 как нет?? почему бы не использовать мапы???
Мое персональное мнение, что ожидать решение такого типа - это против правил. Если для формулирования оптимального алгоритма надо знать приемчики - то такое интервью не дает вам никакой полезной информации. Ну или вернее, если человек знает это решение - то это подтверждение того факта, что он готовился, а не того, что он чего-то там умеет сам. В Amazon'е это бы классифицировали как trick question и в обсуждении не зачли бы. А интервьюеру сказали бы, чтобы он больше этот вопрос не использовал.
Что касается самого подхода, не сказаны главные слова. Надо сказать, что, мол, обратим внимание, что в любой момент времени нас интересуют ИСКЛЮЧИТЕЛЬНО дни справа, в которые температура была ВЫШЕ температуры текущего рассматриваемого дня. Поэтому все температуры, которые мы уже встретили справа и они ниже, можно смело выкидывать из рассмотрения, в любом случае расстояние от любой более низкой температуры слева до текущей будет короче, чем до любой более низкой температуры справа.
Вот именно из этого наблюдения следует оптимальное решение, а вовсе не из переборного решения. Использвать стек или нет - решение наживное, linked list тоже пойдет, там все операции с головой списка тоже O(1), как рту стека
Если несложно, объясните пжста по первой части: при решении с двумя циклами получается, что в решение попадают значения из массива большие по условию, но перебор каждый раз начинается с начала массива, ответы попадают неверные
Перебор начинается не с начала массива, а с элемента на котором мы находимся +1
Ответы попадают верные, однако мы лишний раз проходимся по элементам которые не могут нам подойти
Во втором случае мы эти элементы убираем
@@user-bl2zl6jf2q спасибо)
@@user-bl2zl6jf2q всеравно не получается( я решаю в питоне, запускаю два цикла первый с перебором по значениям, второй с перебором по индексам. Индексы являются решением, но невсегда верны( т.к. каждый раз перебор начинается с начала списка. Помогетп пжста, уже две недели пытаюсь решить, и бросить не могу((
и в каком месте второго решения мы в ответы 0 кладем для 16?
А это уже тест на внимательность :) Вы приняты в Гугол :D
Массив изначально 0 заполнен в джаве
Сильно зависит от условий, конечно. Почему-то снова оценка О() построена на том, что работа со стеком - бесплатная. Причем как удаление / добавление элементов, так и поиск нужного числа в стеке - внезапно бесплатный?! как это так? Это же совершенно не соответствует действительности! Оценка О(n) явно неправильная. В зависимости от везения (т.е. от исходных данных) вычислительная сложность решения со стеком будет на промежутке O(n)....O (n2). И это если не учитывать добавление / удаление в стеке, которое, повторюсь, совершенно не бесплатное.
Однако если последовательность дней ну оочень длинная и температура ходит "туда-сюда" - то выигрыш в решении со стеком будет, это да.
Это не просто стек, это возрастающий монотонный стек (increasing monotonic stack), в котором значения только увеличиваются. И зачем отдельный класс для хранения так же не понятно, можно хранить элементы стека в формате массива [value, index].
Но ведь можно использовать рекусию, или я заблуждаюсь? Просто тогда получается что Оn = (n-1)*n/2. Но я в это мне уверен...
Сложность будет O(n), потому что для каждого элемента мы выполняем максимум 3 операции: проходим по нему в массиве, добавляем в стек и удаляем его в из него. Рассмотрим на примере в видео.
13 12 15 11 9 12 16
Стек: пуст
1. Находим 16 в массиве.
2. Добавляем 16 в стек.
Стек: 16
3. Находим 12 в массиве.
4. Добавляем 12 в стек.
Стек: 12 16
5. Находим 9 в массиве.
6. Добавляем 9 в стек.
Стек: 9 12 16
7. Находим 11 в массиве.
8. Удаляем 9 из стека.
9. Добавляем 11 в стек
Стек: 11 12 16
10. Находим 15 в массиве.
11. Удаляем 11 из стека.
12. Удаляем 12 из стека.
13. Добавляем 15 в стек.
Стек: 15 16
14. Находим 12 в массиве.
15. Добавляем 12 в стек.
Стек: 12 15 16
16. Находим 13 в массиве.
17. Удаляем 12 из стека.
18. Добавляем 13 в стек.
Можно пронаблюдать, что с одним числом делается максимум 3 операции. Вообще, операций может быть немного больше, ведь мы можем какие переменные ещё подключать и тд, но суть в том, что из конечное, небольшое и с фиксированным максимумом количество.
На практике, решение с рекурсией работает быстрее
class Solution {
public int[] dailyTemperatures(int[] days) {
int day = 0;
do {
int dist = daysTraverse(days, day);
day += dist;
} while(day < days.length-1 && day > 0);
days[days.length-1] = 0;
return days;
}
public int daysTraverse(int[] days, int day) {
if(day == days.length - 1) {
return 0;
}
int next = day + 1;
int totalDist = 1;
while(days[day] >= days[next]) {
int dist = daysTraverse(days, next);
totalDist+=dist;
next += dist;
if(dist == 0) {
days[day] = 0;
return totalDist;
}
}
days[day] = totalDist;
return totalDist;
}
}
@@powerhead Сорри за вопрос старому сообщению, но рекурсия - это же тот же стек, только в него ложат не наши данные а текущее состояние системы. Как оно может быть быстрее? Кто знает?
Хорош
Так и не понял зачем стек когда можно хранить 1 число (последнее добавленное в стек), а его ответ укажет где находиться следующее «в стеке»
Потому что возможна ситуация при которой данные только последнего значения не будут достаточными для правильного ответа. Например, если у нас в стеке числа (9, 12, 16) , то для случаев нового дня с температурой 11 и 14 будут разные ответы, которые не получить только из последнего ответа для 9, нужен именно стек всех предыдущих значений.
@@serafim4372 да, но в примере у 9 тоже посчитано расстояние, на которое сразу можно перейти дальше и тд. Т е работать будет как в стеке, но без доп структуры, тк можно считать, что каждый элемент имеет ссылку на следующий в "стеке". и нам достаточно помнить индекс "верхушки"
Мне понравилась задача. Поставил на паузу после условий. Вот такой вариант пришёл в голову, реализация на Питоне (немного учил его на карантине).
a = [13, 12, 15, 11, 9, 12, 16]
for i in range(0, len(a)-1):
print(a[i])
n = 1
while a[i+n] < a[i]:
n +=1
else:
print(str(n) + " дня")
print(str(a[-1]) +" 0 дней")
Интересный код, но работает - тоже за квадрат, если я не ошибаюсь) Примерно то же, что и предлагалось в видео как первый алгоритм.
"Поскольку каждый день мы можем добавить и удалить лишь 1 раз, то сложность O(n)."
Когда мы доходим до дня 2 с темп 15, то мы добавляем 1 раз, но удаляем 2 раза (удаляем день 3 и день 5). Или я что-то путаю? Кто-то может объяснить, пожалуйста, почему сложность O(n), даже в случае, когда мы имеем 100000 элементов и доходим до 0-ого элемента, который имеет, допустим, самую высокую температуру и в худшем случае мы вынуждены проходится обратно по всему стеку и удалять все дни по очереди до 100000-ого элемента?
Имеется в виду, что каждое число из массива может в худшем случае один раз попасть в стек и один раз из него удалиться. Получается максимум 2*N операций. Если мы в конце удалили 100000 элементов, это значит, что мы до этого ни разу ничего не удалили и 100000 раз добавили. Получается, мы сделали для 99999 чисел по одному добавлению и для одного последнего числа 100000 удалений. Всего как раз 2*N.
@@chichkan87 спасибо большое 🙏🏼
Собрался читать «Грокаем алгоритмы». Про О большое теперь что-то знаю :)
не правильно использовать "свойства" length, во втором параметре цикла for (let a = 0; a < t.length; a++)
потому что в таком случае каждый следующий шаг цикла будет каждый раз тратить время на определение t.length.
более быстрее будет сразу задать в первом параметре for (let a = 0, b = t.length; a < b; a++)
неправильно писать тяжелочитаемый код, выигрыш в производительности проигрыш в производительности очень незначителен, но код становится заметно легче для восприятия
@@cringoulique Вообще-то во многих крупных корпорациях выигрыш в производительности как раз таки очень значителен и является самым важным фактором, даже если код становится тяжелочитаемый. Потому что пользователи куда важнее чем программисты читающие код. Именно поэтому выигрыш в производительности очень даже значителен не смотря на тяжелочитаемый код. Особенно когда речь идёт о гиганстких обработок данных.
Да и к тому же, с какой стати код становится тяжелочитаемый ?? Изначально я привёл шапку цикла из примера видео, в нём 34 символа. Дополнение кода изменяет длину шапки всего до 37 символов. С какой стати такая разница превращает код в тяжелочитаемый, если само содержимое цикла не меняется.
Вроде можно просто динамикой решить: если предыдущий день не теплее нашего, то шагнём на столько назад, какое число мы уже заполнили для предыдущего дня и проверим получившийся день. Получается то же самое, только не нужна память под стек.
Покажи мне такое решение со сложностью < O(n^2)
@@redhook777 вот, примерно в 10 раз быстрее чем реализация через стек:
static int[] temperature(int[] t) {
int[] answer = new int[t.length];
for (int i = t.length - 1, head = t.length; i >= 0; i--) {
while (head < t.length && t[head]
@@AlexeySilichenko чем это принципиально отличается от двойного цикла?
@@SwampJay Перескоками через заведомо меньшие. И стек не нужен.
Если исходный массив температур очень большой, то вариант со стеком может оказаться предпочтительнее, чем вариант с перескоками из-за кэш миссов при большом разбросе максимальных температур одновременно попадающих в стек и находящихся в сильно разных местах исходного массива. Также вариант со стеком (буферизацией) единственный при потоковом вводе и выводе значений, естественно всё равно начиная с конца.
class C { } -- я хлопал стоя . спасибо большое тебе , и интересно и полезно , спасибо
9:30 - Pair?
Блин, зачем ты заспойлерил стек в названии( теперь непонятно, сам ли я до стека додумался или ты подсказал
а еще что будет ? а то 4 задачи и все
Кажется, если стек пустой, то нужно добавить в массив ответов 0 для текущей температуры i
Там создаётся массив и в Яве там итак будут нули (в отличии от си или спп)
Ох и багов будет в такой проге
Тут описана работа стека как будто поставить жирафа в холодильник: открыл холодильник, поставил жирафа, закрыл холодильник. Но в действительности можно очень при этом вспотеть. Разве компилятор не делает кучу подкапотной работы при манипуляции со стеклом?
Можно и слева-направо ответы получать тем же способом
А чем плоха рекурсия?
Если элемент справа есть и он больше текущего, то =1 и идём дальше, иначе считаем значение для правого элемента +1
Я не умею в эту вашу Яву, но стек городить тут не нужно. Идём слева направо, для i-го дня ищем следующий с большей температурой (k-й). Когда находим, заполняем все дни с i-го по k-1-й количеством дней до k-го (его даже считать каждый раз не надо, считаем 1 раз и потом уменьшаем на единицу), потом i=k и всё повторяем.
И это правда _хитрая_ задача? Может Яву освоить тогда, в ней вроде платят хорошо.
Дано: [8, 6, 7, 9]. В вашем случае выйдет результирующий массив [3, 2, 1, 0], тогда как правильный - [3, 1, 1, 0].
Очень странное решение, вместо того чтобы записывать в стек все левые числа и каждое новое сверять с поледним в стеке и как только найдем большее собирать инфу и очищать стек, вы решили пройти с конца и чекать постоянно весь стек...
И вышло что Вы к первому решению прикрутили еще и стэк
Лучше рекурсия + динамическое с Хеш-мапой, как по мне. answer[i] = answer[i-1]+1 || 1 || 0
на рекурсию может просто памяти не хватить при больших массивах данных
@@user-gk2kn3ri7z Рекурсия внутри єто тот же стек. Главное запоминать результат в hashMap для посчитаньіх уже ответов.
мне в голову пришло решение с рекурсией. если следующий элемент больше текущего, то ответ 1. иначе берем значение рекурсивной функции следующего элемента и если оно больше нуля, то прибавляем к нему 1 и это будет наше значение. а если значение функции следующего элемента 0, то и наше значение 0.
@via6274 Хорошая идея, сначала даже поверил в неё, но ломается например на последовательности 3 1 2
@@Docik86 да. я это понял тоже почти сразу. не стал удалять коммент 🙂
Спасибо за решение. Только вот во внешнем цикле из t.Length следует вычесть единицу, иначе будет выдана ошибка о выходе за пределы массива. Удачи.
a spoiler in the title
амортизированная линия, а не обычная получается
Обычная линия, при чем тут амортизированная?
Совсем небольшое дополнение, нам по идее понадобится условие для самой первой итерации, чтобы сохранить 0
0-ой элемент в любом случае будет сохранён, зачем условие?
Можно хранить в стеке комплексные числа, в которых есть 2 инта. Не по назначению, но без велосипедов
ну это простенький алгоритм, на этих собесах алгоритмы по сложнее задают, а потом забивают вопросами про линух
На мой взгляд стек тут явно лишний.
Следующий вариант не использует стек совсем, и имеет такое же время работы.
Используем тот факт, что используя заполненную часть массива answer и исходный массив всегда можно пройти по "элементам стека"
public int[] temperatures(int[] t) {
int[] answer = new int[t.Length];
answer[t.Length - 1] = 0;
for (int i = t.Length - 2; i >= 0; i--) {
int next = i + 1;
while (t[i] >= t[next] && answer[next] > 0) {
next += answer[next];
}
answer[i] = t[i] < t[next] ? next - i : 0;
}
return answer;
}
Очень хорошее решение! Но по-моему здесь такой же по температуре день ломает логику.
@@Vitek_23 Спасибо, изменил строгое равенство на нестрогое, теперь логика не ломается.
Жаль что пропал(
Прекрасное решение со стеком. Взял на вооружение. Думаю, что автору нужно брать и еще профайлить свой код, для того чтобы учесть архитектуру современных процессоров.
В общем если алгоритм будет не кэш-френдли, а именно будут происходить частые мисы в кэш, то это может сильно ухудшить время работы алгоритма. В общем при большом массиве может результат не таким однозначным и первый вариант будет выигрывать по скорости потому что он всегда ходит вперед. В общем нужны тесты.
Сложность от кэш френдли не измениться, конечно, но в практическом плане для стека по идее будут операции с более близко расположенными значениями по памяти происходить, соответсвенно реже мисс кэша, ибо первое правило кэширования - по расстоянию (по крайней мере во всех известных мне аппаратных архитектурах).
На интервью это как правило не спрашивают, если только вас не нанимают писать драйверы.
Оптимизация под архитектуру оправдана только в том случае, если у вас cpu-bound процесс, что в общей массе кода - редкость, обычно на I/O затык все равно.
@@kostyajan Ну конечно изменится. При грамотном опережении префетчинга для X86_64 и изоляции ядра, вариант без стеков раз в 100 быстрее будет. Оно по этой цепочке раз 10 туда обратно успеет сходить, пока вы единственную операцию new будете делать. Это, если распараллеливание на ядрах не эксплуатировать. А если эксплуатировать то и в 1000 раз быстрее может будет. Конвеер одного ядра вообще-то давно уже не линейно работает, а с опережающим предсказанием. Вообще все эти рассуждения про сферические сложности O(n) - это только для навешивания лапши на уши кандидатов при собеседовани годится. Самая дорогая операция для процессора это копирование, а для ОС - выделение памяти при первом в нее обращении. А циклы внутри кэша это вообще не time consuming ни разу (вы их даже штатными таймерами наносекндными с трудом измерить сможете), ну если конечно вы не в яве живете. Там, конечно, трэш полный.
@@alexyevdokimov642, сложность это про зависимость количества операций от объема данных а не про скорость выполнения алгоритма в каких то архитектурах. Ну и сложность конечно не изменится.
@@kostyajan А как вы узнаете кол-во операций, если вы в суть вдаваться не хотите?
uint32_t a = *(uint32_t*)(0xFABCE00045123625);
uint32_t b = (uint32_t)(*(uint8_t*)(0xFABCE00045123625 + 256));
По вашему для при своения a и b нужно однинаковое кол-во операций или разное?