Задача с собеседования в Google на $200.000

Какие задачи надо решать собеседованиях в 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_worm]

Я бы просто насрал if, if else и с позором завершил собес

[pavlovn]

Влад, шикарное видео! Делай, пожалуйста, как можно больше разборов таких задач! будем лайкать каждое видео!!

[maks]

Очень интересно. Такие видео с разбором задач пожалуй лучший контент)

[remeyperson]

Поставил на паузу в начале видео. Решил эту задачу. Меня не учили лучшие преподаватели по алгоритмам из лучших бигтех компаний

[bebra]

Спасибо что делишься такой важной инфой для нас)

[someuser]

Спасибо, полезное и заряжающее видео, в прочем как обычно)❤️

[svetlanamazhaykina]

Спасибо за Ваш труд! Коммент в поддержку канала.

[overshotkuka]

Очень полезное видео. Хотелось бы больше видео такого формата

[ukludds]

Влад, вы просто супер мастер, это потрясающе, я восхищена

[_polyakov_a_d_]

Интересная задача на подумать, теперь хочется ее на Python сделать 👍

[kaluginpeter]

Интересная задача. Тоже поймал себя на greedy не учитывая constrains, но об этом нужно сразу уточнять. По факту наличия минуса в голову пришло хранить в массиве, но это не оптимально, так как дает пространственно линейную сложность. Остаётся выход использовать переменную для константной сложности.

[doudhhy]

спасибо, классное видео и интересная задача

[alex_illusion]

До просмотра решения. Возможно в алгоритме сделать условие поведения в зависимости от 4х цифр:
1) есть ли 0
2) есть ли числа от 0 до 1
и в зависимости от того какой индекс конкретного числа

[dv-key]

остановил на 8:07, пишу примерное свое решение. в целом еще до пояснений стало понятно, что могут быть отрицательные числа, 0 и от 0 до 1.
Дальнейшие размышления: нам надо для каждого следующего числа проверять в какой диапазон он попадает и в зависимости от этого применять знак.
Для начала забываю про то, что формируемый результат может быть отрицательным. Главное увеличивать число, положительный знак попробую выставить правильным количеством операций. По идее, если на отрицательные числа умножать/делить четное количество раз, то все будет хорошо) Тогда:
0 как правило лучше прибавлять/отнимать (одно и тоже),
на числа от 0 до 1 (не включительно) и от 0 до -1 делить,
1 прибавлять, -1 отнимать (либо использовать для корректировки знака).
на те, что >1 и <-1 умножать
Хорошо бы далее оценить количество отрицательных чисел в массиве и сколько раз мы их собрались использовать в операциях умножения/деления. Если они используются четное количество раз, то мы получим максимальный результат по вышеозвученнм правилам. Если нечетное, то нам надо одно из отрицательных чисел (ближайшее к -1) использовать не в операции умножения/деления, а в операции сложения/вычитания.
Примерно так, для больше точности надо реализовывать, а мне уже лень, еще на прошлом видео с задачкой собирался закончить

[TheMurodilla]

1. Хранить последное число в переменную last_num
2. Проделать все операции с последним и текущим числом
3. Получить максимальное число из полученных результатов, и хранить в переменную max_num
4. Установить max_num в last_num

P.S: Не учел отрицательные числа)

[samFATEWOLF]

Писал код на питоне, пока не смотрел продолжение, но написал довольно быстро, не верится что задача такая простая… (это не Хейт, наоборот, уважение автору за разминку для мозгов!!🤝)

Логика следующая:
Брать каждую пару чисел в массиве (за счет цикла for) и находить максимальный результат действий с ними (для этого написал функцию, только надо учесть что числа могут быть 0.0, в функции результаты всех действий беру в массив и возвращаю максимальное число), а после результат подставляю на место второго числа в паре, чтобы дальше идти по циклу.

После окончания цикла ответом будет последнее число в массиве, оно же - максимальное

АПД: очень круто, я понял в хитрость задачи, я в гугл не прошел 😂😂

[artempogorelov]

Поставил на паузу, подумал несколько минут.
Кажется, это задача на дерево. Каждый узел имеет 4 ветви(+, -, /, *). Обходим дерево, отсекая каждый раз 2 из 4 ветвей. Нас интересует максимум положительный и минимум отрицательный (потому что на следующих этапах можно умножить или разделить на другое отрицательное число). Довольно интересная, но несложная задача. Вначале она кажется сложнее, чем есть. Я думал над матрицей решений, в зависимости от текущего значения и следующего числа (от минус бесконечности до -1, от -1 до нуля, нуль, от нуля до 1, от единицы до плюс бесконечности), но этот подход не будет давать оптимального решения, если нужно дважды умножить на отрицательное число, чтобы получить максимум. Поэтому я решил представить себе полный перебор (ребята, всегда начинайте с тупого и неэффективного решения, оно лучше, чем ничего). А это просто dfs, и его можно соптимизировать, как я написал выше.
О, а ведь можно и дальше пойти в оптимизации, если делать обход в ширину, и хранить отрицательный минимум и положительный максимум для всего уровня, а не только для текущего узла, тогда углубление будет только в 2 ветви.

[gellolenok]

А я подумал, что мы можем брать любые соседние элементы массива, применять к ним операцию, а затем записывать новый элемент вместо этих двух. То есть не обязательно идти по порядку: на любом шаге берём любые a[i] и a[i+-1] (рядом стоящие элементы), получаем new_elem посредством применения определённой операции к a[i] и a[i+-1], кладём его на i-ое место, а[i] и a[i+-1] удаляем. Такая задача была бы сильно сложнее, хотя возможно, это и подразумевалось.

[Blendershick]

Очень интересно спасибо. Разбор очень крутой все понятно)

[panfilovandrey]

Ну да, вариант у тебя более наглядный с точки зрения кода, его будет проще понять тому, кто будет потом разбираться. Согласен.