Задача с собеседования в Google на $200.000
ฝัง
- เผยแพร่เมื่อ 15 มิ.ย. 2024
- Интенсив "Разбор алгоритмов"по ссылке: www.faang.school/analysis-of-...
Какие задачи надо решать собеседованиях в 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/?...
Java Magics. Бесплатный курс для начинающих: www.faang.school/java-magics?...
Социальные сети:
Instagram: / faang.school
LinkedIn: / vlad-mishustin
ВК: faang.school
ТГ-канал "Road to FAANG": t.me/fakng_eng
ДИСКЛЕЙМЕР
Любая информация, высказанная в данном видео является моим личным мнением и никак не относится и не отражает позиции моего работодателя или любых связанных со мной организаций.
Любой код, документация, логи или диаграммы, показанные в видео, являются моими личными макетами, написанными/созданными в мое свободное время на своей собственной машине, конкретно для демонстрации в роликах, никак не относясь и не используя интеллектуальную собственность моего работодателя или любых связанных со мной организаций.
![ถ้าพี่วุ้นท้อง แป้งจะท้องไปด้วยกัน !!!! [ดูคลิปเต็มหน้าช่อง] #Short | PANG ORNHIRA](http://i.ytimg.com/vi/FeyEnVMwitA/mqdefault.jpg)
Я бы просто насрал if, if else и с позором завершил собес
Очень интересно. Такие видео с разбором задач пожалуй лучший контент)
Спасибо что делишься такой важной инфой для нас)
Влад, шикарное видео! Делай, пожалуйста, как можно больше разборов таких задач! будем лайкать каждое видео!!
Спасибо,полезное и заряжающее видео,в прочем как обычно)❤️
Топ контент! Ушел решать задачу))
Очень полезное видео. Хотелось бы больше видео такого формата
Влад, вы просто супер мастер, это потрясающе, я восхищена
Спасибо за Ваш труд! Коммент в поддержку канала.
Крутой контент! Продолжай!💪
Супер ролик, спасибо
спасибо, классное видео и интересная задача
Владос лучший ! Если не сложно , ответь на вопрос .
Развиваюсь в сфере аналитики и мне интересно знать , как в FAANG обстоят дела с данным направлением , либо может поделишься где можно узнать информацию насчет аналитических направлений в биг тех ?
Интересная задача на подумать, теперь хочется ее на Python сделать 👍
До просмотра решения. Возможно в алгоритме сделать условие поведения в зависимости от 4х цифр:
1) есть ли 0
2) есть ли числа от 0 до 1
и в зависимости от того какой индекс конкретного числа
Ахуенный видос, продолжай в том же духе 🔥
Топчик!
Интересная задача. Тоже поймал себя на greedy не учитывая constrains, но об этом нужно сразу уточнять. По факту наличия минуса в голову пришло хранить в массиве, но это не оптимально, так как дает пространственно линейную сложность. Остаётся выход использовать переменную для константной сложности.
Ну да, вариант у тебя более наглядный с точки зрения кода, его будет проще понять тому, кто будет потом разбираться. Согласен.
Поставил на паузу в начале видео. Решил эту задачу. Меня не учили лучшие преподаватели по алгоритмам из лучших бигтех компаний
то есть можно просто прорешать наиболее частые задачи или даже заучить и попасть на высокую позицию?
Очень интересно спасибо. Разбор очень крутой все понятно)
больше таких роликов)
5:50 - так мы ищем максимум как результат всех операций, или мы должны вернуть такую последовательность операций, которые дадут максимальный результат?
Если второе, то у нас сложность по памяти O(N)
Как решить задачу, если проходиться не последовательно? У меня в голове есть решение и вроде как o(n*n) . Это правильно?
остановил на 8:07, пишу примерное свое решение. в целом еще до пояснений стало понятно, что могут быть отрицательные числа, 0 и от 0 до 1.
Дальнейшие размышления: нам надо для каждого следующего числа проверять в какой диапазон он попадает и в зависимости от этого применять знак.
Для начала забываю про то, что формируемый результат может быть отрицательным. Главное увеличивать число, положительный знак попробую выставить правильным количеством операций. По идее, если на отрицательные числа умножать/делить четное количество раз, то все будет хорошо) Тогда:
0 как правило лучше прибавлять/отнимать (одно и тоже),
на числа от 0 до 1 (не включительно) и от 0 до -1 делить,
1 прибавлять, -1 отнимать (либо использовать для корректировки знака).
на те, что >1 и
Не могу зайти в телегу, при отправке формы сайт кидает ошибку
Для Макс мин не нужно сравнение?, можно использовать готовое?
Влад с интенсива будут видео?
Писал код на питоне, пока не смотрел продолжение, но написал довольно быстро, не верится что задача такая простая… (это не Хейт, наоборот, уважение автору за разминку для мозгов!!🤝)
Логика следующая:
Брать каждую пару чисел в массиве (за счет цикла for) и находить максимальный результат действий с ними (для этого написал функцию, только надо учесть что числа могут быть 0.0, в функции результаты всех действий беру в массив и возвращаю максимальное число), а после результат подставляю на место второго числа в паре, чтобы дальше идти по циклу.
После окончания цикла ответом будет последнее число в массиве, оно же - максимальное
АПД: очень круто, я понял в хитрость задачи, я в гугл не прошел 😂😂
Точно так же решил 😅
спасибо
Поставил на паузу, подумал несколько минут.
Кажется, это задача на дерево. Каждый узел имеет 4 ветви(+, -, /, *). Обходим дерево, отсекая каждый раз 2 из 4 ветвей. Нас интересует максимум положительный и минимум отрицательный (потому что на следующих этапах можно умножить или разделить на другое отрицательное число). Довольно интересная, но несложная задача. Вначале она кажется сложнее, чем есть. Я думал над матрицей решений, в зависимости от текущего значения и следующего числа (от минус бесконечности до -1, от -1 до нуля, нуль, от нуля до 1, от единицы до плюс бесконечности), но этот подход не будет давать оптимального решения, если нужно дважды умножить на отрицательное число, чтобы получить максимум. Поэтому я решил представить себе полный перебор (ребята, всегда начинайте с тупого и неэффективного решения, оно лучше, чем ничего). А это просто dfs, и его можно соптимизировать, как я написал выше.
О, а ведь можно и дальше пойти в оптимизации, если делать обход в ширину, и хранить отрицательный минимум и положительный максимум для всего уровня, а не только для текущего узла, тогда углубление будет только в 2 ветви.
Досмотрел, убедился, что я молодец😄
Нюанс в том, что собеседование в гугл - это, во-первых, стресс, во-вторых, лотерея. Я свои собесы не то чтобы завалил, задачи были даже проще, чем я ожидал(кроме одной), но не дотянул то тут, то там. Времени действительно дают очень мало, всего час, из него минус минут 10-15 на разговор вначале и в конце, и при этом надо было решить 2 задачи каждый раз.
Но все вполне реально, хоть и непросто. пару месяцев на литкоде, пара книжек, несколько лет опыта в индустрии, немного везения, и вот она, «работа мечты».
Кстати, 200к это в США же, в Европе разве столько base дают, или это TC?
Автору спасибо, зрителям удачи😉
можно поробовать накапливать результат выражения и применяя каждую операцию проверять стало ли накопленное число больше, если меньше, то другая операция и так до конца массива
Как насчет этого варианта решения?
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? Или по условии задачи последовательность чисел в массиве нельзя менять?
Привет! Спасибо за видео. У меня вопрос почему при сложении числа "-3" с числом "1" у тебя получается "4"?
Потому что он взял вычитание сначала 1-(-3), а минус на минус дает +, и как следствие 1+3
Дайте ссылку на литкод с этой задачей, кто нибудь
А я подумал, что мы можем брать любые соседние элементы массива, применять к ним операцию, а затем записывать новый элемент вместо этих двух. То есть не обязательно идти по порядку: на любом шаге берём любые a[i] и a[i+-1] (рядом стоящие элементы), получаем new_elem посредством применения определённой операции к a[i] и a[i+-1], кладём его на i-ое место, а[i] и a[i+-1] удаляем. Такая задача была бы сильно сложнее, хотя возможно, это и подразумевалось.
Есть вопрос: если проставить действия сразу?: то тогда даже с первым набором цифр, результат другой если считать по правилам математики: типа умножение первое делать... если считать отдельно каждый раз пошагово так сказать может стоить прописать условия для операций: А) если число 0, то /; (но тут надо добавить неравенство - если оба числа меньше ед... типа, чтобы деление было больше сложения и еще условие для отриц. чисел... тоже проверить)б) если число 1, то +; в) если одно число (+) положит, а другое (-) отриц., то * или -; г) если число = 0, то + (чтобы не занулять результат) ; д) если оба положительные, то *; и е) если оба числа отрицательные, то *. Тогда вообще легко: действия отсеиваются сразу...
Первое что в голову пришло это пройтись циклом и вложенными тернарнеми операторами соблюсти условия на ноль и отрицательные числа 🤔 Посмотрим теперь какое решение😅
Мда, условие нужны от i = -1 то +, еще и знаки учесть нужно, потом n += i или n *= i.
По производительности конечно нужно проверить.
После просмотра видео пришла еще мысль запустить цикл, переменная n равна первому числу. Потом берем в каждой итерации цикла четыре переменные полученые с разными знаками и присваиваем максимальное полученное значение n = Max(x1, Max(x2, Max(x3, x4))). Так пробегаем по массиву.
Проход по массиву за n
Дальше конструкции иф , елсе иф, елсе с проверками: 1 число отрицательное - знак минус, =1 или =0 - знак плюс, 0
Не правильно, если что
[4.0, -2.0, -5.0] выдаст 11,
а ожидалось 40.0
в такой ситуации все тоже самое, только сначала считаем количество отрицательных чисел, если четное то при отрицательном числе умножение, если нечетное то перед отрицательным числом умножение, но перед последним отрицательным числом минус. Проходя по массиву можно просто считать количество отрицательный@@persssotami
@@persssotami Просто в голос хохочу с таких организмов, которые указывают кому-либо на ошибки и при этом демонстрируют собственную безграмотность... вдвойне смешнее, когда такие типы говорят о том, что что-то *неправильно* и при этом даже не знают как *правильно* это слово пишется 😂😂😂
1. Хранить последное число в переменную last_num
2. Проделать все операции с последним и текущим числом
3. Получить максимальное число из полученных результатов, и хранить в переменную max_num
4. Установить max_num в last_num
P.S: Не учел отрицательные числа)
Какой номер задачи на литкод?
Ну это простая задача, линейный алгоритм с одним проходом. Нам нужно сохранять два массива операций, некое ветвление, когда попадается отрицательное число, а наш сумматор положительный, ибо, если он отрицательный, вычисляем, что будет больше, вычесть минус (для сумматора близкого к нулю) или умножить но новое отрицательное и получить большее положительное. Как только оно попалось, в первом массиве храним "безопасный вариант" с вычитанием, а параллельно сохраняем вариант с умножением и переходом в минус для сумматора. Как только нам попалось еще одно отрицательное, его домножаем и делаем второй вариант решения основным, а если до конца массива минусов больше не попалось, то исходный безопасный остается. Для чисел меньше 1 по модулю делаем деление, ну и для отрицательных так, как выше было описано, только с заменой умножения на деление. Если попадается ноль, то просто ставим плюс. Теперь посмотрим видео дальше, что же ты предлагаешь :) Кстати, звук очень тихий, либо надо прямо в микрофон говорить, либо усиление громкости сделать...
А обязательно ли брать всн числа в массиве последовательно. Во втором примере видно, что если нарушить последовательность, можно получить больший результат
Нельзя. В условии задачи операторы можно вставлять только между двумя соседними элементами.
Автор сказал, не меняя последовательность чисел.
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 результата а плюсом вычислить минимальный и вести их оба к концу массива
Почему в объяснение ничего не говорится про переполнение. Если тип double то вполне возможно. Если использовать нормальные языки программирования
Но последнее решение даёт максимум и не запоминает порядок мат. действий. Если входной массив пустой, то надо бы вернуть что-то типа undefined
В расчёт также надо брать и наиболее близкие к 0, а не только min/max . Как вам 1 /- 0.00000001
Кажется правильным. Но как доказать, что между min и max нет числа, которое задавало бы новый min или max при +-*/ на любое число.
Понял. Если это умножение на любое число, то оно не рождает новый min или max(деление можно представить в виде умножения: 1 деленное на это число) . Сложение не рождает новый min или max (вычитание можно представить в виде сложения такого же числа с другим знаком)
Что-то слишком простая задача, решается сходу. Тянет на изи на литкоде, может медиум-
Если за такое 200к$ платят, то я что-то делаю не так
Поставил на паузу. Backtracking?
Разве имеет смысл тащить дальше минимальное значение, если оно не отрицательное?
Если мы потом вычитать будем, то вроде как да
@@Drimondadsесли оно не отрицательное, то вычитать будет точно не нужно
Хорошее замечание! Думаю, что и правда не нужно
погромче бы)
а почему рещение Идеальное O(n), если для каждой операции еще нужно минимум и максимум найти
Всегда ищем их среди постоянного числа вариантов, а значит постоянное время на поиск
Эти операции выполняются за константу
а что там на мониторе одна и та же шляпа бегает? )))) типо матрица перезагрузка? ))))
Решение последнего примера сделано неверно. В первых вычислениях получилось число -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
Не могу понять, почему с ифами будет дольше, чем второй вариант
Можно же изначально пройти по массиву, посмотреть сколько чисел отрицательных
Затем снова идем по массиву возможны следующие ситуации:
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] - здесь лучше сложить, а не умножить.
И быстрее будет вычислить сумму и произведение и их сравнить, чем делать сравнения-вычисления чтобы понять, какую операцию выбрать. Ифы годятся чтобы совсем уж бесперспективные операции не выполнять, вроде деления в примере выше.
Довольно плохое решение я считаю, но
1)отсортировать массив
2)и проходясь по циклу ставим на все возможные варианты условия(например если меньше единицы и больше -1 прибавляем или отнимаем, а если меньше -1 умножаем или ой чет запутался )
Знаю что очень плохое решение, но это то что пришло в голову в первую очередь
Смотрю дальше!
Если отсортировать массив, то нарушится порядок действий + nlogn уже неоптимально
так там нельзя сортировать
Задача довольно простая (уровня Medium на Leetcode). Линейный проход по массиву. Не верю что это задача на 200к. Разве что на первых этапах собеседования. Вот если бы тут соблюдался приоритет операций - поверил бы, да, это сложнее гораздо.
Сразу видно кто после курсов по пайтону 😅
@@ukr9760 При чем тут пайтон? Я если что C++ разраб. Да и в данном случае язык принципиальной роли играет в решении данной задачи от слова совсем.
Блин, какие все вокруг умные! Мне страшно даже…(
@@benjaminBTNне смотри на других, смотри на себя
@@nurmashfg8858 легко сказать. Человек- существо социальное
Почему именно среди программистов столько много каррртавых?
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 Это неважно, он любые комментарии не читает