Задача с собеседования в Google на $200.000
HTML-код
- Опубликовано: 20 май 2024
- Алгоритмы с нуля по ссылке: www.faang.school/algorithms-f...
Какие задачи надо решать собеседованиях в Google, чтобы получить оффер с зарплатой более $200 000 в год? И смог ли я это сделать? Узнаем из нового видео!
В этом ролике я подробно разбираю решение алгоритмической задачи, которая мне попалась на собеседовании с инженером из Google.
Приятного просмотра!
00:00:00 - Вступление
00:03:49 - Пример
00:05:55 - Объяснение
00:08:37 - Непроизводительное решение
00:16:32 - Первый код
00:17:45 - Правильное решение
00:25:22 - Второй код
00:26:32 - Заключение
Обучение:
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
ВК: faang.school
ТГ-канал "Road to FAANG": t.me/fakng_eng
ДИСКЛЕЙМЕР
Любая информация, высказанная в данном видео является моим личным мнением и никак не относится и не отражает позиции моего работодателя или любых связанных со мной организаций.
Любой код, документация, логи или диаграммы, показанные в видео, являются моими личными макетами, написанными/созданными в мое свободное время на своей собственной машине, конкретно для демонстрации в роликах, никак не относясь и не используя интеллектуальную собственность моего работодателя или любых связанных со мной организаций.
Я бы просто насрал if, if else и с позором завершил собес
Спасибо что делишься такой важной инфой для нас)
Очень интересно. Такие видео с разбором задач пожалуй лучший контент)
Спасибо,полезное и заряжающее видео,в прочем как обычно)❤️
Влад, шикарное видео! Делай, пожалуйста, как можно больше разборов таких задач! будем лайкать каждое видео!!
Топ контент! Ушел решать задачу))
Очень полезное видео. Хотелось бы больше видео такого формата
Крутой контент! Продолжай!💪
Влад, вы просто супер мастер, это потрясающе, я восхищена
Спасибо за Ваш труд! Коммент в поддержку канала.
Супер ролик, спасибо
спасибо, классное видео и интересная задача
Интересная задача на подумать, теперь хочется ее на Python сделать 👍
До просмотра решения. Возможно в алгоритме сделать условие поведения в зависимости от 4х цифр:
1) есть ли 0
2) есть ли числа от 0 до 1
и в зависимости от того какой индекс конкретного числа
Поставил на паузу в начале видео. Решил эту задачу. Меня не учили лучшие преподаватели по алгоритмам из лучших бигтех компаний
Топчик!
Владос лучший ! Если не сложно , ответь на вопрос .
Развиваюсь в сфере аналитики и мне интересно знать , как в FAANG обстоят дела с данным направлением , либо может поделишься где можно узнать информацию насчет аналитических направлений в биг тех ?
Ахуенный видос, продолжай в том же духе 🔥
Интересная задача. Тоже поймал себя на greedy не учитывая constrains, но об этом нужно сразу уточнять. По факту наличия минуса в голову пришло хранить в массиве, но это не оптимально, так как дает пространственно линейную сложность. Остаётся выход использовать переменную для константной сложности.
больше таких роликов)
Очень интересно спасибо. Разбор очень крутой все понятно)
остановил на 8:07, пишу примерное свое решение. в целом еще до пояснений стало понятно, что могут быть отрицательные числа, 0 и от 0 до 1.
Дальнейшие размышления: нам надо для каждого следующего числа проверять в какой диапазон он попадает и в зависимости от этого применять знак.
Для начала забываю про то, что формируемый результат может быть отрицательным. Главное увеличивать число, положительный знак попробую выставить правильным количеством операций. По идее, если на отрицательные числа умножать/делить четное количество раз, то все будет хорошо) Тогда:
0 как правило лучше прибавлять/отнимать (одно и тоже),
на числа от 0 до 1 (не включительно) и от 0 до -1 делить,
1 прибавлять, -1 отнимать (либо использовать для корректировки знака).
на те, что >1 и
спасибо
Проход по массиву за n
Дальше конструкции иф , елсе иф, елсе с проверками: 1 число отрицательное - знак минус, =1 или =0 - знак плюс, 0
Не правильно, если что
[4.0, -2.0, -5.0] выдаст 11,
а ожидалось 40.0
в такой ситуации все тоже самое, только сначала считаем количество отрицательных чисел, если четное то при отрицательном числе умножение, если нечетное то перед отрицательным числом умножение, но перед последним отрицательным числом минус. Проходя по массиву можно просто считать количество отрицательный@@persssotami
@@persssotami Просто в голос хохочу с таких организмов, которые указывают кому-либо на ошибки и при этом демонстрируют собственную безграмотность... вдвойне смешнее, когда такие типы говорят о том, что что-то *неправильно* и при этом даже не знают как *правильно* это слово пишется 😂😂😂
Писал код на питоне, пока не смотрел продолжение, но написал довольно быстро, не верится что задача такая простая… (это не Хейт, наоборот, уважение автору за разминку для мозгов!!🤝)
Логика следующая:
Брать каждую пару чисел в массиве (за счет цикла for) и находить максимальный результат действий с ними (для этого написал функцию, только надо учесть что числа могут быть 0.0, в функции результаты всех действий беру в массив и возвращаю максимальное число), а после результат подставляю на место второго числа в паре, чтобы дальше идти по циклу.
После окончания цикла ответом будет последнее число в массиве, оно же - максимальное
АПД: очень круто, я понял в хитрость задачи, я в гугл не прошел 😂😂
Точно так же решил 😅
Ну да, вариант у тебя более наглядный с точки зрения кода, его будет проще понять тому, кто будет потом разбираться. Согласен.
Первое что в голову пришло это пройтись циклом и вложенными тернарнеми операторами соблюсти условия на ноль и отрицательные числа 🤔 Посмотрим теперь какое решение😅
Мда, условие нужны от i = -1 то +, еще и знаки учесть нужно, потом n += i или n *= i.
По производительности конечно нужно проверить.
После просмотра видео пришла еще мысль запустить цикл, переменная n равна первому числу. Потом берем в каждой итерации цикла четыре переменные полученые с разными знаками и присваиваем максимальное полученное значение n = Max(x1, Max(x2, Max(x3, x4))). Так пробегаем по массиву.
то есть можно просто прорешать наиболее частые задачи или даже заучить и попасть на высокую позицию?
🔥
А я подумал, что мы можем брать любые соседние элементы массива, применять к ним операцию, а затем записывать новый элемент вместо этих двух. То есть не обязательно идти по порядку: на любом шаге берём любые a[i] и a[i+-1] (рядом стоящие элементы), получаем new_elem посредством применения определённой операции к a[i] и a[i+-1], кладём его на i-ое место, а[i] и a[i+-1] удаляем. Такая задача была бы сильно сложнее, хотя возможно, это и подразумевалось.
Влад с интенсива будут видео?
Ну это простая задача, линейный алгоритм с одним проходом. Нам нужно сохранять два массива операций, некое ветвление, когда попадается отрицательное число, а наш сумматор положительный, ибо, если он отрицательный, вычисляем, что будет больше, вычесть минус (для сумматора близкого к нулю) или умножить но новое отрицательное и получить большее положительное. Как только оно попалось, в первом массиве храним "безопасный вариант" с вычитанием, а параллельно сохраняем вариант с умножением и переходом в минус для сумматора. Как только нам попалось еще одно отрицательное, его домножаем и делаем второй вариант решения основным, а если до конца массива минусов больше не попалось, то исходный безопасный остается. Для чисел меньше 1 по модулю делаем деление, ну и для отрицательных так, как выше было описано, только с заменой умножения на деление. Если попадается ноль, то просто ставим плюс. Теперь посмотрим видео дальше, что же ты предлагаешь :) Кстати, звук очень тихий, либо надо прямо в микрофон говорить, либо усиление громкости сделать...
5:50 - так мы ищем максимум как результат всех операций, или мы должны вернуть такую последовательность операций, которые дадут максимальный результат?
Если второе, то у нас сложность по памяти O(N)
Для Макс мин не нужно сравнение?, можно использовать готовое?
можно поробовать накапливать результат выражения и применяя каждую операцию проверять стало ли накопленное число больше, если меньше, то другая операция и так до конца массива
Влад Крутоо!!!!!
Есть вопрос: если проставить действия сразу?: то тогда даже с первым набором цифр, результат другой если считать по правилам математики: типа умножение первое делать... если считать отдельно каждый раз пошагово так сказать может стоить прописать условия для операций: А) если число 0, то /; (но тут надо добавить неравенство - если оба числа меньше ед... типа, чтобы деление было больше сложения и еще условие для отриц. чисел... тоже проверить)б) если число 1, то +; в) если одно число (+) положит, а другое (-) отриц., то * или -; г) если число = 0, то + (чтобы не занулять результат) ; д) если оба положительные, то *; и е) если оба числа отрицательные, то *. Тогда вообще легко: действия отсеиваются сразу...
Что-то слишком простая задача, решается сходу. Тянет на изи на литкоде, может медиум-
Если за такое 200к$ платят, то я что-то делаю не так
Как решить задачу, если проходиться не последовательно? У меня в голове есть решение и вроде как o(n*n) . Это правильно?
Дайте ссылку на литкод с этой задачей, кто нибудь
Как насчет этого варианта решения?
double[] nums = {1,-3,0.1,-5};
Arrays.sort(nums);
double max;
for (int i = 1; i < nums.length; i++) {
max = nums[i-1]*nums[i];
double d = nums[i - 1] / nums[i];
double sum = nums[i - 1] + nums[i];
double minus = nums[i - 1] - nums[i];
if(d > max) max=d;
else if(sum > max) max = sum;
else if(minus > max) max = minus;
nums[i] = max;
}
System.out.println(nums[nums.length-1]);
И здесь во втором примере же ответ должен же быть 151? Или по условии задачи последовательность чисел в массиве нельзя менять?
Не могу зайти в телегу, при отправке формы сайт кидает ошибку
1. Хранить последное число в переменную last_num
2. Проделать все операции с последним и текущим числом
3. Получить максимальное число из полученных результатов, и хранить в переменную max_num
4. Установить max_num в last_num
P.S: Не учел отрицательные числа)
Интересно где-нибудь на литкоде она есть
Первое что пришло в голову - перебор всех вариантов. По ресурсам не очень хорошо, зато работать будет
Привет! Спасибо за видео. У меня вопрос почему при сложении числа "-3" с числом "1" у тебя получается "4"?
Потому что он взял вычитание сначала 1-(-3), а минус на минус дает +, и как следствие 1+3
Довольно плохое решение я считаю, но
1)отсортировать массив
2)и проходясь по циклу ставим на все возможные варианты условия(например если меньше единицы и больше -1 прибавляем или отнимаем, а если меньше -1 умножаем или ой чет запутался )
Знаю что очень плохое решение, но это то что пришло в голову в первую очередь
Смотрю дальше!
Если отсортировать массив, то нарушится порядок действий + nlogn уже неоптимально
так там нельзя сортировать
А обязательно ли брать всн числа в массиве последовательно. Во втором примере видно, что если нарушить последовательность, можно получить больший результат
Нельзя. В условии задачи операторы можно вставлять только между двумя соседними элементами.
Автор сказал, не меняя последовательность чисел.
Решение последнего примера сделано неверно. В первых вычислениях получилось число -0,33, Влад его зачеркнул. Но если мы умножим 0,1 на -0,33, то получится -0,033. Дальше делим -5 на -0,033 и уже получается 151,52 примерно. Этот ответ уже больше того, который получился способом Влада. Думаю, что там возможны и другие хитрости, которые я не рассмотрел. Так что решение Влада не даёт самого-самого максимального ответа, особенно если в массиве много дробных чисел. Забавно, что сам Влад постоянно упоминал про нюансы с дробями, но не учёл их
Так а почему вы поменяли числа местами и делите -5 на -0,033?
Чтобы получить максимум с дробями, нужно большее число разделить на маленькое, т.е. стратегия получения максимума остается верной
по условию нельзя -5 делить на -0.033
-5 последнее число в массиве, можно только делать действия с ним вторым номером: умножить / отнять / поделить / сложить -> и тут максимальное значение будет -0.033 * (-5) = 0.165
time complexity 4^n. Первый пример - 3 елемента в массиве, но операций далеко не 64. Или это не так работает?
по факту 4^(n-1), но константы упускаем, поэтому просто 4^n
*Видео на паузе*
**насколько понял из условия - вывод должен быть максимальным значением, без необходимости сохранять последовательность знаков
а также массив нельзя сортировать и нужно работать лишь с исходным
создаём два счётчика
Проходим по массиву и сохраняем:
1) количество отрицательных чисел в первый счётчик, если оно чётное - ставим булевую переменную можноУмножитьДваждыНаМинус - true, else false
2) количество отрицательных чисел > -1 во второй счётчик, если оно чётное - ставим булевую переменную можноДелитьДваждыНаМинус - true, else false
- создаём 2 временные переменных типа double для числ массива [temporary1] [temporary2]
- создаём 2 переменных типа double для результата, куда будем записывать два варианта промежуточных действий и сравнивать их [result1] [result2]
проверяем что массив содержит больше 1го элмента и записываем первый элемент в [temporary1]
иначе сразу выводим его
Заходим в цикл (начинаем с первого индекса, не нулевого)
проходим заново по массиву, записывая i во временную переменные -> [temporary2]
заходим в проверки:
1) Если [temporary2] == 0
{
суммируем / вычитаем два временных элемента, без разницы результат сразу записываем в temporary1;
continue;
}
2) Если [temporary2] > 0
{
суммируем и перемножаем [temporary1] [temporary2] записывая в [result1] [result2];
сравниваем [result1] [result2] и записываем большее значение в [temporary1];
continue;
}
3) Если [temporary2] < 0 && > -1
если можноДелитьДваждыНаМинус == true
{
делим и вычитаем [temporary1] [temporary2] записывая в [result1] [result2];
сравниваем [result1] [result2] и записываем большее значение в [temporary1];
continue;
}
else
{
вычитаем [temporary1] [temporary2] результат сразу записываем в temporary1;
continue;
}
4) Если [temporary2] < 0
если можноУмножатьДваждыНаМинус == true
{
умножаем и вычитаем [temporary1] [temporary2] записывая в [result1] [result2];
сравниваем [result1] [result2] и записываем большее значение в [temporary1];
}
else
вычитаем [temporary1] [temporary2] результат сразу записываем в temporary1;
выходим из цикла
return temporary1;
не кидайтесь тапками если совсём всё плохо... я только начал учиться:)
upd: досмотрел видео.. выше всё плохо(
надо было не сравнивать в моменте 2 результата а плюсом вычислить минимальный и вести их оба к концу массива
Поставил на паузу. Backtracking?
В расчёт также надо брать и наиболее близкие к 0, а не только min/max . Как вам 1 /- 0.00000001
погромче бы)
Главное сделать умное табло на превьюшку
Не могу понять, почему с ифами будет дольше, чем второй вариант
Можно же изначально пройти по массиву, посмотреть сколько чисел отрицательных
Затем снова идем по массиву возможны следующие ситуации:
1) Число > 1: умножаем на него
2) число 0 < 1: делим на него
3) число = 1: прибавляем
4) число = 0: прибавляем
5) число -1 < 0: если отрицательных четное количество, то делим, иначе вычитаем
6) число = -1: вычитаем
7) число < -1: если количество отрицательных четное, то умножаем, иначе вычитаем
Неужели 7 ифов будут дольше?
Ты отбросишь варианты, которые могли бы дать больше в перспективе
в первом же примере после числа 1 идет число 2. По вашей логике стоит умножить, но как видим сложение дает лучший результат
@@freedomtv2295нет, у меня же отдельная проверка на 1 - 3 условие
Ифами надо учитывать что у нас в аккумуляторе лежит. Например, [0,2 и 1.5] - здесь лучше сложить, а не умножить.
И быстрее будет вычислить сумму и произведение и их сравнить, чем делать сравнения-вычисления чтобы понять, какую операцию выбрать. Ифы годятся чтобы совсем уж бесперспективные операции не выполнять, вроде деления в примере выше.
Почему в объяснение ничего не говорится про переполнение. Если тип double то вполне возможно. Если использовать нормальные языки программирования
Но последнее решение даёт максимум и не запоминает порядок мат. действий. Если входной массив пустой, то надо бы вернуть что-то типа undefined
Кажется правильным. Но как доказать, что между min и max нет числа, которое задавало бы новый min или max при +-*/ на любое число.
Понял. Если это умножение на любое число, то оно не рождает новый min или max(деление можно представить в виде умножения: 1 деленное на это число) . Сложение не рождает новый min или max (вычитание можно представить в виде сложения такого же числа с другим знаком)
Задача довольно простая (уровня Medium на Leetcode). Линейный проход по массиву. Не верю что это задача на 200к. Разве что на первых этапах собеседования. Вот если бы тут соблюдался приоритет операций - поверил бы, да, это сложнее гораздо.
Сразу видно кто после курсов по пайтону 😅
@@ukr9760 При чем тут пайтон? Я если что C++ разраб. Да и в данном случае язык принципиальной роли играет в решении данной задачи от слова совсем.
Блин, какие все вокруг умные! Мне страшно даже…(
@@benjaminBTNне смотри на других, смотри на себя
@@nurmashfg8858 легко сказать. Человек- существо социальное
Разве имеет смысл тащить дальше минимальное значение, если оно не отрицательное?
Если мы потом вычитать будем, то вроде как да
@@Drimondadsесли оно не отрицательное, то вычитать будет точно не нужно
Хорошее замечание! Думаю, что и правда не нужно
а почему рещение Идеальное O(n), если для каждой операции еще нужно минимум и максимум найти
Всегда ищем их среди постоянного числа вариантов, а значит постоянное время на поиск
Эти операции выполняются за константу
Да... А я минусы не учел(
5:47 тут ошибочка, получается 25 а не 36
так сказали, что математический приоритет не играет никакой роли
А разве сложность алгоритма не 4**(n-1)?
Константы не учитываются, потому что n может быть бесконечно большим в сравнении с единицей. Поэтому постоянные величины всегда можно опускать для сокращения записи
@@mihusle4187, да, ты прав, спасибо за объяснение)
@@mihusle4187 не всегда, иногда константы решают
O(4^n) эквивалентно по сложности O(4^(n-1))
200 баксов за то что ты пообщаешься с якобы гуглуром )) Нууу, без лоха и жизнь плоха
а ти циркач)
If if elif else проснитесь вы обосрались
Подумал про перебор, но попроизводительней вначале. Как начал обьяснять сразу сообразил о втором решение, что сам бы не допер сразу - так это брать в запас самое меньшее значение.
Можешь рассказывать что в {название компании} берут за зарплату {большие деньги} за решение задачи, и разбираешь рандом задачу с литкода
Отличный ролик, спасибо за труд. (далее будет мой вариант кода)
Писал код до предоставления Владом решения
Написал на python за ~20 минут, если не трудно подскажите как улучшить. Заранее спасибо
from random import randint as r
array = []
while len(array) < 30:
array.append(r(-500, 500)/r(-500, 500))
summ = array[0]
count_of_negative_values = 0
if count_of_negative_values % 2 == 0:
for i in array[1:]:
if i > 0:
summ += max((summ + i), (summ * i), (summ / i))
else:
summ += max(-(summ * i), -(summ / i))
else:
worse_negative_value = float('-0.' + '0' * 100 + '1')
for n in array:
if n < 0:
count_of_negative_values += 1
if max((-10 * n), (-10 / n)) < max((-10 * worse_negative_value), (-10 / worse_negative_value)):
worse_negative_value = n
for i in array[1:]:
if i > 0:
summ += max((summ + i), (summ * i), (summ / i))
elif i != worse_negative_value:
summ += max(-(summ * i), -(summ / i))
else:
summ -= worse_negative_value
print(summ)
Наивный нечукотский юноша, думающий, что организму с видео не наcpaть на комменты под ним 😂
@@TafferDP Я не прошу помощи у автора.
@@timurshamsiev336 Это неважно, он любые комментарии не читает