Алгоритмическое собеседование в Android / Сергей Глотов (Авито)

Понравилось видео и хочешь узнать что-то еще про Android или алгоритмы? Забирай весь плейлист на is.gd/kChYnl или купи билет на следующий сезон конференции is.gd/auKynm
Подпишись на канал - каждую неделю мы выкладываем новые видео про то, как устроена работа и жизнь в IT!

[@wazo4ka]

За 4 года принципиально ничего не изменилось, всё также есть алгоритмический этап, надо кодить в блокноте, а чел который тебя собеседует, запускает это где-то у себя и говорит в какой части кода у тебя ошибка вроде опечатки в переменной и тд. И если ты привык пользоваться IDE, то шансы пройти до этапов проверки реальных знаний языка и систем-дизайна стремятся к нулю. Есть вопросы к людям придумавшим такой флоу отбора, пустой просёр времени что для соебседующих, что для собеседуемого.

[@kirillsushilnikov9614]

"Для чего мне это нужно?" "-Для того, чтобы если ты не Android-разработчик, то знал, сможешь ли ты справиться с таким объемом данных". Вот и я думаю, зачем это всё клиентскому приложению?

[@torburgmax]

а как фоточки на устройстве обрабатывать на лету, например?

[@konstantinalekseev5789]

Очень странное решение первой задачи. Просили найти максимальную сумму, по факту нашли сумму максимальных цен

[@user-fi9rw4vx2b]

Решение корректное. Умножение опустили т.к. по условию каждый день производится 1 штука товара, нет смысла умножать на 1

[@artemkhateev3650]

Полезно для собесов в иностранные компании. Лайк.

[@Das.Kleine.Krokodil]

В авито есть такие собесы, чисто алгоритмические?

[@Das.Kleine.Krokodil]

4:05 просто нужно было микрофон взять там видимо на камеру пишется

[@Das.Kleine.Krokodil]

Что то не понял, а где в первой задаче умножения колва на цену?

[@m.e.r.k3487]

В данном решении не требуется умножение количества на цену, так как мы используем максимальное найденное на данный момент значение цены для добавление к результату на каждой итерации. Таким образом если текущее значение цены (обратите внимание что итерация происходит в обратном порядке - с конца в начало) меньше максимального значения цены, то мы добавляем в результат максимальное значение цены (найденное на данный момент). В противном случае мы добавляем текущее значение и обновляем максимальное значение. Т.Е. в каждой итерации мы продаем 1 товар по максимальной цене, найденной на данный момент. Надеюсь понятно объяснил :)

[@aleksandr_t]

Вторую задачу разве не так решаем? 1) сортируем массив 2) используем метод динамического плавающего окна, начинаем процессинг с конца массива 2.1) сравниваем элемент по индексу R с суммой элементов по индексу L, L - 1. 2.2) если сумма меньше чем правый элемент, то двигаем окно влево и вычитаем текущую сумму 3.3) в конце запоминаем максимум, перед этим обновив текущую сумму Выглядит что такое решение заходит, так как у нас сохраняется свойство правильности подпоследовательности, так как присутствует монотонность. Решение получается в общей сложности O(NlogN).

[@papa_kottt]

Блин, я не понимаю как решить первую задачу даже на пальцах (без программирования, просто словами так сказать) х) Почему из массива 1 3 1 2 получается 10?

[@papa_kottt]

@@golanger Спасибо, прекрасный человек!

[@romildathetortoise]

@@golanger у нас один проход - O(n). Мы смотрим понедельник - 1 руб. Это дорого или дешево? Мы еще ничего не знаем про вторник и про три рубля. Может в среду цена будет 20 руб. Тогда мы могли бы продать 3 * 20 + 1 * 2 = 62 руб. Как я понял, это из жадных алгоритмов. В голове что-то не укладывается. Машина времени нужна.

[@romildathetortoise]

То есть, действуя жадно, мы смотрим, если i-й элемент

[@romildathetortoise]

let arr = [1, 3, 1, 2] var sum = 0 var rest = 0 for i in 0.. arr[i + 1] { // продаем, копим заново sum += rest * arr[i] rest = 0 } // иначе копим, в последний день отдаем все, что осталось } print("sum:", sum)

[@user-fi9rw4vx2b]

Первая задача норм. Идею решения парень описал верно, с реализацией что-то затупил

[@thexaerom]

Не быть мне "андроид разработчиком", буду всю жизнь кнопочки передвигать с текстовыми полями :(

[@user-sl9og4bp2l]

Как всегда тупое условие задачи, как ты продашь товар в прошедшие дни?

[@user-fi9rw4vx2b]

Нормальное условие, это может быть ретроспективный анализ

[@ynblpb1985]

Во второй задаче можно было решить со сложностью n, а не n*ln(n).

[@gijduvon6379]

А как?

[@ynblpb1985]

@@gijduvon6379 я ошибся. Неправильно понял 3словие задачи.

[@user-qp9tg5pn5e]

@@gijduvon6379 я думаю так можно сперва сортинг массива потом реверс и сумма 0 и 1 индекса

[@user-kg6hy1sz4y]

Можно, если как то передвигать 3 индекса за одну итерацию. То есть максимум и два минимума. И так же суммировать сам массив. С максимумом и суммой не проблема. Но итерировать 2 минимума будет как то сложнее.

[@HelloWorld-sy4yc]

Ну чел много чего не понимает

[@torburgmax]

вряд ли он хорошо шарит за то, как вырабатывается норадреналин. но и вы не понимаете, как писать осмысленные комментарии. все мы не без греха.