Савватеев решает задачи с собеседований. Матрица. Авто на шоссе. / ЛОГИКА САВВАТЕЕВА / ДЕПЛОЙ ПОЛЬЗА

Всем Деплой-привет! Савватеев в здании! Приятного деплоя и делитесь своими решениями в комментариях!
--------
Поддержать канал: boosty.to/in.office
Поддержать канал Алексея: boosty.to/savvateev
Наш телеграм: t.me/dev_yttg
--------
Мы в ВК: deployprod
Мы в Dzen: dzen.ru/deploy
Мы на RuTube: rutube.ru/channel/30396580/
Мы на Яндекс.Музыке: music.yandex.ru/album/2498068...
Мы на Apple Podcasts: podcasts.apple.com/ru/podcast...
Ваня на Твиче: / stressoid

[@user-yd3gw2xy3f]

Канал про it, а они даже не могут экран планшета вывести😢

[@akame6747]

И звук гуляет по уровням (((

[@absfree123]

Это бета-версия

[@kurc_wl]

Согласен, это огромное упущение

[@tapoolkeer]

и ноут зарядить забыли

[@user-xw3lf2vd6d]

Вы видимо сами не it) в it во первых решение задачи должно решать задачу но не обязано превосходить её) то есть если не было цели показать каракули савватеева то зачем? А во вторых не каждый it умеет настраивать цифровую технику)

[@Alex-um2lh]

Поржал, когда сверху появилась табличка с ответом на вторую задачу "Никто не ожидает, что вы можете в уме извлекать кубические корни", хотя Саватеев только что это и сделал) Ну математик, понятно, просто смешно получилось)

[@user-hq9xf9fh1v]

Эффективный алгоритм поиска в отсортированной матрице очень простой: Поиск начинаем с правого верхнего угла матрицы. Если искомое число меньше текущего, то идем влево, а если больше - то вниз. И так далее, пока не встретим искомое число. Временная сложность алгоритма O(n+m).

[@anton3919]

Он менее эффективен, чем тот вариант на 10 страниц. Но он быстрее построчного бинарного поиска и, при этом, проще. Очень хороший баланс простоты и эффективности

[@alexd8803]

Неплохо было бы видеть рассуждения собеседуемого с экрана его планшета где-нибудь в правом или левом углу экрана)

[@aebezbuldyrabyz]

Ага

[@sozinovss]

Сразу лайк! Спасибо!

[@user-uu6jp8lu7l]

Спасибо за видео!

[@mir0max]

Скажите ему, что продолжительность свечения экрана можно увеличить.

[@robertmarzoev8409]

Это не его планшет, и это задача организаторов съёмки - подготовить условия и аппаратуру. А так он наверно и микрофон может сам настроить, фильтр с собой принести, лампы для правильного освещения тоже с собой...

[@user-do4gc6ys5y]

Первая задача - это классическая задача (баян), решается за O(n + m). Из правого верхнего угла идём либо влево, либо вниз, и сравниваем с тем, что нужно найти.

[@sergeygamer1455]

Нет никакого О(n + m). Всегда это записывается в виде O(n), либо O(n^2)

[@kirillpetrenko55]

У тебя в общем случае разное количество строк и столбцов и эти величины не зависят друг от друга

[@sergeygamer1455]

@@kirillpetrenko55 почитай про нотацию О-большое и больше не пиши такую ерунду. Там нет ни сложений, ни умножений. Есть n, 1, степени, логарифмы, факториалы

[@kirillpetrenko55]

@@sergeygamer1455 хорошо))) Какова сложность алгоритма поэлементного обхода двумерного массива у которого n строк и m столбцов?

[@kirillpetrenko55]

@@sergeygamer1455 какова сложность алгоритма, который суммирует все элементы матрицы размера n*m, находящиеся на ее "периметре" (1 и n строка и 1 и m столбец)? Какова сложность алгоритма, который пишет n раз "Hello", а потом m раз "World"?

[@alariy9414]

Никто не умеет извлекать корень кубических в уме а Савватеев умеет

[@IlyaMasalsky]

Мне кажется это не очень сложно с небольшими числами

[@user-we6xp8pn4w]

Матрица отсортирована по принципу относительное топографии. Можно построить изометрические кривые. По этому принципу строятся карты относительной высоты, давления, температуры. Частая тема у метеорологов.

[@seensLC]

На самом деле первый вопрос немного некорректный и вводит его в ступор, изначально это типичная задача "напишите алгоритм поиска значений в таблице за минимальное количество действий" и тогда уже начнется поиск оптимального алгоритма

[@A____V]

Ничерта не понятно, но очень интересно

[@tapoolkeer]

понятно, что на такое собеседование лучше не ходить

[@andrew-new]

Алексей, первая задача решается за O(n+m), что лучше чем логарифм, надо было прочитать решение :)

[@Mopszz]

Бинарным поиском можно logN+LogM.

[@xxxxPomaHxxxx]

нет не лучше, логарифм быстрее чем линия, есть решение O(logn+logm)

[@andrew-new]

@@xxxxPomaHxxxx решение O(log n + log m) не видел, я имел ввиду что O(n + m) быстрее чем O(n log m)

[@nicholasspezza9449]

лол, дурачок, логарифм быстрее чем линейное время. По твоей ущербной логике если O(n log m) - логарифмическая сложность, то тогда О(n*m) - получается линейная)))

[@andrew-new]

@@nicholasspezza9449 хорошо, посчитай что больше миллион плюс миллион или миллион умножить на логарифм миллиона

[@_Smai1e_]

Насчёт первой задачи. Я бы не стал применять бинарный поиск к каждой строке, можно всего один раз. Матрица отсортирована по строкам и столбцам. Перегоняем её в по диагоналям (нижний левый/верхний правый) в массив. На примере нашей матрицы будет [15, 20, 20, 30, 35, 40, ...]. И уже к этому массиву применяем бинарный поиск И в итоге сложность вместо N×log(N) будет log(N×N), что значительно лучше. К примеру, если N=1000, то в первом случае будет ≈997, а во втором ≈20

[@vadimrumyantsev8498]

У вас 80 будет стоять после 85 и т.д.

[@user-or6pu7ub3b]

САВВА - КРАСССССССССССССАВЧИК!

[@user-su5gn4dd4u]

Не могу без запятой.. Много законов физики..

[@nicholasspezza9449]

Первая задача легкотня, начинаем с правого верхнего угла и ходим только вниз и влево.

[@user-tg4ll9ws3i]

Решение от программиста :). У нас матрица. Делим матрицу на 4 равные (по возможности конечно). четвертинки. В каждой четвертинке мы проверяем может ли быть нужное нам число. Если левое-верхнее число больше нужного или наоборот нижнее-правое меньше нужно то эта четвертинка нам не подходит и мы её выкидываем. В худшем случае останется 2 четвертинки из 4х (диагональные) которые могут содержать число. На эти подходящие четвертинки повторяем алгоритм, пока матрица не выродится в единственное число. Понятно что эффективность алгоритма логарифмическая.

[@Waterlaz]

Не будет логарифмическая. Похоже, что линейная от n для матрицы (n*n).

[@f.linezkij]

Беда в том, что если из четырёх всегда остаются две четвертинки-кандидата, то их количество растёт экспоненциально по основанию 2. Показатель степени - логарифм n по основанию 2. В итоге сложность линейная.

[@MrAleksey12345]

Интересно... Мне на экзамене в вузе попались матрицы... Потом это убрали из заданий на вступительных экзаменах. Неужели опять ввели?

[@russ1anasanov1ch49]

Савватееву выдали 5-копеечный стилус в отместку за "Apple Pencil"?Надо было ему гвоздь выдать и фанерку.

[@iglukhov]

Надо было экран писать с планшета.

[@user-hk5vf6nx9c]

Тут все пишут, что нужно вывести происходящее на планшете на экран. Легче всего это сделать, начав видеосозвон в чем-нибудь типа зума или гуглтока, поставить запись, расшарить экран в запись, а потом при монтаже просто прикрутить по таймингу. Проще, чем читать комменты про «выж прогеры, чеж вы не можете».

[@user-xw3lf2vd6d]

Блин. А какое решение то у матриц? инет показывает что у бинарного поиска у отсортированных матриц сложность n*log2(m). Почему не log2(n)*log2(m)? Почему то объяснения именно на матрицах не нашел. Только на строках. Хоть бы ссылку дали или проговорили.

[@vadimrumyantsev8498]

Потому что бинарный поиск работает только по одному измерению. Но другое дело, что в данном случае матрицу, наверное, можно определённой перестановкой элементов свести к вектору и получить log(m*n).

[@Dimonshirson]

Таблица: Начинаем поиск с правой верхней ячейки вниз, как только значение больше искомого, начинаем поиск по строке влево до совпадения или меньше - если совпадения нет.

[@user-wo4pr7vj2b]

Можно подробнее? Нужно найти 55. Начинаем справа сверху - 85, оно больше искомого, но слева нужно значения нет

[@alexey1930]

@@user-wo4pr7vj2b начинаем справа сверху и если искомое число больше, то идете вниз по матрице, если меньше то влево. Например ищем 55. попали на 85. 85 больше чем 55? Да. Значит смотреть ниже 85 нет смысла, так как они отсортированы и ниже будут числа больше 85. Значит двигаемся влево на число 40, снова сравниваем 55 и 40. 55 больше, смотреть левее нет смысла, ибо они отсортированы и слева числа меньше 40, значит двигаемся на единичку вниз на число 80. Снова 55 больше 80, нет. Значит идем влево на число 35. Сравниваем 55 и 35, 55 больше значит идем вниз. И нашли.

[@user-wo4pr7vj2b]

@@alexey1930 благодарю, не так понял сначала!

[@user-yc4dn8ix7n]

с экрана нельзя было видео записать и показать в уголке?

[@user-mp8su1yf5j]

Мысль 2. Ключевое замечание - матрица отсортировона. значит она уже по возрастанию. Получается, любой перебор с шагом 1 даст нужный результат. Более того, есть странная мысль что это самый быстрый путь

[@_Smai1e_]

неа)

[@1van1vy]

Что? 10 страниц? Есть же тривиальное решение первой задачи за log(n)+log(m).. Примерно опишу метод. Заметим, что мы можем найти столбец, в котором наше число за log(n). Просто бинарный поиск по самой нижней строке. Это происходит так как любое нижнее число больше чем ВСЕ числа левого прямоугольника, который отсекается столбцом, где стоит наше нижнее число. На примере из видео видно, что 80 больше чем числа 15. 20. 20. 35. 30. 55. 40. Или 100 больше чем 15. 20. 40. 20. 35. 80. 30. 55. 95. 40. 80. Таким образом мы находим столбец, в котором наше число. Далее в этом столбце за log(m) находим его тем же бинарным поиском (если оно есть) Возможны какие-то тонкости, но идея рабочая

[@pandalove6795]

поставь вместо 55 число 54, а вместо например 85 число 55. И ищи 55. Твой алгоритм тупо не найдет число. Мы не можем быть уверены, что нашли сразу столбец с числом. (ну может я не правильно понял твою идею, но вряд ли)

[@kirillpetrenko55]

Нет не находим. В первом столбце 55 быть точно не может, а во всех остальных судя только по нижниму ряду может

[@user-db4ib8tl1i]

Нихера😂😂😂

[@papalyosha]

Первую задачу нельзя решить за логарифм. Представьте у вас квадратная матрица, и вам даже сказали, что число находится на диаганали, которая идет с нижне-левого угла в верхне-правый. На этой диаганали числа могут быть в любом порядке, поэтому отсортированасть матрицы вам не поможет. Так что меньше, чем за n не получится решить даже с дополнительным ограничением.

[@vadimrumyantsev8498]

Это означает только то, что мы выбрали неэффективный способ обхода.

[@vadimrumyantsev8498]

А представьте, что у вас не квадратная матрица. Например, 1000000x1. Это уже контрпример к вашему утверждению.

[@papalyosha]

@@vadimrumyantsev8498 Нет, не контрпример. Мой аргумент заключается в том, что меньше, чем за min(m,n) нельзя. А логарифм в общем случае меньше, чем min(m,n), поэтому за логарифм не получится. Для матрицы 1000000x1, min(m,n)=1. Поэтому это не противоречит моему утверждению. Хоть для такой матрицы задача решается за одно обращение, не существует алгоритма, который бы решал задачу за логарифм для *любой* матрицы.

[@papalyosha]

@@vadimrumyantsev8498 Нет, это верно для любого способа. Не существует алгоритма, который ищет в неотсортированном массиве нужный элемент гарантировано за логарифм сравнений. Потому что, пока мы не сравним его со всеми, мы не можем гарантировать, что найденный элемент средний. Значит нам нужно прочитать n элементов вне зависимости от способа обхода. Поэтому в квадратной матрице, мы не найдем элемент, даже если мы точно знаем, что он на диагонали. Уж тем более мы не можем найти элемент, если мы не знаем, что он на диагонали.

[@vadimrumyantsev8498]

@@papalyosha савватеев предложил решение за логарифм для любой матрицы. Выбрав число в середине матрицы и сравнив с ним искомое, мы выкидываем либо верхний левый, либо нижний правый квадрат. Далее повторяем эту процедуру рекурсивно для Г-образных оставшихся полей, которые разбиваются на прямоугольник и квадрат. В среднем за шаг мы будем откидывать не менее 1/8 клеток, что даёт логарифм по основанию 8/7. То, что вторая диагональ матрицы не упорядочена, ничего не значит.

[@user-su5gn4dd4u]

На диоганали 2корень из 2

[@DanteAlighery]

Упрощённая 19 задача из ЕГЭ)) Слева-направо или сверху-вниз сравниваем числа с искомым, найдя большее искомого отступаем на предыдущую строчку(столбец) и идём уже наоборот, по этой строке или столбцу до подобного момента, пока не дойдём до конечной точки. У меня за ЕГЭ было 70 баллов, если можно лучше, то милости прошу...

[@vadimrumyantsev8498]

Это решение за m+n шагов, неэффективное. Савватеев предложил log(m)*log(n). Идея тут в том, что в отсортированных последовательностях нам нет необходимости просматривать все элементы. Искать в отсортированном массиве за линейное время - это серьёзный косяк с профессиональной точки зрения, который прямо бросается в глаза. Для школы, конечно, нормально, но Савватеев понимает, что это заведомо плохой алгоритм, и поэтому не стал его рассматривать, хотя он очевиден. Например, при m=1000000 и n=1 Савватеев решит задачу за 20 шагов, а вы за 500000. Хотя его алгоритм не самый лучший.

[@arsenypogosov7206]

@@vadimrumyantsev8498 Это решение действительно за O(n + m), только оно не верное. Саватеев "предложил" решение за O(log(max(n, m)), что невозможно. Вы "предлагаете" алгоритм за log(m)*log(n), что тоже не возможно. При этом говорите что линейное время - серьезный косяк, хотя очевидно что алгоритма быстрее не существует (для n = m). Забавно получается.

[@user-mp8su1yf5j]

Я, конечно, тупой, но в задаче по матрице нет критерия оптимизации. Значит что она решается "В лоб" перебором. Да, не оптимально, но без мысленных усилий и погнали дальше. Где я не прав? Кстати, при таком подходе фактор предварительной сортировки не имеет значения совсем

[@vadimrumyantsev8498]

Так это задача с собеседования, там вопрос не в формальном ответе, а в продемонстрированных навыках. Вам скажут: спасибо, до свидания.

[@user-wf7xo5zp2p]

Я первое задание даже решать не стала, потому что не люблю такие.

[@romanapanovich5267]

блин, с вероятностями у меня тупик. Но допустим так... надо взять две ситуации - когда за 30 минут автомобиль так и не появился и когда он всё-таки появился в течение 30 минут, какова вероятность того, что он появился именно в эти 10 минут (скажем, первые). Возьмём обратную вероятность - вероятность, что он не появится. В первом случае (5%) эта вероятность будет 100% (в любые 10 минут из этих 30 автомобиль не появится, так как он не появится вообще в течение этих 30 минут). А во втором (автомобиль всё таки появился в течение 30 минут, но не факт, что именно в эти) вероятность, что именно в эти 10 минут он не появился равна 2/3 Итого это будет 0.05*1 + 0.95*2/3 - итого получится 1.9/3+0.05 чето такое. И соответственно, вероятность, что появится всё таки равна 1-эта вероятность. Как-то некрасиво... но не вижу у себя логической ошибки.

[@romanapanovich5267]

ммм когда слушаю объяснение Савватеева - понимаю красоту и логичность его рассуждения... но найти ошибки у себя не могу. Хотя цифры выходят разные. Возможно, ошибка моя в правильном моделировании. Но чем моя формулировка отличается от оригинальной? Разве вероятность, что в течение 10 минут пройдёт машина и вероятность, что именно в ЭТИ 10 минут пройдет машина не одно и то же? Или если мы точно знаем, что в течение 30 минут пройдет автомобиль, разве суть задачи не сводится к тому, чтобы найти вероятность, что автомобиль из этих 30 минут НЕ пройдет в конкретно ЭТИ 10 минут? И если сводится, то разве данная вероятность при вышеупомянутом допущении не равна 2/3?

[@arsenypogosov7206]

@@romanapanovich5267 Она не равна 2/3, потому что может приехать больше одного автобуса. Вообще говоря задача не корректна, так как под условие подходит много разных вероятностных пространств. Ваш вариант ответа тоже имеет место быть. Например если автобус в начале дня выезжает в 0, 10 или 20 минут равновероятно, приезжает каждые 30 минут, но с вероятностью 5% пропускает очередной раз. Ответ Саватеева тоже имеет место быть, если предположить что вероятность прибытия автобуса в отрезки времени равной длины одинаковы и независимы в совокупности (если отрезки не пересекаются). Тогда для любого отрезка времени длиной в 10 мин рассмотрим еще 2 рядом. Если вероятность прибытия автобуса в один из отрезков p, то и в остальные тоже p в силу равновероятности. Тогда вероятность неприбытия во все три отрезка (1-p)^3 (в силу независимости). Тогда 1 - (1 - p)^3 = 0.95 => p = 1 - 0.05^(1/3) =~ 0.63.

[@user-uq1ef2wc5c]

Спасибо за твой комментарий, читая его, я осознал, что привести правильное решение - это ещё не показатель глубокого понимания его сути и сути темы в целом. А вот опровергнуть любое неверное решение, это уже другой уровень. Пытаясь понять, где же у тебя ошибка - я окунулся глубже в теорию вероятности. Не то чтобы я теперь всё отлично понимаю, но стало ясно, что есть куда копать... Насчет твоих рассуждений - 2\3 это уже кажется ошибка, для простоты обозначим вероятность того, что автобус приехал , как "1", а того, что не приехал, как "0", тогда у нас возможны всего 6 сценариев: 1-0-0 , 1-1-0, 1-0-1, 0-1-0, 0-1-1, 0-0-1 , и уже тут ясно, что если даже рассматривать эти варианты как равновероятные, то вероятность того, что он не вышел в первой десятке - 1\2 , но на самом деле это не так, т.к. вероятность того, что автобус приедет - больше вероятности того, что он не приедет, а значит случаи, когда автобус приехал в двух разных десятках сразу будут встречаться чаще, чем случаи когда автобус приехал только в одной из трех десяток. Итого наша вероятность будет зависеть от соотношения вероятностей того, приедет автобус за 10 минут или нет, а это нам неизвестно. По очень извилистому пути ты пошел конечно, но это хорошо. Насчет рассуждений про 0,05 и 100% вероятность - я до сих пор не могу понять, корректны они или нет, точнее больше склоняюсь к тому, что некорректны, но до конца не понимаю почему. Есть над чем подумать. Дебри конечно те ещё выходят, но только так наверное и можно начать по настоящему понимать теорию вероятностей, а не просто действуя по типичным алгоритмам, которые 50\50 понял\запомнил.

[@user-su5gn4dd4u]

Не могу жить.. Полный.. Фильм

[@MccDimarius]

А можно говорить в микрофон? Ничего же не слышно половину ролика. А задачки интересные.

[@user-mp8su1yf5j]

Мысль 3. Поиск по сортированной матрице относится к типовым проблемам и вообще не является интересной. TL:DR Сорри оставлял мысли по ходу

[@life_on_fire]

Анекдот про попугая вырезали, дизлайк отписка😂

[@IlyaMasalsky]

расскажите?)

[@nicholasspezza9449]

летит попугай и залетает пипиркой те в рот.

[@absfree123]

​@@nicholasspezza9449и дальше? Не гуглится

[@Mozgroin]

e^3~20.085

[@user-gl2tu2vj9b]

А может ктото пояснить как 0.63 получается во второй задаче?

[@hubertjf9726]

Крч, вероятность что за 30 минут проедет авто = 95%, значит вероятность что авто не проедет = 5%. (Или 0,05) Итак за первые 10 минут вероятность, что авто не появится Х, за вторые 10 минут Х^2, за третьи 10 минут Х^3. т.к события равновероятны, то вероятности перемножаются. Нужно извлечь куб из 5%. Это 5/100 или 1/20. В ходе вычислений получаем, что кубический корень из 20 ≈ 2,7 а следовательно кубический корень из 1/20 = 1/2,7 = 0,37. Итак вероятность того, что авто не появится за 10 минут 0,37. Значит вероятность того что появится 1-0,37 = 0,63.

[@user-uq1ef2wc5c]

"т.к. события равновероятны, то вероятности перемножаются" - не равновероятны, а - зависимые. Независимые вероятности складываются, а зависимые - перемножаются. Тут их равность не играет роли, но думаю ты просто опечатался. Поправил, дабы никто случайно не ввелся в заблуждение)) @@hubertjf9726

[@Frostgaming335]

😅 1 задачу вообще не понял о чем речь и что требуется 2 задача классная

[@user-su5gn4dd4u]

Пилу

[@user-me5cv1em8h]

9:10 Боюсь, что допущение независимости вероятностей Р-1 в каждые 10 минут - ошибочно. Процесс зависит от течения времени, вероятность что автомобиль не появится во вторые 10 минут уже ниже чем в первые.

[@user-ts6uy2xc8u]

С житейской точки зрения кажется, что вероятность меньше, на самом деле нет. Приведу классический пример с монетами, какова вероятность выпадения решка, если перед этим подряд выпало 10 орлов, монета идеально сбалансирована? Ответ 0,5 предыдущие результаты выпадения монеты не влияют на следующие

[@TurboGamasek228]

вы человек, который не знает вероятности

[@TtopYyyt-tm5ff]

@@user-ts6uy2xc8u он имел ввиду вкупе, а не отдельный результат, какова вероятность выпадения 10 орлов и решки?

[@absfree123]

​@@TtopYyyt-tm5ffтак это уже за 20 минут

[@155617]

господи, если машин нет 30 минут то их нет три раза по 10 минут - тоесть X^3 = 1-0.95;

[@lilbutcher2338]

нет, не X^3 = 1-0.95, а 0.05=(1-X)^3

[@seeker_in_the_shadows]

@@lilbutcher2338 Приветствую! Что значит нет? Какие трудности в записи X^3 = 1-0.95?

[@xxxxPomaHxxxx]

Первая задача очень не очень, непонятно что такое отсортированная матрица 1 1 1 2 4 6 3 3 3 вот это отсортировано или нет?

[@IlyaMasalsky]

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

[@cf8253]

Здесь второй и третий столбик не отсортированы, поэтому и матрица.

[@IlyaMasalsky]

@@cf8253 а если бы были отсортированы столбцы, то НЕ матрица?)

[@xxxxPomaHxxxx]

@@cf8253 Напиши как отсортировать её, какой результат? Во время сортировки можно вообще все элементы куда хочешь двигать что ле?

[@cf8253]

По определению: матрица отсортирована, если все её строки и все столбцы отсортированы. То есть это характеристика конкретной матрицы. Если мы хотим отсортировать некоторую матрицу, то нужно сперва определить операции, после выполнения которых будет получаться матрица, в некотором смысле эквивалентная исходной. (Как, например, при вычислении определителя: при транспонировании матрицы определитель не меняется.) Если элементы двигать как угодно, то все матрицы, содержащие одинаковые наборы чисел, будут для нас эквивалентны относительно такой сортировки.

[@user-su5gn4dd4u]

Осьрекаться, два корень из двкх