И это задача на 150 000$ ?! Я прошел собес в Amazon
ฝัง
- เผยแพร่เมื่อ 23 ก.ย. 2024
- Друзья! Решил поделиться задачей, которая мне попалась на самом настоящем собесе в Amazon, а точнее ее детальным решением!
Кто бы мог подумать, что одна из самых популярных задач на LeetCode будет на алгоритмическом собеседовании на позицию Senior Software Engineer c зарплатой в 150.000$ в год!
В видео рассказал и показал каждый шаг своих действий! Приятного просмотра!
Ссылка на мой ТГ-канал: t.me/+9fKb_X2W...
Обучение:
Java Буткемп: www.faang.scho...
Java Magics. Бесплатный курс для начинающих: www.faang.scho...
Бесплатные материалы для подготовки к собесам:
www.faang.scho...
Социальные сети:
Instagram: / faang.school
LinkedIn: / vlad-mishustin
ТГ-канал "Road to FAANG": t.me/fakng_eng
ТГ-сообщество FAANG School - t.me/+fgoLmBk0...
ДИСКЛЕЙМЕР
Любая информация, высказанная в данном видео является моим личным мнением и никак не относится и не отражает позиции моего работодателя или любых связанных со мной организаций.
Любой код, документация, логи или диаграммы, показанные в видео, являются моими личными макетами, написанными/созданными в мое свободное время на своей собственной машине, конкретно для демонстрации в роликах, никак не относясь и не используя интеллектуальную собственность моего работодателя или любых связанных со мной организаций.
Блестящий разбор задачи! Спасибо большое, Влад, ценю все твои видео, ты молодец!
Влад, спасибо за видео, очень интересный формат, хотелось бы побольше такого контента с разбором задач
Спасибо за разбор задачи , очень интересно и познавательно. Хотелось, чтобы еще больше было подобных выпусков)
Видос топовый, так и продолжай❤😊
Придумал решенин за О(nlogn)
1. Бежим по элементам массива, но не по порядку, а по возрастанию высоты столбцов
2. Тогда для текущей высоты мы точно знаем высоту контейнера (она равна текущему элементу, так как бежим по возрастагию, значит, высот меньше просто нет, а предыдущие уже не учитываем)
3. Раз для любого второго слобца высота контейнера будет одинакова, то для максимизации площади нужно выбрать самый дальний столбец (высота не важна)
4. Создаем массив visited, заполненный нулями (если посетили i-ый стробеу, то visited[i] = 1), и два указателя - на первый и последний элемент (это максималтно близкие непосещенные стробцы к левой и правой стороне)
5. Если посещенный столбец совпал с указателем, то двигаем его вправо (если он левый) и влево (если он правый) до тех пор, пока visited[i] не будет равен 0
6. Пробегаясь по всем столбцам в порядке возрастания их высот, мы можем находить наибольшую площадь контейнера, используя указатели
Да, решение не за O(n) и память не О(1), но вот такое решение придумал)
Если бы мне выпала эта задача я бы прошёл собеседование )) Удивительно что ее спросили на senior позицию. Проблема в том что hard задачи это реальность в больших компаниях сейчас.
Продолжай в том же духе. Такое интересно
Супер разбор, четко и понятно. Спасибо)
Влад, спасибо большое, такие разборы очень помогают! А сможешь в одном из следующих видео разобрать многопоточность? Думаю это может быть многим полезно
Немного ошибся ниже с крайних значений обоих мы не отнимаем не чего верно, а в серединке мы отнимаем пол объема, но если четный то серединки две и пол объема минус 1)
вот с одним циклом мысль пришла с утра
for (int i = 0; i < length; i++) {
int index = (i < mid) ? i : length - 1 - i;
int result = array[i] - index;
indexMax2 = (result > max1) ? indexMax1 : (result > max2 ? i : indexMax2);
max2 = (result > max1) ? max1 : (result > max2 ? result : max2);
indexMax1 = (result > max1) ? i : indexMax1;
max1 = (result > max1) ? result : max1;
}
Я думаю в будущем ты станешь очень важной личностью если будешь так же продолжать!
Лол, Влад уже стал локомотивом индустрии и ютуба😊
Интересуюсь для себя, чтобы быть в теме(сын программист, хочется быть осознанной в беседе). Решила задачу с ходу. Теперь думаю, а точно ли врач - это моё 😂
Лучшая компания -- это та, где именно тебе лучше всего, а не это вот всë.
Думаю если дано n столбов высоты h(i) i=1, 2,..., n, то для каждого такого столба соответствует n-1 длина l. Я думаю построить матрицу nxn где в первой строке будут записаны высоты, а в нижних строках будут записаны длины для каждой из высот. Н -р, в первом столбике на первой строчке высота h(1) а под ней в остальных n-1 строках соответствующие ей длины. Так вот, берем под каждой высотой максимальную длину, перемеожаем каждую из полученных длин со своей высотой, получаем список состоящий из значений площадей, находим максимум этого списка. Но я не знаю насколько верно это решение🤔
вот это ты даёшь конечно
Привет. Спасибо за видео. 5 месяцев назад вышло видео на канале про собеседование в амазон и оно совершенно противоречит этому. На этот раз тоже были все эти 5 собеседований подряд или условия отбора изменились?
Крутяк, спасибо
Привет! На каком уровне изучения Java нужно учить алгоритмы? Я понимаю, что достаточно иметь базовые знания, но если так, чтобы двигаться по road map какой-то?
Все инфо цыгане как раз говорят что чтобы получить road map нужно пойти к ним на курсы, иначе растратишь время на изучение не нужных технологий, так что видимо бесплатно этой информации не планируется (так как это снизит смысл идти на курсы)..
Алгоритмы нужно учить с самого начала, это база. Язык программирования тут вообще не важен.
решал год назад, но все равно было интересно)
Привет , круто , молодец
Если в первой итерации допустим мы получили самое большое значение "max", после других итерации значение в "max" не испортится?
Одна из самых легких задач на литкоде. Не может быть чтоб ее давали даже мидлам
Доброго времени суток! Извените, Я бы хотел узнать ваше мнение.
Как вы относитесь к накрутки опыта в разработке?
Если другие варианты?
У меня сейчас 2 резюме и единственное, что в них различается, это количество опыта, но на одном 2 отлика (о опыта), а на другом 27 (1.7 опыта)
Супер
А зачем воду в столбики наливать ?😢
Привет,
Влад, я не силен в алгоритмах, но можно ли сделать так, чтобы эти указатели работали так:
Первый шел с начала массива,
А второй с конца.
Так ты сразу будешь искать максимальную дистанцию и максимальное значение.
Это не правильное решение?
Я не понял. В решении и так первый указатель идёт от начала, а второй от конца.
Все равное не понимаю, сужая стрелки, вы же не проверите расстояние между 3 и 9,...как будто вообще игнорируем некоторые расстояния, мне кажется в тесте этот метод не выдержит, при больших массивах
решил за 2 минуты )))
Имеет ли смысл проходит до конца, пока два указателя встретятся? Если мы знаем что максимальная высота стенки 8, а максимальная площадь 49, то если расстояние между двумя указателями будет меньше 7 (7*8 дадут нам новое максимальное значение) то процесс можно останавливать.
а программа как будет знать что 8 это максимальная высота стенки?
@@hankie5 встроенные функции языка max() я так понимаю использовать нельзя?
Можно, но это сразу один полный проход по неупорядоченному массиву, О(n). Ну и по большому счету он не даст дополнительной информации, так как все равно в ходе выполнения предлагаемого алгоритма этот проход по всем элементам будет сделан, получим только лишний проход
Думаю будет эффективнее если сначала сортировать значения столбов и ноль далее берем середину и будем идти от середины и умножаем число на себя в. Конце берем самый большое число таким же способом находим слева
Можете подсказать, почему у второго алгоритма сложность 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). Те со сложностью легко понять как будет масштабироваться алгоритм / система / микросервисы на выросшее кол-во входных данных / запросов / пользователей
На 15-00 график то линейный показал а не квадратичный )))))
Как отключить субтитры
всё амазон не отпустит Влада никак)
Старнно, что задача уровня medium. Объяснение хорошее, но так дотошно рассатривать такую незамысловатую задачу думаю смысла нет, складывается ощущение, что ребенку объясняешь.
Вы видимо в Amazon работаете?
Эти задачи ведь Chat-GPT скоро сможет решать, нет?
Он уже спокойно решает
аахаах я новичок но решил это задачу за 10 минут
♥
Минус за кликбейт
Простая задача, сходу решил
Ты уже работаешь в 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
Ттт
И тут я понял, что программистом я быть не хочу😂
Влад Привет! Я бы решил эту задачу так.
Прохожу по маcсиву с лева на права и отнимаю у всех i (то есть у первого элемента - 1 у второго -2 и т.д.), то есть отнимаю по сути номер ячейки =сохраняю в массив под названием лефт,
прохожу с права на лево по оригиналу и также минусую по -1 ,от самой правой не минусую естественно сохраняю ?называю его райт.
далее берем индекс в лефте где самое большое число в случае дублежа
и в райте берем наибольшее число
int[] left = new int[originalArray.length];
int[] right = new int[originalArray.length];
for (int i = 0; i < originalArray.length; i++) {
left[i] = originalArray[i] - i - 1;
right[originalArray.length - 1 - i] = originalArray[originalArray.length - 1 - i] - i;
}
int maxLeftIndex = 0;
int maxRightIndex = 0;
for (int i = 1; i < originalArray.length; i++) {
if (left[i] > left[maxLeftIndex]) {
maxLeftIndex = i;
}
if (right[i] > right[maxRightIndex]) {
maxRightIndex = i;
}
}
Да два цикла фор - второй то бы вычислить наибольшее число, но они не вложены в друг друга
А ваще думаю можно сделать и лучше
Проходимся одним циклом под индексом 0 от числа отнимаем i и летс(длину)
Вариант два
берем массив чисел и если его количество ячеек не четное, то делит на два и начиная от серединки отнимает от чисел по половине длины массива, но с каждым шагом отнимается половина длины массива минус-1. То есть напимер массив на 8 ячеек значит у его ячеек под индексом 3 и 4 у чисел отнимаеься по 4, у ячеек 2 и 5 по 3, у ячеек 1 и 6 по 2 и у ячеек 0 и 7 по 1. Ну а если количество ячеек нечетное то серединки отнимаем половина количества ячеек плюс 1.
Затем выбираем два индекса где самые большие числа, но если например одно из самых больших чисел повторяется пофигу брать можно любое, так как это дина и ширина по сути казалось бы ведь самое левое например значение 17 под индексом 0, лучще чем значение 17 под индексом 2 - но нет тк как проще говоря значение 17 под индексом два стартануло просто больше при вычитании потому-что оно правее - таким образом вывод берм любое - площадь будет одинаковая.
вот код второго варианта решения
public static void myMethod(int[] massiv) {
int dlina = massiv.length;
int polovina = dlina / 2;
for (int i = 0; i < polovina; i++) {
int smeshenie = polovina - i;
massiv[i] -= smeshenie;
massiv[dlina - 1 - i] -= smeshenie;
}
if (dlina % 2 != 0) {
massiv[polovina] -= (polovina + 1);
}
int firstMaxIndex = 0;
int secondMaxIndex = 1;
if (massiv[secondMaxIndex] > massiv[firstMaxIndex]) {
firstMaxIndex = 1;
secondMaxIndex = 0;
}
for (int i = 2; i < massiv.length; i++) {
if (massiv[i] > massiv[firstMaxIndex]) {
secondMaxIndex = firstMaxIndex;
firstMaxIndex = i;
} else if (massiv[i] > massiv[secondMaxIndex]) {
secondMaxIndex = i;
}
}
System.out.println("Индекс первого самого большого числа: " + firstMaxIndex);
System.out.println("Индекс второго самого большого числа: " + secondMaxIndex);
}
}
00:00 - услышал голос. Вырубил видео. Кринж.
О нет, только не это, прошу...