И это задача на 150 000$ ?! Я прошел собес в Amazon
HTML-код
- Опубликовано: 19 дек 2023
- Переходи по ссылке и начни разбираться в алгосах уже сейчас: www.faang.school/algorithms-f...
Друзья! Решил поделиться задачей, которая мне попалась на самом настоящем собесе в Amazon, а точнее ее детальным решением!
Кто бы мог подумать, что одна из самых популярных задач на LeetCode будет на алгоритмическом собеседовании на позицию Senior Software Engineer c зарплатой в 150.000$ в год!
В видео рассказал и показал каждый шаг своих действий! Приятного просмотра!
Ссылка на мой ТГ-канал: t.me/+9fKb_X2Wixw4ODAy
Обучение:
Java Буткемп: www.faang.school/?...
Курс "Алгоритмы с нуля": www.faang.school/algorithms-f...
Курс "Подготовка к собеседованию в IT": www.faang.school/product-inte...
Java Magics. Бесплатный курс для начинающих: www.faang.school/java-magics?...
Социальные сети:
Instagram: / faang.school
LinkedIn: / vlad-mishustin
ТГ-канал "Road to FAANG": t.me/fakng_eng
ТГ-сообщество FAANG School - t.me/+fgoLmBk0B1EyODk0
ДИСКЛЕЙМЕР
Любая информация, высказанная в данном видео является моим личным мнением и никак не относится и не отражает позиции моего работодателя или любых связанных со мной организаций.
Любой код, документация, логи или диаграммы, показанные в видео, являются моими личными макетами, написанными/созданными в мое свободное время на своей собственной машине, конкретно для демонстрации в роликах, никак не относясь и не используя интеллектуальную собственность моего работодателя или любых связанных со мной организаций.
Влад, спасибо за видео, очень интересный формат, хотелось бы побольше такого контента с разбором задач
Спасибо за разбор задачи , очень интересно и познавательно. Хотелось, чтобы еще больше было подобных выпусков)
Видос топовый, так и продолжай❤😊
Блестящий разбор задачи! Спасибо большое, Влад, ценю все твои видео, ты молодец!
Супер разбор, четко и понятно. Спасибо)
Влад, спасибо большое, такие разборы очень помогают! А сможешь в одном из следующих видео разобрать многопоточность? Думаю это может быть многим полезно
Продолжай в том же духе. Такое интересно
Привет. Спасибо за видео. 5 месяцев назад вышло видео на канале про собеседование в амазон и оно совершенно противоречит этому. На этот раз тоже были все эти 5 собеседований подряд или условия отбора изменились?
Доброго времени суток! Извените, Я бы хотел узнать ваше мнение.
Как вы относитесь к накрутки опыта в разработке?
Если другие варианты?
У меня сейчас 2 резюме и единственное, что в них различается, это количество опыта, но на одном 2 отлика (о опыта), а на другом 27 (1.7 опыта)
Крутяк, спасибо
Придумал решенин за О(nlogn)
1. Бежим по элементам массива, но не по порядку, а по возрастанию высоты столбцов
2. Тогда для текущей высоты мы точно знаем высоту контейнера (она равна текущему элементу, так как бежим по возрастагию, значит, высот меньше просто нет, а предыдущие уже не учитываем)
3. Раз для любого второго слобца высота контейнера будет одинакова, то для максимизации площади нужно выбрать самый дальний столбец (высота не важна)
4. Создаем массив visited, заполненный нулями (если посетили i-ый стробеу, то visited[i] = 1), и два указателя - на первый и последний элемент (это максималтно близкие непосещенные стробцы к левой и правой стороне)
5. Если посещенный столбец совпал с указателем, то двигаем его вправо (если он левый) и влево (если он правый) до тех пор, пока visited[i] не будет равен 0
6. Пробегаясь по всем столбцам в порядке возрастания их высот, мы можем находить наибольшую площадь контейнера, используя указатели
Да, решение не за O(n) и память не О(1), но вот такое решение придумал)
вот это ты даёшь конечно
Привет , круто , молодец
Привет! На каком уровне изучения Java нужно учить алгоритмы? Я понимаю, что достаточно иметь базовые знания, но если так, чтобы двигаться по road map какой-то?
Все инфо цыгане как раз говорят что чтобы получить road map нужно пойти к ним на курсы, иначе растратишь время на изучение не нужных технологий, так что видимо бесплатно этой информации не планируется (так как это снизит смысл идти на курсы)..
Привет,
Влад, я не силен в алгоритмах, но можно ли сделать так, чтобы эти указатели работали так:
Первый шел с начала массива,
А второй с конца.
Так ты сразу будешь искать максимальную дистанцию и максимальное значение.
Это не правильное решение?
Я не понял. В решении и так первый указатель идёт от начала, а второй от конца.
Я думаю в будущем ты станешь очень важной личностью если будешь так же продолжать!
Лол, Влад уже стал локомотивом индустрии и ютуба😊
Думаю если дано n столбов высоты h(i) i=1, 2,..., n, то для каждого такого столба соответствует n-1 длина l. Я думаю построить матрицу nxn где в первой строке будут записаны высоты, а в нижних строках будут записаны длины для каждой из высот. Н -р, в первом столбике на первой строчке высота h(1) а под ней в остальных n-1 строках соответствующие ей длины. Так вот, берем под каждой высотой максимальную длину, перемеожаем каждую из полученных длин со своей высотой, получаем список состоящий из значений площадей, находим максимум этого списка. Но я не знаю насколько верно это решение🤔
Если в первой итерации допустим мы получили самое большое значение "max", после других итерации значение в "max" не испортится?
решал год назад, но все равно было интересно)
Интересуюсь для себя, чтобы быть в теме(сын программист, хочется быть осознанной в беседе). Решила задачу с ходу. Теперь думаю, а точно ли врач - это моё 😂
Супер
Можете подсказать, почему у второго алгоритма сложность O(n), насколько я понимаю в нем сложность определяется наилучшим сценарием, верно?
я так понимаю, потому что мы проходимся по элементам один раз, если два раза, то n*n. Если три раза, то N*N*N. Чем больше итераций, тем сложнее.
@@felixvoid5521 Если мы проходимся по массиву несколько раз, это не всегда квадратичная сложность. Например, в первый раз собрали префикс суммы, второй раз прошлись, сделали с ними что нибудь. То такая сложность будет O(n+n) -> O(2n) но не O(n^2).
Для квадратичной сложности нужно для каждого элемента в массиве, проходится по массиву снова. Это можно выразить как O(n1+n2+n3 ... n n-1+ n n).
@@felixvoid5521 Сложность алгоритмов нужна, чтобы ответить на вопрос, как измениться время программы/запроса если кол-во данных увеличиться в неск. раз. К примеру в 2 раза. Если в вашем алгоритме "двойного/тройного прохода по массиву" элементов стало вдвое больше. То вам придется сделать просто вдвое больше операций, что займет вдвое больше времени. Т.е линейная зависимость O(n). Если новое время исполнения будет в 4 (= 2^2) раза больше прежнего, то сложность квадратичная O(n^2). Те со сложностью легко понять как будет масштабироваться алгоритм / система / микросервисы на выросшее кол-во входных данных / запросов / пользователей
Как отключить субтитры
Имеет ли смысл проходит до конца, пока два указателя встретятся? Если мы знаем что максимальная высота стенки 8, а максимальная площадь 49, то если расстояние между двумя указателями будет меньше 7 (7*8 дадут нам новое максимальное значение) то процесс можно останавливать.
а программа как будет знать что 8 это максимальная высота стенки?
@@hankie5 встроенные функции языка max() я так понимаю использовать нельзя?
Можно, но это сразу один полный проход по неупорядоченному массиву, О(n). Ну и по большому счету он не даст дополнительной информации, так как все равно в ходе выполнения предлагаемого алгоритма этот проход по всем элементам будет сделан, получим только лишний проход
Одна из самых легких задач на литкоде. Не может быть чтоб ее давали даже мидлам
Старнно, что задача уровня medium. Объяснение хорошее, но так дотошно рассатривать такую незамысловатую задачу думаю смысла нет, складывается ощущение, что ребенку объясняешь.
Эти задачи ведь Chat-GPT скоро сможет решать, нет?
Все равное не понимаю, сужая стрелки, вы же не проверите расстояние между 3 и 9,...как будто вообще игнорируем некоторые расстояния, мне кажется в тесте этот метод не выдержит, при больших массивах
♥
решил за 2 минуты )))
всё амазон не отпустит Влада никак)
Простая задача, сходу решил
Ты уже работаешь в faang?
@@Dmitry__Ershov нет, да и не планировал пока
Думаю будет эффективнее если сначала сортировать значения столбов и ноль далее берем середину и будем идти от середины и умножаем число на себя в. Конце берем самый большое число таким же способом находим слева
Минус за кликбейт
Вот вот 100 тысач....
99.9 сейчас😁
Уже
Если прям совсем точно то у первого алгоритма скорее n! (факториал) вариантов, так как с каждым шагов второй итератор проходит на 1 меньше
Точно не n!.
Первый итератор проходит n шагов. Второй - на первой итерации n-1, на второй - n-2, ... на n-ой итерации - 0 шагов. По сути проходов n (первый итератор) + 1 + 2 + 3 + ... + n-1 = n + сумма арифметической прогрессии от 1 до n-1 = n + (n-1)(n-2)/2 => O(n^2/2 + остальные менее значимые части многочлена) => опускаем множитель и младшие члены многочлена => O(n^2)
Ттт
0
И тут я понял, что программистом я быть не хочу😂
00:00 - услышал голос. Вырубил видео. Кринж.
О нет, только не это, прошу...